Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability

Introduction

Statisticians have long studied the identifiability of probabilistic models [Tei61, Tei67, TC82], i.e. whether the parameters of a model can be learned from data generated by the model. A central question in unsupervised learning [Gha04] is the efficient computation of such latent model parameters from observed data. A necessary step towards efficient (polynomial time) learning is to show that the parameters are indeed identifiable after observing polynomially many samples. The method of moments approach, pioneered by Pearson [Pea94], infers model parameters from empirical moments such as means, pairwise and other higher order correlations. In general, very high order moments may be needed for this approach to succeed and the unreliability of empirical estimates of these moments leads to exponential sample complexity [MV10, BS10, GLPR12].

An exciting sequence of recent work [MR06, AHK12, HK12, AGH+12] has met with considerable success in cases where the underlying models satisfy a certain non-degeneracy condition (that we will explain later). Informally, the condition requires that the dimension ($n$) of the observations is at least as large as the number of possible values ($R$) for the hidden variable and that certain model parameters are in general position. The moments are naturally represented by tensors (high dimensional analogs of matrices) and low rank decompositions of such tensors can be used to deduce the parameters of the underlying model. Under suitable non-degeneracy assumptions, the required tensor decompositions can be computed efficiently using an iterative procedure akin to power iteration for computing matrix eigenvalues. One focus of our work is developing tensor decomposition techniques that apply in more general settings where these non-degeneracy assumptions are violated, i.e. $n$ is much smaller than $R$. Such settings do arise in many cases of practical interest such as in applications of hidden Markov models to speech recognition and image classification, where the dimension ($n$) of the feature space is typically much smaller than the number of values ($R$) for the hidden variable. For instance, the (effective) feature space corresponds to just the low-frequency components in the fourier spectrum in speech, or the local neighborhood of a pixel in images. These are typically low dimensional than the number of words or image classes.

In fact, the connection of tensor decompositions to learning probabilistic models has been made earlier in the algebraic statistics literature. In a series of papers, identifiability of several latent variable models was established [AMR09, APRS11, RS12] via low rank decomposition of certain moment tensors. A fundamental result of Kruskal [Kru77] on uniqueness of tensor decompositions plays a crucial role in ensuring that the model parameters are correctly identified by this procedure. Note that this assumes access to an infinite number of samples and does not give any information on the number of samples needed to learn the model parameters within specified error bounds. Kruskal’s theorem by itself is not useful for establishing any such sample complexity bounds since it only guarantees uniqueness for low rank decompositions of the actual moment tensors. It does not say anything about the decomposition of empirical moment tensors which are approximations of these. In order to understand how large a sample size is needed, one would need a robust uniqueness guarantee of this form: if the empirical moment tensor $T^{\prime}$ is close to the moment tensor $T$, then a low rank decomposition of $T^{\prime}$ is (term by term) close to a low rank decomposition of $T$.

Our main technical contribution in this work is establishing such a robust version of Kruskal’s classic uniqueness theorem for tensor decompositions. This provides a uniqueness guarantee that is directly applicable for establishing polynomial identifiability in a host of applications [AMR09] where Kruskal’s theorem was used to prove identifiability assuming access to exact moment tensors. Since polynomially many samples from the distribution (typically) yield an approximation to these tensors up to $1/\text{poly}(n)$ error, our robust version of Kruskal’s theorem establishes polynomial identifiability in all such applications. To the best of our knowledge, no such robust version of Kruskal’s theorem is known in the literature. Given the importance of this theorem in the tensor literature, we expect that this robust version will have applications beyond the settings we explore in this work. Our robust uniqueness theorem is accompanied by new algorithms to find low rank tensor decompositions.

A tensor is a multidimensional array – a generalization of vectors and matrices e.g. an $n_{1}\times n_{2}\times n_{3}$ tensor is a 3-tensor which is an element in $R^{n_{1}\times n_{2}\times n_{3}}$. Low rank tensor decompositions (analogs of SVD for matrices) have been studied intensively as methods for extracting structure in data. These originated in work of Hitchcock [Hit27] and Cattell [Cat44]. They were studied in the 60’s and 70’s in the psychometrics literature and since the 80’s, in the chemometrics literature. The notion of tensor rank also plays an important role in algebraic complexity, and is closely connected to the exponent of matrix multiplication. More recently, tensor decompositions have found applications in signal processing, numerical linear algebra, computer vision, numerical analysis, data mining, graph analysis, neuroscience and more.

Carroll and Chang [CC70] introduced CANDECOMP (canonical decomposition) and independently, Harshman [Har70] introduced PARAFAC (parallel factors). CANDECOMP/PARAFAC is now referred to as CP decomposition [Kie00]. It expresses a tensor as a sum of rank-one tensors where each rank-one tensor is the outer product of column vectors. The rank of a tensor is the minimum number of terms required for such a decomposition. While the definition of tensor rank is analogous to that of matrix rank, their properties are quite different. In fact, computing the rank of a tensor is NP-hard [Hås90] and in fact several other problems associated with low rank approximation of tensors are NP-hard as well [HL13].

For matrices, a fundamental result of Eckart and Young [EY36] shows that the best rank-$k$ approximation consists of the leading $k$ terms of the SVD. This is not the case for CP decomposition of tensors – the best rank one approximation may not be a factor in the best rank two approximation. In fact, the best rank $k$-approximation may not exist. For example, certain tensors of rank-three can be arbitrarily well approximated by a sequence of rank-two tensors [Knu, Paa00, DSL08, Lan12]. In fact, the set of tensors of a certain size that do not have a best rank-$k$ approximation has positive volume [DSL08]. To overcome this problem, the concept of border rank was introduced and studied in the algebraic complexity community. This is defined to be the minimum number of rank-one tensors that are sufficient to approximate the given tensor with arbitrarily small error. In fact, the complexity of matrix multiplication is exactly captured by the border rank of the associated tensor [KB09, Lan12].

An important property of higher order tensors is that (under certain conditions) their minimum rank decompositions are unique upto trivial scaling and permutation. This is in contrast to matrix decompositions. Note that the SVD of a matrix is unique (assuming distinct singular values) only because we impose additional orthogonality constraints.

A classic result of Kruskal [Kru77] gives a sufficient condition for uniqueness of the CP decomposition of a 3-tensor. Suppose that a 3-tensor $T$ has the following decomposition:

Let the Kruskal rank or K-rank $k_{A}$ of matrix $A$ (formed by column vectors $A_{r}$) be the maximum value of $k$ such that any $k$ columns of $A$ are linearly independent. $k_{B}$ and $k_{C}$ are similarly defined. Kruskal’s result says that a sufficient condition for the uniqueness of the decomposition (1) is

We give a robust version of of Kruskal’s uniqueness theorem for decomposition of 3-tensors. To this end, we need a natural robust analogue of Kruskal rank: we say that $\text{K-rank}_{\tau}(A)\geq k$ if every submatrix of $A$ formed by $k$ of its columns has minimum singular value at least $1/\tau$. A matrix is called bounded if its column vectors have bounded length. Finally, we measure closeness between two tensors or two matrices by the Frobenius norm of their difference. Please see Section 2 for precise definitions.

