1
$\begingroup$

Is there an algorithm for mapping a nonnegative tensor / kD array into stochastic form? i.e. assume we have a tensor of unnormalized counts, $c: ℕ^{n^k}$, can we derive a function $f: ℕ^{n^k} → ℝ^{n^k}$ such that:

  1. $f^{-1}(f(c)) \propto c$, and
  2. $∀ i, i'∈[0,k), D_i: \{D ∈ [0, n)^k | D[i']=i\} → Σ_{d_i ∈ D_i} f(c)[*d_i] = 1$? (where $n, k: ℕ$, $d_i: [0, n)^k$, $*$ is the spread operator and $[\cdot]$ is an index into $ℝ^{n^k}$)

In other words, every (k-1)D slice of the tensor should sum to 1. The $n=6, k=3$ case is depicted in the bottom row of the figure below:

slices_vs_tensors

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I can’t decipher your notation, but I would suggest playing around with applying projections using the KL-divergence as a “metric” a la Csiszar. If you explain your notation a bit more, I can try to expand this into a real answer. $\endgroup$ Commented May 22, 2021 at 2:41
  • $\begingroup$ Thanks for your reply. Essentially, I want all the univariate marginals to sum to 1, i.e. in the same way that every row and column of a bistochastic matrix is a probability vector, every possible projection of the tensor onto an (N-1)-D array should produce a normalized distribution. $\endgroup$ Commented May 22, 2021 at 3:08
  • $\begingroup$ Thanx. I’m still not one hundred percent clear what you are looking for. In Sinkhorn’s algorithm, as I understand it, you produce two matrices such that the product of all three matrices is stochastic. What do want the analog of those matrices to be? $\endgroup$ Commented May 22, 2021 at 11:32
  • $\begingroup$ The end result should be that every possible (k-1)-D slice of the tensor sums to 1. I'm not entirely convinced a general algorithm exists, but it seems like it should be possible. There are some recent results (c.f. arxiv.org/pdf/1702.08142.pdf) which show it is possible to construct a tensor whose 1D fibers are all probability vectors. My intuition is, it would be easier to solve for slices since the total number of constraints to satisfy would be much fewer (i.e. only kn slices to normalize instead of kn^(k-1) fibers). But I could be wrong, maybe the analogy breaks down after k=2. $\endgroup$ Commented May 24, 2021 at 21:13

1 Answer 1

Reset to default
1
$\begingroup$

Here’s a generalization on the Sinkhorn/RAS/IPFP algorithm that may get you what you want.

Give a tensor $T^{i_1i_2\dots}$, define $S_n(T) = \sum_{\mbox{all but }i_n} T^{i_1i_2\dots}$. What I am guessing is that you want a way of going from $T$ to a new tensor $f(T)$ such that $S_n(f(T)) = 1$ (where $1$ is a vector of ones) for all $n$.

I don’t think you have put enough conditions to restrict $f$ above, but here is something that should work. For a given vector $v$, we define the multiplication $D_{n,v}(T) = v^{i_n} T^{i_1i_2\dots}$ — note that there is no sum and the $i_n$ index appears twice. This generalizes matrix multiplication by the diagonal matrix associated with $v$.

Now, the algorithm will proceed by cyclically going through all values for $n$ (ie, from 1 to the rank of the tensor). At each step, calculate $v = 1/S_n(T)$ where $T$ is the tensor from the previous step and the reciprocal is calculated componentwise. Now apply $D_{n,v}$ to obtain a new tensor. I claim that, as long as a tensor with the same set of zeroes as what you started with exists that satisfies the desired stochastic condition, this algorithm will converge to the tensor you are looking for. Furthermore, each of the $D_{n,v}$ with the same $n$ can be combined, so that the resulting tensor is given by applying a single $D_{n,v}$ for each $n$.

The proof follows directly from Csiszar’s paper:

Csiszár, Imre. "I-divergence geometry of probability distributions and minimization problems." The Annals of Probability (1975): 146-158. https://www.jstor.org/stable/2959270?seq=1

This is a version of the alternating projection algorithm, using the KL-divergence as a “metric”. The algorithm converges to the “projection” on the space of tensors with the desired stochastic form. In fact, it’s not too hard to generalize the proof in the paper above to drop the requirement that the operators are applied cyclically, as long as each occurs an infinite number of times.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I appreciate your detailed reply! Thank you for the reference to Csiszár (1975) which looks relevant. What I am guessing is that you want a way of going from T to a new tensor f(T) such that S_n(f(T))=1 (where 1 is a vector of ones) for all n. I think this condition not strong enough. If we consider the n=2 case, this will produce a stochastic matrix, but not a doubly-stochastic matrix. We need all possible (k-1)D slices to be normalized, not just a single one. Re: I don’t think you have put enough conditions to restrict f above... What other restrictions would you have added? $\endgroup$ Commented May 25, 2021 at 20:38
  • 1
    $\begingroup$ Note that the condition holds for all $n$. This ensures that it is doubly stochastic in the matrix case where the two conditions for $n=1, 2$ restrict the row sums and the column sums to each be a vector of ones. $\endgroup$ Commented May 25, 2021 at 20:58

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.