Proof of 3-fold Tensor Uniqueness

Question

In the notes linked below Professor Roughgarden states Theorem 3.1 without proof.

http://timroughgarden.org/s17/l/l10.pdf

Any ideas how one would go about proving this statement or references to where I would find such a proof?

Thanks

Answer 1

This is a classical result. (in fact Theorem 1 holds under less restrictive assumptions). This is the proof for $k=n$. Let $U$, $V$, and $W$ be $n\times n$ matrices formed by the vectors $u$, $v$, and $w$, respectively. It can be verified that the decomposition in Theorem 1 can be written as a set of $n$ matrix equations. $$ A(:,:,1) = U diag(W(1,:))V^T,\dots, A(:,:,n) = U diag(W(n,:))V^T,$$ where $A(:,:,m)$ denotes the $m$th frontal slice of the tensor $A$ and $W(m,:)$ denotes the $m$th row of $W$. If $A(:,:,2)$ is nonsingular (=invertible), then $$A(:,:,1)A(:,:,2)^{-1} = U diag(W(1,:))V^T(U diag(W(1,:))V^T)^{-1} = U diag(W(1,:))diag(W(2,:))^{-1} U^{-1}.$$ The matrix $diag(W(1,:))diag(W(2,:))^{-1}$ is diagonal, so
$$ A(:,:,1)A(:,:,2)^{-1}=U diag(W(1,:))diag(W(2,:))^{-1} U^{-1}$$ is the eigenvalue decomposition of $A(:,:,1)A(:,:,2)^{-1}$. It is known that if the the eigenvalues of $A(:,:,1)A(:,:,2)^{-1}$ are distinct (that is, the diagonal entries of $diag(W(1,:))diag(W(2,:))$), then the eigenvectors of $A(:,:,1)A(:,:,2)^{-1}$ can be uniquelly recovered (up to permutation and scaling of course). This gives you the way to compute matrix $U$ (This also proves that $U$ is unique up to permutation and scaling of its columns).

In general, $A(:,:,2)$ can be singular or $A(:,:,1)A(:,:,2)^{-1}$ may have repeated eigenvalues, so one replaces matrix equations with $A(:,:,1)$ and $A(:,:,2)$ by generic linear combinations of all matrix equations. It can be shown that both new matrix slices $A(:,:,1)$ and $A(:,:,2)$ are nonsingular. Note that generic linear combinations will also affect the diagonal matrices $diag(W(1,:))$ and $diag(W(2,:)$. Again it can be shown that for generic linear combinations the new diagonal matrix $diag(W(1,:))diag(W(2,:))$ will have distinct entries on the main diagonal. (That is why, in the Algorithm, the first step is to take random $x$ and $y$). The uniqueness of $V$ and $W$ can be proved in the same way.