Our first result shows that any tensor with bounded decomposition that satisfies the robust Kruskal condition has a unique decomposition upto small error (formal statement in Section 2):

Informal Theorem. If any order $3$ tensor $T$ has a bounded rank $R$ decomposition $[A~{}B~{}C]$, where the robust $\text{K-rank}_{\tau}$ $k_{A},k_{B},k_{C}$ satisfy $k_{A}+k_{B}+k_{C}\geq 2R+2$, then any decomposition $[A^{\prime}~{}B^{\prime}~{}C^{\prime}]$ that is $\varepsilon$-close to $T$ has $A^{\prime},B^{\prime},C^{\prime}$ being individually $\varepsilon^{\prime}$-close to $A,B$ and $C$ respectively when $\varepsilon<\varepsilon^{\prime}\cdot\text{poly}(R,n,\tau)$.

A similar theorem (see Theorem 2.7) also holds for higher order tensors and the analogous robust Kruskal rank condition is exactly (3) where $k_{{U}^{(j)}}$ corresponds to the robust Kruskal rank of ${U}^{(j)}$. Note that when all the ${U}^{(j)}$ have the same rank, the robust Kruskal condition becomes weaker for higher order tensors.

Why is it non-trivial to obtain a robust version from existing proofs? Kruskal’s theorem gives conditions under which the components of a tensor decomposition can be identified uniquely. However the proofs that we are aware of strongly use inductive lemmas which prove that subsets of the components of one decomposition have to necessarily belong in any other potential decomposition, and use them to conclude that any two decompositions are in fact the same. When working with representations that are only nearly equal, these inductive arguments typically accumulate errors in each step, thereby requiring the initial error to be exponentially small in order to reach the desired conclusion. Such a result would not be of any value for establishing polynomial sample complexity bounds, since the sample size would need to be exponentially large for the empirical moment tensors to approximate the true moment tensor within such a low error. We overcome this issue by using arguments that are purely combinatorial whenever possible, and carefully avoiding a loss at each step.

Since finding low-rank decomposition of tensors is of great practical interest, it is natural to study algorithms for this problem. While this and many related problems are NP-hard in general [HL13], we give an algorithm which given an approximation to a tensor, finds an approximate low-rank decomposition in time exponential only in the rank (and not the dimensions of the tensor).

Informal Theorem. Given a tensor with a bounded, rank $R$ decomposition up to an error $\varepsilon$, we can find a rank $R$ approximation with error $O(\varepsilon)$ in time $\exp(R^{2}\log(n/\varepsilon))\text{poly}(n)$.

This can be viewed as a tensor analog of low-rank approximation, which is very well-studied for matrices. Note that our algorithm does not require the promised decomposition to have additional well-conditioned properties. If we additionally have such guarantees (for e.g., that the sum of K-rank of the components is high), then Theorem 2.7 implies that the algorithm finds this particular decomposition (up to a small error).

2 Latent Variable Models

We now describe some of the latent variable models that our results are applicable to. We will formally state the identifiability and algorithmic results we obtain for each of these in Section 5.

Multi-view models are very expressive, and capture many well-studied models like Topic Models [AHK12], Hidden Markov Models (HMMs) [MR06, AMR09, AHK12], random graph mixtures [AMR09], and the techniques developed for this class have also been applied to phylogenetic tree models [Cha96, MR06] and certain tree mixtures [AHHK12].

Exchangeable (single) Topic Model

Hidden Markov Models

As mentioned previously, in many important applications of HMMs, $n$ is much smaller than $R$. e.g. in image classification, the commonly used SIFT features [Low99] are 128 dimensional, while the number of image classes is much larger, e.g. 256 classes in the Caltech-256 dataset [GHP07] and several thousands in the case of ImageNet [DDS+09]. Similarly, in speech recognition, the features of an audio signal are typically based on mel-frequency cepstral coefficients (MFCCs) or an encoding called perceptual linear prediction (PLP) that incorporates psychoacoustic constraints [GY08], e.g. these are used to obtain a 39 dimensional feature vector in the popular HTK toolkit for building HMMs for speech recognition [YEG+02, WGPY97]. On the other hand, the number of states in these HMMs is much larger. Further, in some other applications, even when the feature vectors lie in a large dimensional space ($n\gg R$), the set of relevant features or the effective feature space could be a space of much smaller dimension ($k<R$), that is unknown to us.

Mixtures of Spherical Gaussians

Informal Theorem. For a multi-view model with $R$ topics or distributions, such that each of the parameter matrices ${M}^{(j)}$ has robust K-rank of at least $\delta R$ for some constant $\delta$, we can learn these parameters upto error $\varepsilon$ with high probability using $\text{poly}_{\delta}(n,R)$ samples. Further, these parameters can be approximately computed in time $\exp_{\delta}\left(R^{2}\log(n/\varepsilon)\right)\text{poly}(n)$ time.

Polynomial identifiability was not known previously for these models in the settings that we consider. Moreover, except for the well studied setting of mixtures of Gaussians, no provably good algorithms were known (even with running time $\exp(\text{poly}(R))$).

For mixtures of Gaussians, our results shed more light on polynomial identifiability: the algorithm of [AGH+12, HK13] shows how to identify mixtures of (spherical) Gaussians efficiently when we have $R$ Gaussians in $d$ dimensions, when the means satisfy certain well-conditioned properties (which in particular requires $d\geq R$). When $d=2$, Moitra and Valiant [MV10] rule out polynomial identifiability by giving two distributions for which we require exponentially many samples to distinguish one from the other. Thus it is natural to ask what happens in between, when $d<R$, but is not too small. Our results imply that a mixture of $R$ Gaussians of known variance in a $\delta R$ dimensional space (any $\delta>0$) can be identified with polynomially many samples.

3 Overview of Techniques

The main technical contribution of our paper is the Robust Uniqueness theorem for Tensor decompositions. Our proof broadly follows the outline of Kruskal’s original proof [Kru77]: It proceeds by establishing a certain Permutation lemma, which gives necessary conditions to conclude that the columns of two matrices are permutations of each other (up to scaling). Given two decompositions $[A~{}B~{}C]$ and $[A^{\prime}~{}B^{\prime}~{}C^{\prime}]$ for the same tensor, it is shown that $A,A^{\prime}$ satisfy the conditions of the lemma, and thus are permutations of each other. Finally, it is shown that the three permutations for $A,B$ and $C$ (respectively) are identical. To prove the robust uniqueness theorem, the key ingredient is a robust version of the permutation lemma.

The first step in our argument is to prove that if $A$, $B$, $C$ are “well-conditioned” (i.e., satisfy the K-rank conditions of the theorem), then any other “bounded” decomposition which is $\varepsilon$-close is also well-conditioned. This step is crucial to our argument, while an analogous step was not explicitly needed for the proofs of exact uniqueness theorem.Note that the uniqueness theorem, in hindsight, establishes that the other decomposition is also well-conditioned. Besides, this statement is interesting in its own right: it implies, for instance, that there cannot be a smaller rank (bounded) decomposition.

The second and most technical step is to prove the robust permutation lemma. The (robust) Permutation lemma needs to establish that for every column of $C^{\prime}$, there is some column of $C$ close to it. Kruskal’s proof [Kru77] roughly uses downward induction to establish the following claim: for every set of $i\leq$ K-rank columns of $C^{\prime}$, there are at least as many columns of $C$ that are in the span of the chosen vectors. The downward induction infers this by considering intersections of columns close to $i+1$ dimensional spaces.

The natural analogue of this approach would be to consider columns of $C$ which are $\varepsilon$-close to the spans of subsets of columns of $C^{\prime}$. However, the inductive step involves considering combinations and intersections of the different spans that arise, and such arguments do not seem very tolerant to noise. In particular, we lose a factor of $\tau n$ in each iteration, i.e., if the statement was true for $i+1$ with error $\varepsilon_{i+1}$, it will be true for $i$ with error $\varepsilon_{i}=\tau n\cdot\varepsilon_{i+1}$. Since $k$ steps of downward induction need to be unrolled, we recover a robust permutation lemma only when the error $<1/(\tau n)^{k}$ to start with, which is exponentially small since $k$ is typically $\Theta(n)$.

We overcome this issue by showing a different, more tricky inductive statement, whereby we do not lose any error in the recursion. This is described in Section 3.3. To carry forth this argument we crucially rely on the fact that $C^{\prime}$ is also “well-conditioned” and other observations.

At a high level, our algorithm for finding a rank $R$ approximation proceeds by finding a small ($O(R)$) dimensional space and then exhaustively searching, which takes time $\exp(R^{2}\log n)\text{poly}(n)$. Note that a naive exhaustive search using an $\varepsilon$-net in the entire $n$ dimensional space would incur a run time of $\exp(Rn)\text{poly}(n)$, which is much worse if $n\gg R$.

Suppose the best rank $R$ approximation to an input tensor has error $\varepsilon$. We first find an $R$-dimensional space for each of the (three) dimensions, so that there is an $O(\varepsilon)$-close rank $R$ decomposition that comprises vectors only from the corresponding $R$-dimensional spaces. We note that the spaces we find need not correspond to the span of the components in the optimum decomposition, but they suffice to obtain an $O(\varepsilon)$ approximation. Another feature of the algorithm is that it does not assume that the tensor has an approximate “well conditioned” decomposition, and assumes only boundedness.

4 Related Work

While our applications to learning latent variable models are inspired by the works of [AHK12, AGH+12], our results are significantly different, particularly from a tensor decomposition perspective. Anandkumar et al [AGH+12] give algorithms for tensors which have a symmetric orthogonal decomposition, i.e. a decomposition of the form $\sum_{r=1}^{R}A_{r}\otimes A_{r}\otimes A_{r}$ where the vectors $A_{r}$ are orthogonal. In general, a rank-$R$ tensor may not have any orthogonal decomposition. Note that any tensor in $n\times n\times n$ dimensions, which has rank $R>n$ can not have an orthogonal decomposition. While this is one source of intractability for general tensor decompositions [HK12], we crucially use such tensors of rank $R>n$ to give polynomial identifiability beyond the non-degenerate range ($R\leq n$).

For various latent variable models, in the non-degenerate setting (where the number of mixtures/ topics $R$ is larger than the dimension of the space $n$), Anandkumar et al [AGH+12] use order $3$ tensors given by the third moment tensor to identify the hidden parameters. In these tensors, each rank-$1$ component corresponds to a hidden parameter, like one of the means. While these parameters may not be orthogonal, a certain “whitening” transform of the space [AHK12, HK12] produces a new instance in which these means are now orthogonal. For this they crucially rely on two assumptions:

The $n\times R$ matrix of the means has rank $\geq R$ (and well conditioned). This of course needs $R\leq n$.

The algorithm has access to the second moment tensorThis is certainly a valid assumption when learning latent variable models. This assumption will not hold in the case of the general problem of tensor decompositions.

Finally, in the context of learning latent variable models, we go beyond the non-degeneracy barrier and get polynomial identifiability even when $n=\delta R<R$. One interesting aspect of our results is that we use successively higher $O(1)$-moments to handle larger values of $R$ (hidden topics/ mixtures). This smooth tradeoffNote that the $R^{th}$ moment is sufficient to identify the parameters typically [BS10, MV10, FSO06]. is in contrast to the works of [AHK12, HK12, AGH+12], where they seem to get no additional advantage out of higher moments (larger than $3$). Further, even when using third moments, [AHK12, HK12, AGH+12] only obtain polynomial identifiability when $R\leq n$, whereas we obtain polynomial identifiability till $R=3n/2-1$. On the other hand, since we argue about identifiability directly through uniqueness theorems for tensors, it allows us to handle larger values of $R$.

We also mention work on PAC learning of mixtures of $k$ product distributions (see e.g. [FOS05, FSO06]) that typically run in $\exp(k)\text{poly}(n)$ time and produce a distribution that is statistically close to the underlying distribution – however they do not recover the actual mixture components themselves.

Some preliminaries and our results

We start with basic notation on tensors which we will use throughout the paper. We then state our results formally in these terms, and place them in context. In the process, we will see some intriguing properties of tensors (relevant to our results) which distinguish them from matrices.

where we use the notation $A_{r}$ to denote the $r$th column vector of matrix $A$.

Third order tensors (or $3$-tensors) play a central role in understanding properties of tensors in general (as in many other areas of mathematics, the jump in complexity occurs most dramatically when we go from two to three dimensions, in this case from matrices to $3$-tensors). For $3$-tensors, we will often write the decomposition as $[A~{}B~{}C]$, where $A,B,C$ have dimensions $n_{A},n_{B},n_{C}$ respectively.

We will sometimes write this as $T_{1}=_{\varepsilon}T_{2}$.

An $n\times R$ matrix $A$ is said to be $\rho$-bounded if each of the columns has length at most $\rho$, for some parameter $\rho$.

We next define the notion of Kruskal rank, and its robust counterpart.

Let $A$ be an $n\times R$ matrix. The K-rank (or Kruskal rank) of $A$ is the largest $k$ for which every set of $k$ columns of $A$ are linearly independent.

Let $\tau$ be a parameter. The $\tau$-robust k-rank is denoted by $\text{K-rank}_{\tau}(A)$, and is the largest $k$ for which every $n\times k$ sub-matrix $A_{|S}$ of $A$ has $\sigma_{k}(A_{|S})\geq 1/\tau$.

Note that we only have a lower bound on the ($k$th) smallest singular value of $A$, and not for example the condition number $\sigma_{\max}/\sigma_{k}$. This is because we will usually deal with matrices that are also $\rho$-bounded, so such a bound will automatically hold, but our definition makes the notation a little cleaner. We also note that this is somewhat in the spirit of (but much weaker than) the Restricted Isometry Property (RIP) [CT05] from the Compressed Sensing literature.

Another simple linear algebra definition we use is the following

To avoid complications due to scaling, we will assume that our tensors are scaled such that all the $\tau_{A},\tau_{B},\dots,$ are $\geq 1$ and $\leq\text{poly}(n)$. So also, our upper bounds on lengths $\rho_{A},\rho_{B},\dots$ are all assumed to be between $1$ and some $\text{poly}(n)$. This helps simplify the statements of our lemmas.

We will, in many places, encounter statements such as “if $Q_{1}\leq\varepsilon$, then $Q_{2}\leq(3n^{2}\gamma)\cdot\varepsilon$”, with polynomials $\vartheta$ (in this case $3n^{2}\gamma$) involving the variables $n,R,k_{A},k_{B},k_{C},\tau,\rho,\dots$. In order to keep track of these, we use the notation $\vartheta_{1},\vartheta_{2},\dots$. Sometimes, to refer to a polynomial introduced in Lemma 3.11, for instance, we use $\vartheta_{3.11}$. Unless specifically mentioned, they will be polynomials in the parameters mentioned above, so we do not mention them each time.

2 Our Results

We are now ready to formally state the results in our work. The first is a robust version of the uniqueness of decomposition for $3$-tensors.

Suppose a rank-$R$ tensor $T=[A~{}B~{}C]$ is $(\rho_{A},\rho_{B},\rho_{C})$-bounded, with $\text{K-rank}_{\tau_{A}}(A)=k_{A},\text{K-rank}_{\tau_{B}}(B)=k_{B},\text{K-rank}_{\tau_{C}}(C)=k_{C}$ satisfying $k_{A}+k_{B}+k_{C}\geq 2R+2$. Then for every $0<\varepsilon^{\prime}<1$, there exists

for some polynomial $\vartheta_{\ref{thm:unique3}}$ such that for any other $(\rho^{\prime}_{A},\rho^{\prime}_{B},\rho^{\prime}_{C})$-bounded decomposition $[A^{\prime}~{}B^{\prime}~{}C^{\prime}]$ of rank $R$ that is $\varepsilon$-close to $[A~{}B~{}C]$, there exists an ($R\times R$) permutation matrix $\Pi$ and diagonal matrices $\Lambda_{A},\Lambda_{B},\Lambda_{C}$ such that

We remark that in order to prove the theorem, we did not make any assumptions about the Kruskal ranks of $A^{\prime},B^{\prime},C^{\prime}$. We simply assumed that they are bounded. This is an interesting feature of our proof, and is formalized in Lemma 3.4. Another observation: though we assumed that the decomposition $[A^{\prime}~{}B^{\prime}~{}C^{\prime}]$ is rank $R$, we really need only an upper bound. This is because we can append zeroes and apply the theorem.

Our next result is a higher dimensional analogue of the above.

Since finding a small rank decomposition of a tensor is of great practical interest as we have seen, it is natural to ask if it is possible to compute it efficiently. We can prove:

Suppose $T$ is a $3$-tensor which has an (unknown) $\rho$-bounded representation $[A~{}B~{}C]$, where $A,B,C$ have dimensions $n_{A}\times R,n_{B}\times R$ and $n_{C}\times R$ respectively, for some parameter $\rho$. Then, given a tensor $T^{\prime}$ which is $\varepsilon$-close to $T$, we can find a rank-$R$ tensor $T^{\prime\prime}$ (along with its decomposition) which is $5\varepsilon$ close to $T$ in time $\text{poly}(n_{A},n_{B},n_{C})\cdot\exp(R^{2}\log(R\rho/\varepsilon))$.

We can view the above as an approximation algorithm for the low-rank approximation problem for tensors. We will expound on this viewpoint in Section 4. We also note that although our algorithm is quite simple, it has a running time better than simply trying to guess the $3R$ vectors in the decomposition. The latter typically takes time $\exp(R(n_{A}+n_{B}+n_{C}))$, which could be much worse than our bound for small values of $R$ (which is when the low rank approximation problem is typically interesting).

As we mentioned before, the algorithm does not need the promised decomposition $[A~{}B~{}C]$ to have large K-rank . However, if we are guaranteed that it has additional well-conditioned properties (for e.g., the sum of K-rank of $A,B,C$ is $\geq 2R+2$), then Theorem 2.7 guarantees that the algorithm finds this particular decomposition (up to a small error).

Also, the algorithm extends naturally to higher dimensional tensors: we state this version in Section 4, Theorem 4.5.

Finally, we show how the above results on tensor decompositions can be used to learn latent variable models with polynomial samples, hence showing polynomial identifiability under some weak conditions involving the K-rank of the matrices. We first show polynomial identifiability for the Multi-view mixture model, which captures various latent variable models that are used commonly.

For each mixture $r\in[R]$, the mixture weight $w_{r}>\gamma$.

Polynomial identifiability of the Multi-view mixture model also leads to polynomial identifiability of other latent variable models like topic models and HMMs. The following corollary shows that Hidden Markov models can be learned from polynomial many samples by observing constant number of consecutive time steps under mild conditions involving the K-rank (the constant depends on the exact K-rank condition). Please refer to section 5 to see the implications for other latent variable and mixture models like topic models, mixtures of gaussians etc.

Corollary 5.5 (Polynomial Identifiability of Hidden Markov models). The following statement holds for any constant $\delta>0$. Suppose we are given a Hidden Markov model with parameters as follows :

The stationary distribution $\{w_{r}\}_{r\in[R]}$ has $\forall r\in[R]~{}w_{r}>\gamma_{1}$,

The observation matrix $M$ has $\text{K-rank}_{\tau}(M)\geq k\geq\delta R$,

The transition matrix $P$ has minimum singular value $\sigma_{R}(P)\geq\gamma_{2}$,

Further, this algorithm runs in time $n^{O_{\delta}(R^{2}\log(\frac{1}{\eta\gamma_{1}}))}\left(n\cdot\frac{\tau}{\gamma_{1}\gamma_{2}}\right)^{O_{\delta}(1)}$ time.

Note that the above results shows polynomial identifiability (for constant $\delta>0$), and additionally gives an algorithm which takes time $n^{O_{\delta}(R^{2})}\text{poly}(n,\tau,R)$ for inverse polynomial error. To the best of our knowledge such algorithmic results with only a polynomial dependence on $n$ were not known for learning HMMs and topic models.

3 Auxiliary lemmas

In our proofs we will require several simple (mostly elementary linear algebra) lemmas. The Section A is a medley of such lemmas. Most of the proofs are reasonably straightforward, and thus we place them in the Appendix.

Uniqueness of Tensor Decompositions

First we consider third order tensors and prove Theorem 2.6 (Sections 3.1 and 3.2). Our proof broadly follows along the lines of Kruskal’s original proof of the uniqueness theorem [Kru77]. The key ingredient, which is a robust version of the so-called permutation lemma is presented in Section 3.3, since it seems interesting its own right. Finally we will see how to reduce the case of higher order tensors, i.e. Theorem 2.7, to that of third order tensors (Section 3.4).

The proof of Theorem 2.6 broadly has two parts. First, we prove that if $[A,B,C]=[A^{\prime},B^{\prime},C^{\prime}]$, then $A$ is a permutation of $A^{\prime}$, $B$ of $B^{\prime}$, and $C$ of $C^{\prime}$. Second, we prove that the permutations in the (three) different “modes” (or dimensions) are indeed equal. Let us begin by describing a lemma which is key to the first step.

This is the core of Kruskal’s argument for the uniqueness of tensor decompositions. Given two matrices $X$ and $Y$, how does one conclude that the columns are permutations of each other? Kruskal gives a very clever sufficient condition, involving looking at test vectors $w$, and considering the number of non-zero entries of $w^{T}X$ and $w^{T}Y$. The intuition is that if $X$ and $Y$ are indeed permutations, these numbers are precisely equal for all $w$.

Kruskal proves that if this sufficient condition holds, then $X$ and $Y$ must have columns which are permutations of each other, up to scaling. More precisely, suppose $X,Y$ are $n\times R$ matrices of rank $k$. Let $nz(x)$ denote the number of non-zero entries in a vector $x$. The lemma then states that if for all $w$, we have

then the matrices $X$ and $Y$ have columns which are permutations of each other up to a scaling. That is, there exists an $R\times R$ permutation matrix $\Pi$, and a diagonal matrix $\Lambda$ s.t. $Y=X\Pi\Lambda$.

We prove a robust version of this lemma, stated as follows (recall the definition of $nz_{\varepsilon}(.)$, Section 2)

Suppose $X,Y$ are $\rho$-bounded $n\times R$ matrices such that $\text{K-rank}_{\tau}(X)$ and $\text{K-rank}_{\tau}(Y)$ are $\geq k$, for some integer $k\geq 2$. Further, suppose that for $\varepsilon<1/\vartheta_{\ref{lem:permutation-poly}}$, the matrices satisfy:

then there exists an $R\times R$ permutation matrix $\Pi$, and a diagonal matrix $\Lambda$ s.t. $X$ and $Y$ satisfy $\left\|X-Y\Pi\Lambda\right\|_{F}<\vartheta_{\ref{lem:permutation-poly}}\cdot\varepsilon$. In fact, we can pick $\vartheta_{\ref{lem:permutation-poly}}:=(nR^{2})\vartheta_{\ref{lem:key-intersection}}$.

In the remainder of this section, we will prove that $A^{\prime}$ is a permutation of $A$, $B^{\prime}$ of $B$ and $C^{\prime}$ of $C$. We do this by assuming Lemma 3.1 for now (it will be proved in Section 3.3) and proving that if $[A~{}B~{}C]=_{\varepsilon}[A^{\prime}~{}B^{\prime}~{}C^{\prime}]$, then the conditions of the lemma hold for $C^{\prime},C$ as $X,Y$ in the statement respectively. We can repeat this argument with $A,B$ to obtain the conclusion.

We now state the key technical lemma which allows us to verify that the hypotheses of Lemma 3.1 hold. It says for any $k_{C}-1$ vectors of $C^{\prime}$ there are at least as many columns of $C$ which are close to the span of the chosen columns from $C^{\prime}$.

Suppose $A,B,C,A^{\prime},B^{\prime},C^{\prime}$ satisfy the conditions of Theorem 2.6, and suppose $[A~{}B~{}C]=_{\varepsilon}[A^{\prime}~{}B^{\prime}~{}C^{\prime}]$. Then for any unit vector $x$, we have

for $\varepsilon^{\prime\prime}=\vartheta_{\ref{lem:perm:conditions}}\cdot(\varepsilon+\varepsilon^{\prime})$, where $\vartheta_{\ref{lem:perm:conditions}}:=4R^{3}(\tau_{A}\tau_{B}\tau_{C})^{2}\rho_{A}\rho_{B}\rho_{C}(\rho^{\prime}_{A}\rho^{\prime}_{B}\rho^{\prime}_{C})^{2}$.

This lemma, together with its corollary Lemma 3.4 will imply the conditions of the permutation lemma. Lemma 3.4 lets us conclude that $\text{K-rank}_{\tau\vartheta}(C^{\prime})\geq\text{K-rank}_{\tau}(C)$ for some error polynomial $\vartheta$, which is essential in our proof of the permutation lemma. It also has other implications, as we will see. While the proof of the robust permutation lemma (Lemma 3.1) will directly apply this Lemma with $\varepsilon^{\prime}=0$, we will need the $\varepsilon^{\prime}>0$ case for establishing Lemma 3.4.

W.l.o.g., we may assume that $k_{A}\geq k_{B}$ (the proof for $k_{A}<k_{B}$ will follow along the same lines). For convenience, let us define $\alpha$ to be the vector $x^{T}C$, and $\beta$ the vector $x^{T}C^{\prime}$. Let $t$ be the number of entries of $\beta$ of magnitude $>\varepsilon^{\prime}$. The assumption of the lemma implies that $t\leq R-k_{C}+1$. Now from (9), we have

where $Z$ is an error matrix satisfying $\left\|Z\right\|_{F}\leq\varepsilon$. Now, since the RHS has at most $t$ terms with $|\beta_{i}|>\varepsilon^{\prime}$, we have that $\sigma_{t+1}$ of the LHS is at most $R\rho_{A}^{\prime}\rho_{B}^{\prime}\varepsilon^{\prime}+\varepsilon$. Using the value of $t$, we obtain

We will now show that if $x^{T}C$ has too many co-ordinates which are larger than $\varepsilon^{\prime\prime}$ then we will contradict (11). One tricky case we need to handle is the following: while each of these non-negligible co-ordinates of $x^{T}C$ will give rise to a large rank-$1$ term, they can be canceled out by combinations of the rank-$1$ terms corresponding to entries of $x^{T}C$ which are slightly smaller than $\varepsilon^{\prime\prime}$. Hence, we will also set a smaller threshold $\delta$ and first handle the case when there are many co-ordinates in $x^{T}C$ which are larger than $\delta$. $\delta$ is chosen so that the terms with $(x^{T}C)_{i}<\delta$ can not cancel out any of the large terms ($(x^{T}C)_{i}\geq\varepsilon^{\prime\prime}$).

Define $S_{1}=\{i:|(x^{T}C)_{i}|>\varepsilon^{\prime\prime}\}$ and $S_{2}=\{i:|(x^{T}C)_{i}|>\delta\}$, where $\delta=\varepsilon^{\prime\prime}/\vartheta$ for some error polynomial $\vartheta=2R^{2}\rho_{A}\rho_{B}\rho_{C}\rho_{A}^{\prime}\rho_{B}^{\prime}\rho_{C}^{\prime}\tau_{A}\tau_{B}\tau_{C}$ (which is always $>1$). Thus we have $S_{1}\subseteq S_{2}$. We consider two cases.

In this case we will give a lower bound on $\sigma_{R-k_{C}+2}(M)$, which gives a contradiction to (11). The intuition is roughly that $A,B$ have $k_{A},k_{B}$ large singular values, and thus the product should have enough large ones as well. To formalize this, we use the following well-known fact about singular values of products, which is proved by considering the variational characterization of singular values:

Thus we only need to show the two inequalities above. The latter is easy, because by the hypothesis we have $2R+2-k_{B}-k_{C}\leq k_{A}$, and we know that $\sigma_{k_{A}}(A)\geq 1/\tau_{A}$, by the definition of $\text{K-rank}_{\tau_{A}}(A)$. Thus it remains to prove the second inequality. To see this, let $J\subset S_{2}$ of size $k_{B}$. Let $B^{T}_{J}$ and $Q_{J}$ be the submatrices of $B^{T}$ and $Q$ restricted to rows of $J$. Thus we have $Q_{J}=\text{diag}(\alpha)_{J}B^{T}_{J}$. Because of the Kruskal condition, every $k_{B}$ sized sub matrix of $B$ is well-conditioned, and thus $\sigma_{k_{B}}(B_{J})=\sigma_{k_{B}}(B^{T}_{J})\geq 1/\tau_{B}$.

Finally, since $Q$ is essentially $Q_{J}$ along with additional rows, we have $\sigma_{\tau_{B}}(Q)\geq\sigma_{\tau_{B}}(Q_{J})\geq\delta/\tau_{B}$. From the argument earlier, we obtain a contradiction in this case.

Roughly, by defining $S_{1},S_{2}$, we have divided the coefficients $\alpha_{i}$ into large ($\geq\varepsilon^{\prime\prime}$), small, and tiny ($<\delta$). In this case, we have that the number of large and small terms together (in $M$, see Eq. (10)) is at most $k_{B}$. For contradiction, we can assume the number of large ones is $\geq t+1$, since we are done otherwise. The aim is to now prove that this implies a lower bound on $\sigma_{t+1}(M)$, which gives a contradiction to Eq. (11).

Now let us define $M^{\prime}=\sum_{i\in S_{2}}\alpha_{i}(A_{i}\otimes B_{i})$. Thus $M$ and $M^{\prime}$ are equal up to tiny terms. Further, let $\Pi$ be the matrix which projects a vector onto the span of $\{B_{i}^{\prime}~{}:~{}|\beta_{i}|\geq\varepsilon^{\prime}\}$, i.e., the span of the columns of $B^{\prime}$ which correspond to $|\beta_{i}|\geq\varepsilon^{\prime}$. Because there are at most $t$ such $\beta_{i}$, this is a space of dimension $\leq t$. Thus we can rewrite Eq. (10) as

where we assumed w.l.o.g. that $|\beta_{i}|\geq\varepsilon^{\prime}$ for $i\in[t]$, and $Err$ is an error matrix of Frobenius norm at most $\varepsilon+R(\rho_{A}\rho_{B}\delta+\rho_{A}^{\prime}\rho_{B}^{\prime}\varepsilon^{\prime})\leq\varepsilon+(R\rho_{A}\rho_{B}\rho_{A}^{\prime}\rho_{B}^{\prime})(\delta+\varepsilon^{\prime})$.

Now because $|S_{1}|\geq t+1$, and $\text{K-rank}_{\tau_{B}}(B)\geq k_{B}\geq t+1$, there must be one vector among the $B_{i}$, $i\in S_{1}$, which has a reasonably large projection orthogonal to the span above, i.e., which satisfies

Let us pick a unit vector $y$ along $B_{i}-\Pi B_{i}$. Consider the equality (13) and multiply by $y$ on both sides. We obtain

Thus we have a combination of the $A_{i}$’s, with at least one coefficient being $>\varepsilon^{\prime\prime}/(R\tau_{B})$, having a magnitude at most $\left\|(Err)y\right\|_{2}<\vartheta_{1}(\delta+\varepsilon^{\prime}+\varepsilon)$, where $\vartheta_{1}$ was specified above. Now $k_{A}\geq k_{B}\geq|S_{2}|$. So, we obtain a contradiction by Lemma A.1 since:

The last inequality follows because $\vartheta=2R^{2}\rho_{A}\rho_{B}\rho_{C}\rho_{A}^{\prime}\rho_{B}^{\prime}\rho_{C}^{\prime}\tau_{A}\tau_{B}\tau_{C}$. This completes the proof in this case, hence concluding the proof of the lemma. ∎

The next lemma uses the above to conclude that $\text{K-rank}_{\vartheta\tau}(C^{\prime})\geq\text{K-rank}_{\tau}(C)$, for some polynomial $\vartheta$.

Let $A,B,C,A^{\prime},B^{\prime},C^{\prime}$ be as in the setting of Theorem 2.6. Suppose $[A~{}B~{}C]=_{\varepsilon}[A^{\prime}~{}B^{\prime}~{}C^{\prime}]$, with

Then $A^{\prime},B^{\prime},C^{\prime}$ have $\text{K-rank}_{\tau^{\prime}}$ to be at least $k_{A},k_{B},k_{C}$ respectively, where $\tau^{\prime}:=\vartheta_{\ref{lem:conditioned}}$.

The lemma implies that if $T$ has a well-conditioned decomposition which satisfies the Kruskal conditions, then any other bounded decomposition which is a sufficiently good approximation should also be reasonably well-conditioned. Further, it says that the decomposition $[A^{\prime}~{}B^{\prime}~{}C^{\prime}]$ can not be of rank $<R$. Otherwise, we could add some zero-columns to each of $A^{\prime},B^{\prime},C^{\prime}$ and apply this lemma to conclude K-rank of $A^{\prime}$ is $\geq 2$, a contradiction if there exists a zero column.

By symmetry, let us just show this for matrix $C^{\prime}$ (dimensions $n\times R$), and let $k=k_{C}$ for convenience. We need to show that every $n$-by-$k$ submatrix of $C^{\prime}$ has minimum singular value $\geq\delta=1/\tau^{\prime}_{C}$.

For contradiction let $C^{\prime}_{S}$ be the submatrix corresponding to the columns in $S$ ($|S|=k$), such that $\sigma_{k}(C^{\prime}_{S})<\delta$. Let us consider a left singular vector $z$ which corresponds to $\sigma_{k}(C^{\prime}_{S})$, and suppose $z$ is normalized to be unit length. Then we have

Thus $|\left\langle z,C^{\prime}_{i}\right\rangle|<\delta$ for all $i\in S$, so we have $nz_{\delta}(z^{T}C^{\prime})\leq n-k$. Now from Lemma 3.2, we have

Let $J$ denote the set of indices in $z^{T}C$ which are $<\varepsilon_{1}$ in magnitude (by the above, we have $|J|\geq k$). Thus we have $\left\|zC_{J}\right\|_{2}<R\varepsilon_{1}$, which leads to a contradiction if we have $\text{K-rank}_{1/(R\varepsilon_{1})}(C)\geq k$.

Since this is true for our choice of parameters, the claim follows. ∎

Once we have the lemmas above, let us check that the conditions of the robust permutation lemma hold with $C^{\prime},C$ taking the roles of $X,Y$ in Lemma 3.1, and $k=k_{C}$, and $\tau=\vartheta_{\ref{lem:conditioned}}\cdot\tau_{C}$. From Lemma 3.4, it follows that $\text{K-rank}_{\tau}(C)$ and $\text{K-rank}_{\tau}(C^{\prime})$ are both $\geq k$, and setting $\varepsilon^{\prime}=0$ in Lemma 3.2, the other condition of Lemma 3.1 holds. Thus we can conclude that there exists a permutation matrix $\Pi_{C}$ and a diagonal matrix of scalars $\Lambda_{C}$ such that $\left\|C^{\prime}-C\Pi_{C}\Lambda_{C}\right\|_{F}$ is small. We will see the quantitative details in what follows.

2 Wrapping up the proof

We are now ready to complete the robust Kruskal’s theorem. From what we saw above, the main part that remains is to prove that the permutations in the various dimensions are equal.

Suppose we are given an $\varepsilon^{\prime}<1$ as in the statement of the theorem. For a moment, suppose $\varepsilon$ is small enough, and $A,B,C,A^{\prime},B^{\prime},C^{\prime}$ satisfying the conditions of the theorem produce tensors which are $\varepsilon$-close.

From the hypothesis, note that $k_{A},k_{B},k_{C}\geq 2$ (since $k_{A},k_{B},k_{C}\leq R$, and $k_{A}+k_{B}+k_{C}\geq 2R+2$). Thus from the Lemmas 3.4 and 3.2 (setting $\varepsilon^{\prime}=0$), we obtain that $C,C^{\prime}$ satisfy the hypothesis of the Robust permutation lemma (Lemma 3.1) with $C^{\prime},C$ set to $X,Y$ respectively, and the parameters

Hence, we apply Lemma 3.1 to $A$,$B$ and $C$, and get that there exists permutation matrices $\Pi_{A}$, $\Pi_{B}$ and $\Pi_{C}$ and scalar matrix $\Lambda_{A},\Lambda_{B},\Lambda_{C}$ such that for $\varepsilon_{2}=\vartheta_{\ref{lem:permutation-poly}}\vartheta_{\ref{lem:perm:conditions}}\cdot\varepsilon$,

We now need to prove that these three permutations are in fact identical, and that the scalings multiply to the identity (up to small error).

Let us assume for contradiction that $\Pi_{A}\neq\Pi_{B}$. We will use an index where the permutations disagree to obtain a contradiction to the assumptions on the K-rank .

For notational convenience, let $\pi_{A}:[R]\rightarrow[R]$ correspond to the permutation given by $\Pi_{A}$, with $\pi_{A}(r)$ being the column that $A^{\prime}_{r}$ maps to. Permutation $\pi_{B}:[R]\rightarrow[R]$ similarly corresponds to $\Pi_{B}$. Using (14) for $A$ we have

By a similar argument, and using triangle inequality ( along with $\varepsilon_{2}\leq 1\leq\rho^{\prime}_{B}$) we get

Let us take linear combinations given by unit vectors $v$ and $w$, of the given tensor $T=[A~{}B~{}C]$ along the first and second dimensions. By combining the above inequality along with the fact that the two decompositions are $\varepsilon$-close i.e. $\left\|\sum_{r\in[R]}A_{r}\otimes B_{r}\otimes C_{r}-A^{\prime}_{r}\otimes B^{\prime}_{r}\otimes C^{\prime}_{r}\right\|_{F}\leq\varepsilon$, we have

Note that the $\varepsilon$ term above is negligible compared to the second term involving $\varepsilon_{2}$. We know that $\pi_{A}\neq\pi_{B}$, so there exist $s\neq t\in[R]$ such that $r^{*}=\pi_{A}(s)=\pi_{B}(t)$. We will now use this $r^{*}$ to pick $v$ and $w$ carefully so that the vector $Z^{\prime}$ is negligible while $Z$ is large. We partition $[R]$ into $V,W$ with $|V|=k_{A}-1$ and $|W|\leq k_{B}-1$, so that $\pi_{A}(t)\in V$ and $\pi_{B}(s)\in W$ and for each $r\in[R]-\{s,t\}$, either $\pi_{A}(r)\in V$ or $\pi_{B}(r)\in W$. Such a partitioning is possible since $R\leq k_{A}+k_{B}-2$.

Let ${\cal{V}}=\operatorname{span}(V)$ and ${\cal{W}}=\operatorname{span}(W)$. We know that $r^{*}=\pi_{A}(s)\notin S$ and $r^{*}=\pi_{A}(t)\notin T$. Hence, pick $v$ as unit vector along $\Pi^{\perp}_{\cal{V}}A_{r^{*}}$ and $w$ as unit vector along $\Pi^{\perp}_{\cal{W}}B_{r^{*}}$. By this choice, we ensure that $Z^{\prime}=0$ (since $v\perp{\cal{V}}$ and $w\perp{\cal{W}}$).

However, $\text{K-rank}_{\tau_{A}}(A)\geq k_{A}$ and $\text{K-rank}_{\tau_{B}}(B)\geq k_{B}$, so $\left\langle v,A_{r^{*}}\right\rangle\left\langle w,B_{r^{*}}\right\rangle\geq 1/\tau_{A}\tau_{B}$ (by Lemma A.2). Further, $|V|=k_{A}-1$ implies that at most $R-k_{A}+1\leq k_{C}-1$ terms of $Z$ is non-zero.

Further, $|\beta_{r^{*}}|\geq(\tau_{A}\tau_{B})^{-1}$, and since $\text{K-rank}_{\tau_{C}}(C)=k_{C}\geq R-|V|+1$, we have a contradiction if $\varepsilon_{3}<(\tau_{A}\tau_{B}\tau_{C})^{-1}$ due to Lemma A.2. This will be true for our choice of parameters. Hence $\Pi_{A}=\Pi_{B}$, and similarly $\Pi_{A}=\Pi_{C}$. Let us denote $\Pi=\Pi_{A}=\Pi_{B}=\Pi_{C}$. In the remainder, we assume $\Pi$ is the identity, since this is without loss of generality.

To show $\Lambda_{A}\Lambda_{B}\Lambda_{C}=_{\varepsilon^{\prime}}I_{R}$:

Let us denote $\beta_{i}=\lambda_{A}(i)\lambda_{B}(i)\lambda_{C}(i)$. From (14) and triangle inequality, we have as before

Combining this with the fact that the decompositions are $\varepsilon$-close we get

By taking linear combinations given by unit vectors $x,y$ along the first two dimensions (i.e. $xA$ and $yB$) we have

We will show each $\beta_{r}$ is negligible. Since $R+2\leq k_{A}+k_{B}$, let $S,W\subseteq[R]-\{r\}$ be disjoint sets of indices not containing $r$, such that $|S|=k_{A}-1$ and $|W|\leq k_{B}-1$. Let ${\cal{S}}=\operatorname{span}(\{A_{j}:j\in S\})$ and ${\cal{W}}=\operatorname{span}(\{B_{j}:j\in W\})$. Let $x$ and $y$ be unit vectors along $\Pi^{\perp}_{\cal{S}}A_{r}$ and $\Pi^{\perp}_{\cal{W}}B_{r}$ respectively.

Since $\text{K-rank}_{\tau_{A}}(A)\geq k_{A}$ and $\text{K-rank}_{\tau_{B}}(B)\geq k_{B}$, we have that $\left\|\Pi^{\perp}_{\cal{S}}A_{r}\right\|\geq 1/\tau_{A}$ (similarly for $B_{r}$). Hence, from Lemma A.2

Thus, $\left\|\Lambda_{A}\Lambda_{B}\Lambda_{C}-I\right\|\leq\varepsilon_{4}\tau_{A}\tau_{B}\tau_{C}\leq\varepsilon^{\prime}$ (our choice of $\varepsilon$ will ensure this). This implies the theorem.

Let us now set the $\varepsilon$ for the above to hold (note that $\vartheta_{\ref{lem:permutation-poly}}$ involves a $\tau$ term which depends on $\vartheta_{\ref{lem:conditioned}}$)

which can easily be seen to be of the form in the statement of the theorem. This completes the proof. ∎

3 A Robust Permutation Lemma

Let us now prove the robust version of the permutation lemma (Lemma 3.1). Recall that $\text{K-rank}_{\tau}(X)$ and $\text{K-rank}_{\tau}(Y)$ are $\geq k$, and that the matrices $X,Y$ are $n\times R$.

Kruskal’s proof of the permutation lemma proceeds by induction. Roughly, he considers the span of some set of $i$ columns of $X$ (for $i<k$), and proves that there exist at least $i$ columns of $Y$ which lie in this span. The hypothesis of his lemma implies this for $i=k-1$, and the proof proceeds by downward induction. Note that $i=1$ implies for every column of $X$, there is at least one column of $Y$ in its span. Since no two columns of $X$ are parallel, and the number of columns is equal in $X,Y$, there must be precisely one column, and this completes the proof.

A natural way to mimic this proof is to say: for each set of $i$ columns in $X$, there exist a set of at least $i$ columns in $Y$ which are $\varepsilon_{i}$ close to the span of the chosen columns in $X$. The difficulty with this is that we lose a factor of $\tau n$ in each iteration, i.e., if the statement was true for $i+1$ with error $\varepsilon_{i+1}$, it will be true for $i$ with error $\varepsilon_{i}=\tau n\cdot\varepsilon_{i+1}$. This means that to obtain a small error at the end, we should have started off with error $<1/(\tau n)^{k}$, which is exponentially small. Thus we need a more tricky inductive statement and additional observations (including Lemma 3.4) to overcome this issue.

We start by introducing some notation. If $V$ is a matrix and $S$ a subset of the columns, we denote by $\operatorname{span}(V_{S})$ the span of the columns of $V$ indexed by $S$. The next two lemmas are crucial to the analysis.

W.l.o.g., let us suppose $B=\{1,\dots,q\}$. Also, let $x_{j}$ denote the $j$th column of $X$. From the hypothesis, we can write:

where $u_{i}\in\operatorname{span}(X_{A})$ and $z_{i}$ are the error vectors, which by hypothesis satisfy $\left\|z_{i}\right\|_{2}<\varepsilon$. We will use the fact that $|A|+|B|\leq k$ to conclude that each $\alpha_{ij}$ is tiny. This then implies the desired conclusion.

By equating the first and $i$th equations ($i\geq 2$), we obtain

Thus we have a combination of the vectors $x_{i}$ being equal to $z_{i}-z_{1}$, which by hypothesis is small: $\left\|z_{i}-z_{1}\right\|_{2}\leq 2\varepsilon$. Now the key is to observe that the coefficient of $x_{i}$ is precisely $\alpha_{1i}$, because it is zero in the $i$th equation. Thus by Lemma A.1 (since $\text{K-rank}_{\tau}(X)\geq k$), we have that $|\alpha_{1i}|\leq 2\tau\varepsilon$.

Since we have this for all $i$, we can use the first equation to conclude that

The last inequality is because $q<n$, and this completes the proof. ∎

A counting argument lies at the core of the inductive proof. We present it in terms of sunflower set systems, since it allows for a clean presentation.

A set system ${\cal{F}}$ is said to be a “sunflower on $[R]$ with core $T^{*}$” if ${\cal{F}}\subseteq 2^{[R]}$, and for any $F_{1},F_{2}\in\cal{F}$, we have $F_{1}\cap F_{2}\in T^{*}$.

Let $\{T_{1},T_{2},\dots,T_{q}\}$, $q\geq 2$, be a sunflower on $[R]$ with core $T^{*}$, and suppose $|T_{1}|+|T_{2}|+\dots+|T_{q}|\geq R+(q-1)\theta$, for some $\theta$. Then we have $|T^{*}|\geq\theta$, and furthermore, equality occurs iff $T^{*}\subseteq T_{i}$ for all $1\leq i\leq q$.

The proof is by a counting argument. By the sunflower structure, each $T_{i}$ has some intersection with $T^{*}$, and some elements which do not belong to $T_{i^{\prime}}$ for any $i^{\prime}\neq i$. Call the number of elements of the latter kind $t_{i}$. Then we must have

Now since all $T_{i}\subseteq[R]$, we have

as desired. For equality to occur, we must have equality in each of the places above, in particular, we must have $|T_{i}\cap T^{*}|=|T^{*}|$ for all $i$, which implies $T^{*}\subseteq T_{i}$ for all $i$. ∎

Finally, we introduce a bit more notation before getting to the proof. For $S\subseteq[R]$ of size $(k-1)$, we define $T_{S}$ to be the set of indices corresponding to columns of $Y$ which are $\varepsilon_{1}$-close to $\operatorname{span}(X_{S})$, where $\varepsilon_{1}:=(nR)\varepsilon$, and $\varepsilon$ is as defined in the statement of Lemma 3.1. For smaller sets $S$, we define:

With the above lemmas in place, we can prove Lemma 3.1.

We first prove the following claim by induction:

Claim. For every $S\subseteq[R]$ of size $\leq(k-1)$, we have $|T_{S}|=|S|$.