An Algorithmic Proof of Kruskal’s Tensor Decomposition Theorem

Bhargava, Vishwas; Schulman, Leonard J.; Sivan, Shiri

doi:10.4230/LIPIcs.ICALP.2026.31

An Algorithmic Proof of Kruskal’s Tensor Decomposition Theorem

Vishwas Bhargava

Department of Computer Science and Engineering, IIT Bombay, Mumbai, India Leonard J. Schulman

Department of Computing and Mathematical Sciences, Caltech, Pasadena, CA, USA Shiri Sivan

Department of Computing and Mathematical Sciences, Caltech, Pasadena, CA, USA

Abstract

A famous theorem of Kruskal gives the simplest and arguably most fundamental criterion under which a tensor is guaranteed a unique minimum-rank decomposition. Kruskal’s condition requires that the sum of the Kruskal ranks $\{k_{i}\}_{i=1}^{m}$ of the components satisfies $\sum_{i\in[m]}k_{i}\geq 2r+m-1$ , where $r$ denotes the rank and $m$ the order of the tensor. However, Kruskal’s original proof and subsequent simplifications/generalizations have remained non-constructive. With the sole exception of the case $(k_{1}=r,k_{2}=r,k_{3}=2)$ , attributed to Jennrich – no algorithm has been established for decomposing tensors under the Kruskal condition without additional assumptions. In fact, whether there exists an efficient algorithm for decomposing a tensor under the Kruskal condition was explicitly posed as an open problem in the work of Bhaskara et al. (COLT 2014). Even slight variations of the Jennrich special case, such as the $(r,r-1,3)$ case, have remained algorithmically open; specifically, no sub-exponential time bound was known.

In this work, we make progress on this problem by giving an elementary, constructive proof of Kruskal’s Theorem for general $m$ -way tensors. Concretely, we give a randomized algorithm that decomposes any tensor satisfying the Kruskal condition by utilizing random projections to map the problem into a geometry of intersecting hyperplanes via a MinRank instance. Specifically for $3$ -way tensors satisfying $k_{1}+k_{2}+k_{3}=2r+2$ , the algorithm achieves a runtime of $n^{O(k)}$ where $k=\min(k_{1},k_{2},k_{3})$ . Thus, we extend smoothly beyond the Jennrich special case, achieving polynomial-time complexity for any family of tensors that satisfies the Kruskal condition, provided the least Kruskal rank is bounded.

Keywords and phrases:

Tensor decomposition, Kruskal’s theorem, tensor rank, MinRank, algebraic algorithms

Category:

Track A: Algorithms, Complexity and Games

Funding:

Vishwas Bhargava: Part of this work was done when the author was a postdoc at Caltech, supported by Prof. Christopher Umans’ Simons Foundation award.

Leonard J. Schulman: Supported in part by NSF CCF-2321079.

Shiri Sivan: Supported in part by NSF CCF-2321079.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Algebraic complexity theory ; Theory of computation

\rightarrow

Design and analysis of algorithms

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Tensor decomposition is a fundamental tool for modern science, with applications ranging from machine learning and statistics to signal processing and computational complexity. In a nutshell, tensors are multi-dimensional arrays with entries from a field $\mathbb{F}$ . For instance, a 3-dimensional (or 3-way or 3-mode) tensor can be written as $\mathcal{T}=(\alpha_{i,j,k})\in\mathbb{F}^{n_{1}\times n_{2}\times n_{3}}$ .

A tensor $T\in\mathbb{F}^{n_{1}\times\dots\times n_{m}}$ can always be written as the sum of rank $1$ tensors; such an expression is known as a tensor decomposition.¹¹1Also known as the CANDECOMP/PARAFAC (CP) decomposition. Here, a rank 1 tensor over a field $\mathbb{F}$ is the outer product of $m$ nonzero vectors, written as

v_{1}\otimes v_{2}\otimes...\otimes v_{m}\in\mathbb{F}^{n_{1}\times n_{2}% \times\cdots\times n_{m}}.

If the decomposition consists of $r$ summands, it is called an $r$ -decomposition. The minimal $r$ for which there exists an $r$ -decomposition is defined as the tensor rank of $T$ , and such a decomposition is then referred to as a rank decomposition.

When $T$ has a decomposition

T=\sum_{t=1}^{r}v_{t}^{(1)}\otimes v_{t}^{(2)}\otimes\cdots\otimes v_{t}^{(m)},

we define the components as, for each $i\in[m]$ , the matrix with columns $v_{t}^{(i)}$ $(t=1,\ldots,r)$ :

V^{(i)}=[v_{1}^{(i)},v_{2}^{(i)},\dots,v_{r}^{(i)}]\in\mathbb{R}^{n_{i}\times r}

The vector space containing $v_{t}^{(i)}$ will be referred to as the $i$ ’th mode of the tensor. We also employ the shorthand notation

T=\llbracket V^{(1)},V^{(2)},\dots,V^{(m)}\rrbracket.

A primary reason for the wide applicability of tensors is that their rank decomposition can be unique (also known as identifiable), a property that matrices (unless of rank 1) lack. The motivations for identifiability in data analysis (beginning at least with work of the psychologist Spearman on tests of intelligence [28]) are abundantly discussed in many references e.g., [6, 12, 24]. We refer the interested reader to these works and the references therein.

The most celebrated criterion for uniqueness of tensor decomposition was given by Kruskal in 1977 [19] (and see [17, 18]). The Kruskal rank (or $k$ -rank) of a matrix is the maximum integer $k$ such that every subset of $k$ columns is linearly independent. Clearly, $k$ -rank $\leq$ rank. Kruskal’s uniqueness theorem states that if a tensor $T$ has an $r$ -decomposition $\llbracket V^{(1)},\dots,V^{(m)}\rrbracket$ , and the $k$ -ranks of the components satisfy

\sum_{i=1}^{m}k_{V^{(i)}}\geq 2r+m-1,

(1)

then $\operatorname{rank}(T)=r$ and the decomposition is unique up to permutation and scaling of the columns (going forward we omit the “up to scaling and permutation”). The inequality in (1) is the Kruskal Condition.

While the theorem guarantees that a unique decomposition exists, the original proof and subsequent simplifications (e.g., [29, 25, 21]) are existential rather than constructive. This limitation is widely recognized. The question of whether there is a hardness result for tensor decomposition, or conversely, whether there exists an efficient (polynomial-time) algorithm for decomposing a tensor under the general conditions of Kruskal’s uniqueness theorem – and whether there is an algorithmic proof of the theorem itself – was explicitly posed as a major open problem in COLT 2014 by Bhaskara et al. [5], carrying a $100 reward.

It is important to note that while the tensor rank problem (and therefore also the problem of finding a decomposition of specified rank) is NP-hard, it remains unknown whether this hardness persists when the input tensor is promised to satisfy the Kruskal condition. The only significant special case of the Kruskal condition in which an efficient algorithm is known is the case that is due (prior to Kruskal’s work) to Jennrich, in which two of the components are invertible ( $k_{1}=k_{2}=r$ ) while the third has Kruskal rank at least $2$ . Even this restricted case has found surprisingly many applications in computer science and statistics. However, even a slight variation, such as the $(r,r-1,3)$ case, has, to the best of our knowledge, remained algorithmically open. This was the original motivation for our work.

1.1 Our contribution

We give the first algorithmic proof of the Kruskal theorem. Rather than relying on an existential argument, we use structural implications of the Kruskal condition to recover the components directly. For ease of presentation, we state our results over the real field $\mathbb{R}$ . Our algorithm and its runtime guarantee is stated in the Real RAM model, where arithmetic over the reals is exact and unit cost. However, the algorithm can be easily implemented over the rationals using standard Turing machines. That is, if the unknown decomposition is in fact rational, then our algorithm can work entirely over the rationals. There is a known polynomial-time reduction (in the input size $\prod n_{i}$ ) that converts an $m$ -way tensor satisfying the Kruskal condition into a 3-way tensor that also satisfies the Kruskal condition (see Theorem 3 in [27] or Lemma 24 in the Appendix).²²2Lemma 24 proves that every Kruskal $m$ -mode tensor has a Kruskal 3-reshaping. Polynomial-time follows from the fact that the number of ways to reshape the tensor is polynomial in the input size. Consequently, we focus our analysis on the 3-way case.

As our objective is to design a decomposition algorithm for Kruskal tensors, we assume $T$ satisfies the Kruskal condition:

k_{1}+k_{2}+k_{3}\geq 2r+2.

We set $k:=2r+2-\max\{k_{1}+k_{2},k_{1}+k_{3},k_{2}+k_{3}\}$ . This value governs both the time complexity and the core technical arguments of our algorithm.

Theorem 1 (Algorithmic Kruskal for 3-tensors).

Let $\mathcal{T}\in\mathbb{R}^{n_{1}\times n_{2}\times n_{3}}$ be a tensor with a decomposition $\mathcal{T}=\sum_{i=1}^{r}u_{i}\otimes v_{i}\otimes w_{i}$ such that the components have Kruskal ranks respectively $k_{1},k_{2},k_{3}$ satisfying the Kruskal condition $k_{1}+k_{2}+k_{3}\geq 2r+2$ . Then there exists a randomized algorithm that recovers the components in $(n_{1}+n_{2}+n_{3})^{O(k)}$ time with high probability.

By definition, $k\leq\min\{k_{1},k_{2},k_{3}\}$ . If the Kruskal condition holds with some slack (i.e., $\sum k_{i}>2r+2$ ), we can effectively replace the smallest Kruskal rank with this smaller value $k$ that saturates the bound. For example, if all Kruskal ranks are $r$ , then $k=2$ .

Our work settles the request of Bhaskara et al. [5] for an algorithmic proof of the Kruskal theorem, and makes substantial progress on the efficiency question without fully settling it: we provide a time complexity upper bound for decomposing Kruskal tensors that scales exponentially with respect to the minimum Kruskal rank of the modes. Notably, for (previously open) instances “close” to the Jennrich case – such as the $(r,r-p,p+2)$ regime for fixed $p$ – our algorithm is polynomial in the input size. By contrast, the best existing method, the brute-force approach of reducing the decomposition to an algebraic system, will typically require $\exp{(nr)}$ time for $n=\max n_{i}$ due to the $n r$ unknowns involved.

We should mention that in the $m$ -to- $3$ reduction alluded to above, the initial $m$ -way tensor does not strictly need to satisfy the Kruskal condition; it is sufficient that it should reduce to a 3-way instance which does. The reduction is achieved by “clubbing” various modes together through Khatri-Rao products – a standard reshaping technique in the literature. (For the $m$ -to- $3$ reduction see [27, 22, 8], or Sections 5 and A.) By partitioning the modes into sets $I,J,\text{ and }L$ such that the resulting reshaped tensor satisfies the 3-way Kruskal criteria, we effectively provide a constructive proof for the more general Reshaped Kruskal Theorem.

Theorem 2 (Reshaped Kruskal Theorem).

Consider an $m$ -way tensor $\mathcal{T}$ with an $r$ -rank decomposition $\llbracket V^{(1)},\dots,V^{(m)}\rrbracket$ . If there exists a partition of the modes $I\sqcup J\sqcup L=[m]$ such that the Kruskal ranks of the partitioned (Khatri-Rao) matrices satisfy:

k_{I}+k_{J}+k_{L}\geq 2r+2

then $\operatorname{rank}(\mathcal{T})=r$ and the decomposition is unique. Furthermore, there exists a randomized algorithm that recovers the components in $N^{O(k)}$ time with high probability, where $N$ is the input size, and $k:=2r+2-\max\{k_{I}+k_{J},k_{I}+k_{L},k_{J}+k_{L}\}$ .

1.2 Related Work

Tensor decomposition is a highly active area of research with many fundamental open problems and landmark results. Here, we mention some of these results with a focus on the identifiability and computational complexity of the problem (and omitting entirely the extensive literature in algebraic complexity theory).

On identifiability, the work of Lovitz and Petrov [22] provides an elegant generalization of Kruskal’s theorem using ideas from matroid theory. It is not clear whether our method can be extended to their generalization.

On the complexity and algorithmic side, determining tensor rank is famously NP-hard [13, 14]. Consequently, one cannot expect efficient algorithms to determine rank or find decompositions for general input tensors. The Kruskal framework is the least restrictive in which hardness is not known. The Kruskal condition is also tight [10]. From this point of view our result is a worst-case tensor decomposition algorithm, unlike “generic” uniqueness or decomposition theorems. Indeed, most research on tensor decomposition algorithms has focused on tensors with additional non-degeneracy conditions; tensors drawn from specific distributions; or heuristic approaches. We discuss some of these results now, moving from no assumptions to progressively adding more structure; as we will see, the assumptions have a tremendous effect on the rank parameters we can efficiently decompose.

In the worst-case setting for 3-dimensional tensors, one essentially cannot outperform brute force, which involves solving systems over the base field. Formally, Schaefer and Stefankovic [26] showed that for any field $\mathbb{F}$ , given a system $S$ of algebraic equations over $\mathbb{F}$ , we can in polynomial time construct a 3-dimensional tensor $\mathcal{T}_{S}$ (with a linear blowup) and an integer $k$ such that $S$ has a solution in $\mathbb{F}$ if and only if $\mathcal{T}_{S}$ has rank at most $k$ over $\mathbb{F}$ . However, for higher $m$ -dimensional tensors, there exists an FPT-style worst-case algorithm with $2^{r^{O(1)}}\mathrm{poly}(n,m)$ runtime [4]. The next level is the generic setting, where the input tensor can be anything barring a (result-specific) lower-dimensional algebraic variety. For generic tensors, Chiantini and Ottaviani [7] prove the uniqueness of decomposition up to rank $\frac{(n_{1}-1)(n_{2}-1)(n_{3}-1)+1}{n_{1}+n_{2}+n_{3}-2}$ . Again in the generic setting, Kothari et al. [16] recently provided an efficient decomposition algorithm for families of tensors with rank approaching $2n$ . Adding even more structure (and moving towards applications), one has the average-case setting; for instance, Ma et al. [23] deployed techniques from the Sum-of-Squares hierarchy to reach rank $\tilde{O}(n^{1.5})$ for tensors drawn from Gaussian decomposition.

2 Proof Overview

We focus our analysis on 3-way tensors, as decomposition of $m$ -way tensors can be reduced in a standard fashion to the 3-way case through the reshaping procedure alluded to in Section 1.1. Let $T\in\mathbb{R}^{n_{1}\times n_{2}\times n_{3}}$ be a tensor that satisfies the Kruskal condition $k_{1}+k_{2}+k_{3}\geq 2r+2$ , and has a decomposition $T=\sum_{j=1}^{r}u_{j}\otimes v_{j}\otimes w_{j}$ . Since part of our goal is to reprove the Kruskal theorem, we shall not assume that this decomposition is unique. As per our notation, we define components $U=[u_{1},\dots,u_{r}]\in\mathbb{R}^{n_{1}\times r}$ , $V=[v_{1},\dots,v_{r}]\in\mathbb{R}^{n_{2}\times r}$ , and $W=[w_{1},\dots,w_{r}]\in\mathbb{R}^{n_{3}\times r}$ .

We start by recovering a single component, say $V$ . Towards this end, we turn to a geometric point of view. Namely, we complete an equivalent task: recovering the $r$ hyperplanes orthogonal to the columns of $V$ . This task is completed in two steps. First we identify all the intersection points of the hyperplanes (collectively these form a zero-dimensional variety); then we reconstruct the hyperplane arrangement, given the intersection points. We refer to the combination of these two steps as the identifiability test, as this test establishes the identifiability of the (projected) component $V$ .

Both steps require that the hyperplane arrangement lie in general position, meaning the intersection of any $t$ hyperplanes has dimension $\max\{d-t,0\}$ . Conveniently, this can be accomplished with probability 1 via a random projection (see Lemma 13).

The identifiability test

To identify the intersection points, we construct a MinRank instance³³3The MinRank search problem is the task of finding a linear combination of given matrices $M_{1},\dots,M_{n}$ that minimizes the rank of the resulting matrix. See e.g., [11, 1] whose solutions correspond precisely to the aforementioned intersection points. Let $T^{\prime}=T\times_{2}A=\llbracket U,AV,W\rrbracket$ be the projected tensor, where $A\in\mathbb{R}^{k_{2}\times n_{2}}$ is a random matrix ( $\times_{i}A$ means that the $i$ -th mode of the tensor is contracted against the rows of matrix $A$ ). For variables $z=(z_{1},\dots,z_{d})$ where $d=k_{2}-1$ , and $[z,1]$ is the vector $(z_{1},\dots,z_{d},1)$ , we define the $V$ -mode contraction:

M(z)=T^{\prime}\times_{2}[z,1]=U\mathrm{Diag}([z,1]AV)W^{T}.

(2)

In words, $M(z)$ is the linear combination of 2nd mode slices associated with coefficients $[z,1]$ . Under the Kruskal condition, we show that for all $z\in\mathbb{R}^{d}$ , $\text{rank}(M(z))\geq r-d$ . Crucially, we prove that the matrix $M(z)$ achieves this minimum rank $r-d$ if and only if $[z,1]AV$ has exactly $d$ zeros.

We only look at slice combinations of the form $[z,1]$ because fixing the last entry ensures that $d$ -intersections are 0-dimensional (points). A more subtle reason for this choice is the projective nature of tensor decomposition; since we can scale components freely, we have the freedom to look for one fewer variable in the search for these hyperplanes.

Geometrically, this implies that the minimizers of $\text{rank }M(z)$ are precisely the $d$ -wise intersection points of the hyperplanes defined by the columns of the projected component $A V$ (see Theorem 14). This already is a significant step toward identifiability, as the matrix $M(z)$ depends solely on the observable tensor rather than the hidden decomposition itself. We are essentially reducing tensor decomposition to the search problem associated with MinRank. We denote

\mathrm{MinRank}(M(z),\ell)=\min_{z\in\mathbb{R}^{\ell-1}}\mathrm{rank}(M(z)),

(3)

where $M(y):=W\mathrm{Diag}([y,1]AV)W^{T}$ for a random $A\in\mathbb{R}^{\ell\times n_{v}}$ .⁴⁴4The parameter $\ell$ is the number of matrices in the MinRank instance, since $M(z)$ is a sum of the matrices $\{W\mathrm{Diag}(a_{i}^{*}V)W^{T}\}_{i\in[\ell]}$ , where $a_{i}^{*}$ denotes the $i$ -th row of $A$ .

It is a geometric fact that the set of $d$ -wise intersection points of an arrangement of hyperplanes in general position in $\mathbb{R}^{d}$ , determine those hyperplanes; and in addition, the hyperplanes can be efficiently computed from the intersection points. This allows us to reconstruct the matrix $A V$ (see Algorithm HP-reconstruction and Lemma 17).

The identifiability test is the heart of our algorithmic proof of Kruskal’s Theorem. Establishing the uniqueness of the projected component $A V$ via this test effectively reduces the problem to the Jennrich setting, where uniqueness is well-understood and efficient decomposition applies (see Lemma 18). With $U$ and $W$ at our disposal, the identifiability of the original $V$ follows.

The tensor decomposition algorithm

Our decomposition algorithm, sketched below, is directly based on the ideas we discussed above for identifiability. For convenience, at each step we link to the text for more details.

Algorithm 1 Rank decomposition algorithm for 3-way tensors (outline).

Input: $T\in\mathbb{R}^{n_{1}\times n_{2}\times n_{3}}$ .

For $k^{\prime}=2,3,...,\min\{n_{1},n_{2},n_{3}\}$ :

For $i=1,2,3$ :
1. 1.
  
  Apply a random projection $A\in\mathbb{R}^{k^{\prime}\times n_{i}}$ on the $i$ -th mode (Step 1).
2. 2.
  
  Generate $M(z)=$ the formal linear combination of mode- $i$ slices with coefficients $(z_{1},...,z_{k^{\prime}-1},1)$ (Step 2).
3. 3.
  Solve $\textsc{MinRank}(M(z),k^{\prime})$ . (Step 3)
  1. (a)
    
    Denote the solution $m$ . (see Equation 3 for the definition of MinRank)
  2. (b)
    
    Calculate the minimizers $\mathcal{S}=\{z\in\mathbb{R}^{k^{\prime}-1}|\;\operatorname{rank}M(z)=m\}$ .
  3. (c)
    
    Set $r^{\prime}=m+k^{\prime}-1$ .
4. 4.
  
  Reconstruct $AV^{(i)}$ (Step 4).
5. 5.
  
  Restore the two other components $V^{(j)},V^{(\ell)}$ (Step 5).
6. 6.
  
  Recover $V^{(i)}$ (Step 6).
7. 7.
  
  If $T=\llbracket V^{(1)},V^{(2)},V^{(3)}\rrbracket$ , output the decomposition.

Output fail.

We employ randomness in Steps 1, 3 and 4. The successful event in Step 1 occurs with probability 1 (see Lemma 25), whereas the randomness in Steps 3 and 4 is utilized solely in sake of computational efficiency and does not affect the uniqueness argument. Concretely, each randomized step admits a deterministic alternative: the random projection can be replaced by going over a sufficiently large grid (by Schwartz-Zippel); the system solving step (and thus MinRank) can be performed deterministically (for instance using the algorithm of Ierardi [15]); and the hyperplane reconstruction can be performed via the deterministic brute-force strategy described in Section 4.2 (specifically, Lemma 16 and the subsequent discussion).⁵⁵5The deterministic version can be implemented in $r^{O(d^{2})}$ time, compared to $r^{O(d)}$ for the randomized version. Thus the algorithm can in principle be made fully deterministic, and its output depends only on the input tensor – not on any random choices.

Thus, the algorithm’s output is uniquely determined for each $i$ and $k^{\prime}$ . It only remains to show that different parameter values cannot result in distinct decompositions. Towards this end, we prove the existence of fixed parameters $k$ and $i$ , determined solely by $T$ , for which the recovery algorithm is guaranteed to succeed. Specifically, if $T$ admits a rank decomposition satisfying the Kruskal condition, the algorithm – called on these parameters – is guaranteed to recover the constituent components. Because the algorithm is deterministic, it maps the tensor $T$ to a unique set of factors (up to scaling and permutation). If two distinct decompositions were to exist, both would necessarily be recovered as the same output by this deterministic procedure, which is a contradiction. Consequently, the decomposition is unique.

This parameter $k$ is defined by

k:=2r+2-\max\{k_{1}+k_{2},k_{1}+k_{3},k_{2}+k_{3}\},

and the corresponding $i$ is the mode of minimal Kruskal rank. That is, $k\leq k_{i}=\min\{k_{1},k_{2},k_{3}\}$ . ⁶⁶6 $(k,i)$ are not the only parameters on which the algorithm is guaranteed to succeed. However, for uniqueness we only need one set of parameters that succeed on all decompositions. Computationally, the choice $(k,i)$ delivers the best time complexity.

Since we do not know the tensor rank and Kruskal ranks we iterate over different $k$ guesses in the outermost loop of the algorithm. The correctness of the algorithm, as well as the uniqueness of the decomposition, rely on the following facts:

1.

If an $r$ -decomposition satisfies the Kruskal condition, then the tensor has rank $r$ and every rank decomposition has the same Kruskal ranks and thus $k$ (see Lemma 19).
2.

At iterations $k^{\prime}<k$ , the decomposition algorithm does not output a “redundant” decomposition, i.e., an $r^{\prime}$ -decomposition with $r^{\prime}>r$ (see Lemma 20).
3.

At iteration $k$ , the algorithm outputs a (unique) $r$ -decomposition (see Theorem 21).

The proofs of facts 1 and 2 are provided in Section 4, while an overview of the 3rd fact follows below. For technical details regarding the subroutines, time complexity, and success probability, see Section 4.

For fact 3, we now “walk” through iteration $(k,i)$ of the algorithm, assuming the success event occurs at every step of the algorithm.

Step 1. Apply a random projection

A random projection will ensure that $AV^{(i)}$ (for $i\in[3]$ ) has full Kruskal rank with high probability. The success event implies that the hyperplanes perpendicular to the columns of $Q:=AV^{(i)}$ lie in general position. More formally, denote the columns of $Q$ by $q_{1},...,q_{r}$ . For all $i\in[r]$ we define the hyperplane

H_{i}=\{z\in\mathbb{R}^{d}|\;\langle[z,1],q_{i}\rangle=0\}.

We denote the full set of hyperplanes by $\mathcal{H}=\{H_{1},...,H_{r}\}$ . By Lemma 13, $\mathcal{H}$ lies in general position with probability 1.

Step 2. Generate a MinRank instance

The MinRank instance generated at this step is the linear combination of $i$ -mode slices associated with coefficients $(z_{1},...,z_{d},1)$ , defined by

M(z)=T\times_{i}[z,1]A=V^{(j)}\mathrm{Diag}([z,1]AV^{(i)})(V^{(\ell)})^{T}.

Step 3. Solve the MinRank instance

The above specific factorization of $M(z)$ coupled with the Kruskal structure of the factor matrices $V^{(j)}$ and $V^{(\ell)}$ ensures that the rank drops precisely when $z$ lies on the intersection of the hyperplanes (see Theorem 14). Thus we have,

\textsc{MinRank}(M(z),k)=r-d

so at Step 3c we set $r^{\prime}=r$ , and then at 3b we find all the minimizers

\mathcal{S}=\{z\in\mathbb{R}^{d}|\;\operatorname{rank}M(z)=r-d\}.

By Theorem 14 this collection of points is exactly the set of $d$ -wise intersection points of hyperplanes in $\mathcal{H}$ .

Step 4. Reconstruct the projected component

Since $\mathcal{H}$ is in general position in $\mathbb{R}^{d}$ , all $d$ of the hyperplanes intersect at a unique point, and each hyperplane contains exactly $\binom{r-1}{d-1}$ points from $\mathcal{S}$ . Moreover, any hyperplane in $\mathbb{R}^{d}\backslash\mathcal{H}$ contains fewer points from $\mathcal{S}$ (see Lemma 27) so we can reconstruct $\mathcal{H}$ by iterating over subsets of $d$ points, generating a list of candidate hyperplanes, and checking which ones contain the characterizing number of points (see Algorithm HP-reconstruction for a randomized version of this algorithm).

Recovering $\mathcal{H}$ is equivalent to the recovery of $Q=AV^{(i)}$ (up to scaling and permutation of the columns), because by definition, the columns of $Q$ are the normals to the hyperplanes.

Step 5. Restore the remaining components $V^{(j)}$ and $V^{(\ell)}$

With the projected component $Q:=AV^{(i)}$ in hand we recover the components $V^{(j)}$ and $V^{(\ell)}$ by essentially reducing the problem to the “Jennrich setting,” and applying the Jennrich decomposition algorithm (see Lemma 9).

Specifically, we find a matrix $P\in\mathbb{R}^{2\times k}$ perpendicular to the first $k-2$ columns of $Q$ , and effectively “zero out” those summands in the decomposition. The resulting tensor now has a reduced number of components, $r^{\prime}=r-k+2$ . Furthermore, this reduction transforms the tensor from an initial $(k_{1},k_{2},k_{3})$ configuration to a “Jennrich state” where the Kruskal ranks of the $j$ and $\ell$ modes are $r^{\prime}$ , while the projected $i$ -mode’s Kruskal rank becomes $2$ . The fact that the truncated components have full rank $r^{\prime}$ follows from the Kruskal condition ( $\sum k_{i}\geq 2r+2$ implies that $k_{j},k_{\ell}\geq r^{\prime}=r-k+2$ ). This ensures that the truncated tensor satisfies the requirement for Jennrich’s algorithm. The remaining component can be recovered directly by applying $p_{j}$ with $\langle p_{j},q_{i}\rangle=\delta_{i,j}$ (see Algorithm 5). Thus, we can uniquely recover $V^{(j)}$ and $V^{(\ell)}$ (in polynomial time).

Step 6. Recover $V^{(i)}$

We recover $V^{(i)}$ by solving the linear system obtained from the entries of $T$ (which become linear in the entries of $V^{(i)}$ once we plug in the values of $V^{(j)}$ and $V^{(\ell)}$ ).

Generalization to $𝒎$ -way tensors

The transition from 3-way to general $m$ -way tensors is handled via a 3-reshaping process. Any $m$ -dimensional tensor satisfying the Kruskal condition can be partitioned into a 3-way tensor through Khatri-Rao products of its components.

We prove that if the original tensor satisfies the Kruskal condition, there exists a partition $I\sqcup J\sqcup L=[m]$ such that the resulting 3-way tensor also satisfies the Kruskal condition. After decomposing this reshaped 3-way tensor to find the partitioned components (e.g., $V_{I},V_{J},V_{L}$ ), we recover the original components $\{V^{(i)}\}_{i\in[m]}$ by exploiting the “injectivity” (up to scaling) of the Khatri-Rao product. This extends our “worst-case” guarantee to any $m$ -dimensional tensor satisfying the Kruskal bound. In terms of time complexity, the search for a 3-partition satisfying the Kruskal condition contributes a multiplicative factor of $O(3^{m})$ which is polynomial in the input size.

2.1 Outline of the paper

Section 3 collects definitions and notation (including some given previously). In Section 4 we formally present the decomposition algorithm, analyze it, and provide auxiliary lemmas and subroutines. Section 5 contains the proof of the main theorem. Finally, the Appendix contains more technical details, some of which may be well-known.

3 Preliminaries

For matrix $M\in\mathbb{R}^{m\times n}$ , row indices $R\subseteq[m]$ , and column indices $C\subseteq[n]$ , we denote $M(R,C)$ the submatrix of $M$ induced by $R$ and $C$ . We also denote $M(C):=M([m],C)$ . We denote the rows of $M$ by $m_{i}^{*}$ for $i\in[m]$ and the columns by $m_{j}$ for $j\in[n]$ (generally, rows/columns are denoted by the lower case letter of the matrix notation).

Definition 3 (Kruskal rank).

The Kruskal rank (or $k$ -rank) of a matrix $M\in\mathbb{R}^{m\times n}$ is the largest integer $k$ such that every subset of $k$ columns is linearly independent.

Definition 4 (mode- $i$ slices).

We define the mode- $i$ slices of a $m$ -way tensor $T$ as the $(m-1)$ -way tensors obtained from $T$ by fixing the $i$ -th index.

Definition 5 (mode- $i$ product).

The mode- $i$ product of a tensor $T\in\mathbb{R}^{n_{1}\times\dots\times n_{m}}$ with a matrix $A\in\mathbb{R}^{J\times n_{i}}$ , denoted by $T\times_{i}A$ , is a tensor of dimensions $n_{1}\times\dots\times n_{i-1}\times J\times n_{i+1}\times\dots\times n_{m}$ . For all $j\in J$ , the $j$ -th slice of $T\times_{i}A$ is a linear combination of the slices of $T$ along the same mode:

(T\times_{i}A)_{:,\dots,:,j,:,\dots,:}=\sum_{k=1}^{n_{i}}A_{jk}T_{:,\dots,:,k,% :,\dots,:},

Note that if $T$ has decomposition

T=\sum_{j=1}^{r}v_{j}^{(1)}\otimes v_{j}^{(2)}\otimes\dots\otimes v_{j}^{(m)}

then

T\times_{i}A=\sum_{j=1}^{r}v_{j}^{(1)}\otimes v_{j}^{(2)}\otimes\dots\otimes Av% _{j}^{(i)}\otimes\dots\otimes v_{j}^{(m)}.

Definition 6 (mode- $V$ contractions).

Let $T\in\mathbb{R}^{n_{u}\times n_{v}\times n_{w}}$ be a 3-way tensor with decomposition $T=\llbracket U,V,W\rrbracket$ . Define for all $z\in\mathbb{R}^{n_{v}-1}$ ,

M(z)=UD([z,1]V)W^{T}=T\times_{v}[z,1].

In other words, $M(z)\in\mathbb{R}^{n_{u}\times n_{w}}$ is the mode- $v$ product of $T$ with $[z,1]\in\mathbb{R}^{n_{v}}$ .

Definition 7 (Khatri-Rao product).

Let matrices $A=[a_{1},a_{2},...,a_{r}]\in\mathbb{R}^{n_{a}\times r}$ and $B=[b_{1},b_{2},...,b_{r}]\in\mathbb{R}^{n_{b}\times r}$ . The Khatri-Rao product $A\odot B$ is the column-wise Kronecker product:

A\odot B=[a_{1}\otimes b_{1},a_{2}\otimes b_{2},...,a_{r}\otimes b_{r}]\in% \mathbb{R}^{(n_{a}n_{b})\times r}.

Note that the rows of $A\odot B$ are the Hadamard products $a_{i}^{*}\odot b_{j}^{*}\in\mathbb{R}^{r}$ , for all $i\in[n_{a}]$ and $j\in[n_{b}]$ (the Hadamard product is the element-wise product of two vectors of the same length).

Definition 8 ( $d$ -reshaping).

Let $T\in\mathbb{R}^{n_{1}\times\dots\times n_{m}}$ be an $m$ -way tensor and let $\mathcal{S}=\{S_{1},\dots,S_{d}\}$ be a partition of the index set $[m]$ . The $d$ -reshaping of $T$ with respect to $\mathcal{S}$ is a $d$ -way tensor $T_{\mathcal{S}}\in\mathbb{R}^{N_{1}\times\dots\times N_{d}}$ , where the dimension of the $i$ -th mode is given by $N_{i}=\prod_{j\in S_{i}}n_{j}$ .

If $T$ has a CP decomposition $T=\sum_{j=1}^{r}v_{j}^{(1)}\otimes\dots\otimes v_{j}^{(m)}$ , then $T_{\mathcal{S}}$ admits a $d$ -way decomposition:

T_{\mathcal{S}}=\sum_{j=1}^{r}u_{j}^{(1)}\otimes u_{j}^{(2)}\otimes\dots% \otimes u_{j}^{(d)},

(4)

where each factor vector $u_{j}^{(i)}$ is the vectorization of the Kronecker product of the original factor vectors in the $i$ -th partition set:

u_{j}^{(i)}=\text{vec}\left(\bigotimes_{k\in S_{i}}v_{j}^{(k)}\right).

(5)

Equivalently, the component $U^{(i)}=[u_{1}^{(i)},\dots,u_{r}^{(i)}]$ is the Khatri-Rao product of the matrices $\{V^{(k)}\}_{k\in S_{i}}$ following the order of indices in $S_{i}$ .

Lemma 9 (Jennrich).

Let $T=\llbracket U,V,W\rrbracket$ be a 3-way tensor of rank $r$ , with components $U\in\mathbb{R}^{n_{u}\times r}$ , $V\in\mathbb{R}^{n_{v}\times r}$ , and $W\in\mathbb{R}^{n_{w}\times r}$ . Suppose that:

1.

$U$ and $W$ have full column rank $r$ .
2.

Every pair of columns of $V$ is linearly independent (i.e., $k_{v}\geq 2$ ).

Then the rank decomposition of $T$ is unique. Furthermore, there exists an algorithm to recover the components in time $O(n_{u}n_{v}n_{w}+r^{3})$ .

Lemma 10 (Making Tensor Concise).

[2, Lemma 5.1] Let $T\in\mathbb{R}^{n_{1}\times n_{2}\times\cdots\times n_{m}}$ be an $m$ -th order tensor of rank $r$ . There exists a randomized algorithm with runtime $\mathrm{poly}(\prod n_{i},r)$ that outputs a compressed tensor $T^{\prime}\in\mathbb{R}^{n^{\prime}_{1}\times n^{\prime}_{2}\times\cdots\times n% ^{\prime}_{m}}$ and transformation matrices $A_{i}\in\mathbb{R}^{n^{\prime}_{i}\times n_{i}}$ of full row rank such that, with probability 1:

1.

$T^{\prime}=(A_{1}\otimes A_{2}\otimes\cdots\otimes A_{m})\cdot T$ .
2.

The dimensions of $T^{\prime}$ are reduced such that $n^{\prime}_{i}=\mathrm{rank}_{i}(T)\leq r$ for each mode $i\in\{1,\dots,m\}$ , where $rank_{i}(T)$ refers to the rank of the $2$ -reshaping associated with the partition $[m]=\{i\}\sqcup[m]\backslash\{i\}$ .
3.

The rank $r$ and the Kruskal ranks $\{k_{i}\}_{i=1}^{m}$ are preserved; consequently, $T$ satisfies the Kruskal condition if and only if $T^{\prime}$ does.

The factor matrices $\{U_{i}\}_{i=1}^{m}$ of the original tensor $T$ are recovered from the factor matrices $\{U^{\prime}_{i}\}_{i=1}^{m}$ of $T^{\prime}$ via an efficiently computable linear mapping, requiring at most $\text{poly}(\prod n_{i},r)$ time.

Theorem 11 (Lakshman–Lazard [20]).

Let $I\subset K[x_{1},\ldots,x_{n}]$ be a zero-dimensional ideal over a field $K$ of characteristic zero, with generators of degree at most $d$ . Under any admissible monomial ordering, the Gröbner basis of radical of $I$ can be computed in $d^{O(n)}$ time, with probability at least $1-1/2^{d^{n}}$ . Moreover, zero-dimensionality of $I$ can be decided at the same cost and with the same probability of success.

Lemma 12 (Shape Lemma [9, Ch. 2, Exercise 16]).

Let $I\subset K[x_{1},\ldots,x_{n}]$ be a zero-dimensional radical ideal such that the $x_{n}$ -coordinates of the points in $V(I)$ are distinct. Let $G$ be the reduced Gröbner basis of $I$ with respect to a lex monomial order with $x_{n}$ as the last variable. If $|V(I)|=m$ , then $G$ consists of $n$ polynomials

g_{1}=x_{1}+h_{1}(x_{n}),\quad\ldots\quad,g_{n-1}=x_{n-1}+h_{n-1}(x_{n}),\quad g% _{n}=x_{n}^{m}+h_{n}(x_{n}),

where $h_{1},\ldots,h_{n}$ are polynomials in $x_{n}$ of degree at most $m-1$ . In particular, all $m$ points of $V(I)$ are recovered by finding the roots of $g_{n}$ and back-substituting into $g_{1},\ldots,g_{n-1}$ .

4 The decomposition algorithm

In this section, we formally present the decomposition algorithm for 3-way tensors. For tensors with $m>3$ modes, we first reshape the tensor to a 3-way tensor, apply our decomposition algorithm, and finally recover the components of the original $m$ -way tensor. We defer the discussion of this process to Section 5.

Let $T$ be a 3-way tensor with an $r$ -decomposition $\llbracket U,V,W\rrbracket$ , and corresponding Kruskal ranks $k_{u},k_{v},k_{w}$ . Recall that

k:=2r+2-\max\{k_{u}+k_{v},k_{u}+k_{w},k_{v}+k_{w}\}.

(6)

Under the Kruskal condition, $k$ is independent of the specific decomposition (see Lemma 19).

Because $k$ and its associated mode are unknown a priori, the full decomposition procedure (Algorithm 1) iteratively tests candidate values $k^{\prime}\geq 2$ and modes $i\in\{u,v,w\}$ until it reaches $k$ (and its corresponding mode).⁷⁷7To optimize performance, the search over $k^{\prime}$ is the outermost loop, as time complexity is exponential in $k$ . We restate a single round of this process as Algorithm DECOMPOSE, which takes parameters $(T,k^{\prime},i)$ . We show that Algorithm DECOMPOSE $(T,k,i)$ returns the unique decomposition with high probability, provided that $T$ satisfies the Kruskal condition and $k_{i}=\min\{k_{u},k_{v},k_{w}\}$ .

Here, we will assume that our tensor is concise: A concise tensor is an $m$ -th order tensor where each mode’s dimension $n_{i}$ is equal to the rank of its mode- $i$ flattening. Consequently, $n_{i}\leq r$ for all $i\in\{1,\dots,m\}$ . Due to Lemma 10, this “compression” and the consequent “decompression” can be performed efficiently, so we may assume WLOG that the input tensor is given in concise form.

Algorithm DECOMPOSE single iteration of Algorithm 1.

Input: $(T,k^{\prime},i)$ , where $T$ is concise. Denote $d^{\prime}=k^{\prime}-1$ .

1.

Apply a random matrix $A\in\mathbb{R}^{k^{\prime}\times n_{i}}$ on the $i$ -th mode of $T$ to obtain $T^{\prime}=T\times_{i}A$ .
2.

For variables $z=(z_{1},...,z_{d^{\prime}})$ form the matrix

$M(z):=T^{\prime}\times_{i}[z,1].$
3.
Run MinRank $(M,k^{\prime})$ .
1. (a)
  
  if the algorithm fails, continue to the next iteration of Algorithm 1. Otherwise,
2. (b)
  
  denote $m:=\textsc{MinRank}(M,k^{\prime})$ and
  
  $\mathcal{S}=\{z\in\mathbb{R}^{d^{\prime}}\,|\;\operatorname{rank}M(z)=m\}$
3. (c)
  
  Set $r^{\prime}=m+d^{\prime}$ .
4.
Apply HP-reconstruction $(\mathcal{S},r^{\prime},k^{\prime})$ to recover the $i$ -th component of $T^{\prime}$ .
1. (a)
  
  If the algorithm fails, continue to the next iteration of Algorithm 1. Otherwise,
2. (b)
  
  denote the output $Q$ .
5.

To recover the two other components $U^{\prime}$ and $W^{\prime}$ , apply Algorithm 5 on input $(T^{\prime},Q)$ .
6.

Solve the system obtained by the $v$ -mode reshaping

$T_{\{v\},\{u,w\}}=V^{\prime}(U^{\prime}\odot W^{\prime}).$
7.

Verify that $T=\llbracket U^{\prime},V^{\prime},W^{\prime}\rrbracket$ (if not, continue to the next iteration).

Output: $(U^{\prime},V^{\prime},W^{\prime})$ .

The algorithm follows the exact procedure described in the proof overview (Section 2). We begin by elaborating on each step, followed by the proof of correctness of DECOMPOSE in Theorem 21.

As discussed in the proof overview (Section 2), a key initial step to recover the factor matrices is to ensure that the hyperplanes perpendicular to the columns of the projected matrix $V$ lie in general position. In Step 1 of the algorithm, a projection matrix $A\in\mathbb{R}^{k\times n_{v}}$ is drawn from an absolutely continuous distribution (e.g., Gaussian) and applied to the $v$ -mode. The resulting tensor $\mathcal{T}^{\prime}\in\mathbb{R}^{n_{u}\times k\times n_{w}}$ possesses an $r$ -rank decomposition $\llbracket U,Q,W\rrbracket$ , where $Q:=AV\in\mathbb{R}^{k\times r}$ represents the projected factor matrix.

This ensures that $Q$ inherits the necessary structural properties for recovery, as formalized in the following lemma:

Lemma 13 (General Position of Projected Hyperplanes).

Let $V\in\mathbb{R}^{n_{v}\times r}$ be a matrix with Kruskal rank $k_{v}\geq k$ . Let $A\in\mathbb{R}^{k\times n_{v}}$ be drawn from an absolutely continuous distribution (e.g., Gaussian), and let $Q=AV$ . Then, with probability 1:

1.

$Q$ has full Kruskal rank $k$ .
2.

The first $d=k-1$ rows of $Q$ have full Kruskal rank $d$ .
3.

The set of hyperplanes $\mathcal{H}=\{H_{j}\}_{j=1}^{r}$ defined by $H_{j}=\{z\in\mathbb{R}^{d}\mid\langle[z,1],q_{j}\rangle=0\}$ lies in general position in $\mathbb{R}^{d}$ .

We defer the proof of the above to the full version [3]. If $A$ is a “good” projection, then the set $\mathcal{H}$ lies in general position in $\mathbb{R}^{d}$ , meaning that the intersection of any $t\leq d$ hyperplanes forms a $(d-t)$ -dimensional flat in $\mathbb{R}^{d}$ (and the intersection of $t>d$ hyperplanes is empty). In particular, $d$ -wise intersections are points, and every point is unique. There are exactly $\binom{r}{d}$ such points (see Lemma 27).

4.1 Step 2: finding the $𝒅$ -wise intersection points

In Step 2 of the decomposition algorithm, we list all the points $z$ , for which

\operatorname{rank}M(z)\leq r-d.

We need to show that:

1.

These points are precisely the $d$ -wise intersection points of hyperplanes in $\mathcal{H}$ . Namely,

$\{z:\;\operatorname{rank}M(z)\leq r-d\}=\bigcup_{I:|I|=d}\;\bigcap_{i\in I}H_{% i},$

and
2.

there are exactly $\binom{r}{d}$ points in this set.

The first fact is proved in the following lemma, while the second fact follows from a standard property of general position; we defer its statement and proof to Appendix Lemma 25.

Theorem 14.

Let $T=\llbracket U,Q,W\rrbracket$ be an $r$ -decomposition satisfying the Kruskal condition. Suppose that $Q\in\mathbb{R}^{k\times r}$ has full Kruskal rank $k$ , and let $M(z)=T\times_{q}[z,1]$ denote the $Q$ -mode contraction for $z\in\mathbb{R}^{d}$ where $d=:k-1$ .

Then,

1.

for all $z\in\mathbb{R}^{d}$ ,

$\operatorname{rank}M(z)\geq r-d,$
2.

$\operatorname{rank}M(z)=r-d$ if and only if $\operatorname{Wt}([z,1]Q)=r-d$ , and
3.

The minimizers of $\operatorname{rank}M$ are precisely the $d$ -wise intersection points:

$\{z:\;\operatorname{rank}M(z)=r-d\}=\bigcup_{I:|I|=d}\;\bigcap_{i\in I}H_{i}.$

Proof.

For all $z\in\mathbb{R}^{d}$ , denote $I_{z}\subseteq[r]$ the indices where $[z,1]Q$ is zero. Thus, $[z,1]Q(I_{z})=0$ for all $z$ . Since $Q$ has Kruskal rank $k$ , the subsystem $Q(I)$ has full rank $k$ whenever $|I|\geq k$ , so $|I_{z}|\leq d=k-1$ for all $z$ . That is, $[z,1]Q$ has at most $d$ zeros,

\implies\operatorname{Wt}([z,1]Q)\geq r-d

(7)

for all $z$ .

For Items 1 and 2 we prove the following:

1.

$\operatorname{Wt}([z,1]Q)=r-d\implies\operatorname{rank}M(z)=r-d$ ,
2.

$\operatorname{Wt}([z,1]Q)>r-d\implies\operatorname{rank}M(z)>r-d$ .

Fix $z\in\mathbb{R}^{d}$ , and denote $t:=|I_{z}|$ . Let $A, D$ and $B$ be the subsystems of $U,D([z,1]Q)$ and $W^{T}$ (respectively) induced by $[r]\backslash I_{z}$ . We have $A\in\mathbb{R}^{n_{u}\times(r-t)},D\in\mathbb{R}^{(r-t)\times(r-t)}$ , $B\in\mathbb{R}^{(r-t)\times n_{w}}$ , and

\operatorname{rank}(M(z))=\operatorname{rank}(ADB).

By Sylvester’s rank inequality, for pair of matrices $M_{1}\in\mathbb{R}^{n_{1}\times r}$ and $M_{2}\in\mathbb{R}^{r\times n_{2}}$ ,

\operatorname{rank}(M_{1}M_{2})\geq\operatorname{rank}M_{1}+\operatorname{rank% }M_{2}-r.

Therefore,

	$\displaystyle\operatorname{rank}(ADB)$	$\displaystyle\geq\operatorname{rank}(A)+\operatorname{rank}(DB)-(r-t)$
		$\displaystyle=\operatorname{rank}(A)+\operatorname{rank}(B)-(r-t)$
		$\displaystyle\geq\min\{r-t,k_{u}\}+\min\{r-t,k_{w}\}-(r-t)$

\implies\operatorname{rank}(M(z))\geq\min\{r-t,k_{u}\}+\min\{r-t,k_{w}\}-(r-t).

(8)

1.

Suppose that $t=d$ .⁸⁸8Recall that $t:=|I_{z}|$ is the number of zeros in $[z,1]V$ . The Kruskal condition implies that $r-d<k_{u},k_{w}$ .⁹⁹9If $k_{u}\leq r-d=r-k+1$ then $k_{u}+k+k_{w}\leq 2r+1$ which violates the Kruskal condition.

Equation 8 then implies that

$\operatorname{rank}(M(z))\geq r-d.$

On the other hand,

$\operatorname{rank}(M)=\operatorname{rank}(ADB)\leq\min\{n_{u},r-d,n_{w}\}=r-d.$

We have shown that

$\operatorname{Wt}([z,1]Q)=r-d\implies\operatorname{rank}(M(z))=r-d.$
2.

Let $t<d$ . By symmetry, we may assume without loss of generality that $k_{u}\geq k_{w}$ . The proof proceeds in two cases:

Case 1: $r-t\leq k_{u}$ .

Equation 8 implies that

$\operatorname{rank}(M)\geq\min\{r-t,k_{w}\}>r-d.$

Case 2: $r-t>k_{u}$ .

$\operatorname{rank}(M)\geq k_{u}+k_{w}-(r-t)\geq(2r+2-k)-(r-t)=(r-d)+(t+1)>r-d.$

In both cases, $\operatorname{rank}(M)>r-d$ .

This concludes the proof of Items 1 and 2.

Finally, we prove Item 3:

\{z:\;\operatorname{rank}M(z)\leq r-d\}=\bigcup_{I:|I|=d}\;\bigcap_{i\in I}H_{% i}.

Recall the definition of the hyperplanes,

H_{i}=\{z\in\mathbb{R}^{d}|\;\langle[z,1],q_{i}\rangle=0\},\;\ \forall i\in[r].

For every $z$ it holds that $z\in\bigcap\limits_{i\in I_{z}}H_{i}$ .

$\blacksquare$

If $\operatorname{rank}M(z)\leq r-d$ , then by Items 1 and 2, $\operatorname{Wt}([z,1]Q)=r-d$

$\implies|I_{z}|=d$

$\implies z\in\bigcup_{I:|I|=d}\;\bigcap_{i\in I}H_{i}.$
$\blacksquare$

Conversely, if $z\in\bigcup\limits_{I:|I|=d}\;\bigcap\limits_{i\in I}H_{i}$ then there exists $I$ of size $d$ s.t. $z\in\bigcap\limits_{i\in I}H_{i}$ , so $|I_{z}|\geq d$ . By Equation 7, $|I_{z}|=d$ . We apply again Item 2 and obtain

$\operatorname{rank}M(z)=r-d.\$

$\hfill\blacktriangleleft$

Algorithm MinRank Find minimizers of

\operatorname{rank}M(z)

.

Input: $(M(z),k^{\prime})$ where

$\blacksquare$

$M(z)=UD([z,1]V)W^{T}$ (this is an affine linear combination of matrices with coefficients $\{z_{1},...,z_{k^{\prime}-1},1\}$ ),
$\blacksquare$

$U\in\mathbb{R}^{n_{u}\times r},V\in\mathbb{R}^{k^{\prime}\times r}$ , $W\in\mathbb{R}^{n_{w}\times r}$ , and
$\blacksquare$

$n_{u},n_{w}\leq r$ .

Denote $n=\min\{n_{u},n_{w}\}$ .
Termination Condition: If at any point the total number of operations performed in the steps below exceeds $n^{ck^{\prime}}$ , for a large fixed determinable constant $c$ , the algorithm aborts and outputs fail.

1.
For $t=n,n-1,\ldots,1$ :
1. (a)
  
  Generate the system $\mathcal{E}_{t}$ by setting all $t$ -minors of $M(z)$ to zero.
2. (b)
  
  If $\mathcal{E}_{t}$ is zero-dimensional, compute the lexicographical Gröbner basis of the radical of $\mathcal{E}_{t}$ using Theorem 11. Then, determine whether a solution exists by applying Lemma 12.
3. (c)
  If the solution set is empty:
  1. i.
    
    Find $\mathcal{S}=\mathbb{V}(\mathcal{E}_{t+1})$ , the solution set of the previous system.
  2. ii.
    
    Output $(t,\mathcal{S})$ .
2.

Output fail.

Before proving the correctness of Algorithm MinRank, we emphasize that Theorem 11 determines dimensionality over $\mathbb{C}$ . It is possible in principal, that $\mathcal{E}_{t}$ has only solutions in $\mathbb{C}\backslash\mathbb{R}$ . In that case, MinRank may output a complex set of minimizers. However, by Theorem 14

\mathrm{MinRank}(M(z),k)=r-d,

and all the minimizers are solutions of a real linear system, and are therefore real. Thus, when Algorithm MinRank is called with $k^{\prime}=k$ , the solution set is real.

Lemma 15.

Let $d:=k-1$ as in Theorem 14, with $k$ as defined by Equation 6, and suppose that $r>9$ . If $V$ has full Kruskal rank $k^{\prime}$ , then with probability at least $1-2^{-r}$ ,

1.

if $k^{\prime}<k$ , then MinRank outputs MinRank $(M(z),k^{\prime})$ and a list of all the minimizers, or fail, and
2.

if $k^{\prime}=k$ , then MinRank outputs MinRank $(M(z),k)$ and a list of all the minimizers.

Either way, the time complexity is at most $n^{ck^{\prime}}=r^{O(d)}$ .

We defer the proof of the above to the full version [3].

4.2 Step 3: Reconstructing $\mathcal{H}$

Suppose that Step 2 of the decomposition algorithm was successfully executed. Then we have obtained the set of points

\mathcal{S}=\{z\in\mathbb{R}^{d}|\;\operatorname{rank}M(z)\leq r-d\}.

By Theorem 14 part 3, this is also the set of $d$ -wise intersection points of hyperplanes in $\mathcal{H}$ , i.e.,

\mathcal{S}=\bigcup\limits_{I:|I|=d}\bigcap\limits_{i\in I}H_{i}.

Our goal at Step 4 is to reconstruct $\mathcal{H}$ . We use the following criterion for identifying hyperplanes in $\mathcal{H}$ , the proof of which is deferred to the Appendix: Lemma 27.

Lemma 16 (Hyperplane Identification Criterion).

Let $\mathcal{H}$ be a set of $r$ hyperplanes in $\mathbb{R}^{d}$ in general position, and let $\mathcal{S}$ be the set of all $d$ -wise intersections of hyperplanes in $\mathcal{H}$ . If $H$ is a $(d-1)$ -dimensional hyperplane such that

|H\cap\mathcal{S}|>\frac{r}{d}\binom{r-2}{d-2},

then $H\in\mathcal{H}$ .

Thus, to reconstruct $\mathcal{H}$ we can iterate through all the $d$ -size subsets of $\mathcal{S}$ . For each subset, we calculate its affine rank. If it is $d-1$ , we find the normal to the hyperplane through the points. Then we can count the number of intersection points on the hyperplane to determine whether or not the hyperplane belongs to $\mathcal{H}$ . However, there are $\binom{|\mathcal{S}|}{d}=r^{O(d^{2})}$ subsets to explore, which dominate any other step of the decomposition algorithm, so we again apply randomness to reduce time complexity to $r^{O(d)}$ . We describe our algorithm for faster sampling of the points to recover these hyperplanes, followed by an analysis of its time complexity and success probability.

Algorithm HP-reconstruction Reconstruct

\mathcal{H}

given

\mathcal{S}

, the set of

d

-wise intersection points.

Input: $(\mathcal{S},r,t)$
Initialize $\mathcal{H}=\emptyset$ .
Repeat $r^{2d+t}$ times:

1.

Choose $d$ points $D\subset\mathcal{S}$ uniformly at random.
2.

If $D$ has affine rank $d-1$ , find the unique hyperplane $H$ through $D$ (up to scaling).
3.

If $|H\cap\mathcal{S}|>\frac{r}{d}\binom{r-2}{d-2}$ , and $H\notin\mathcal{H}$ , add $H$ to $\mathcal{H}$ .

If $|\mathcal{H}|\neq r$ , output fail. Otherwise, output $\mathcal{H}$ .

Lemma 17.

Let $\mathcal{H}=\{H_{1},...,H_{r}\}$ be a set of hyperplanes in general position in $\mathbb{R}^{d}$ ,¹⁰¹⁰10Meaning that the affine dimension of $\bigcap\limits_{i\in I}H_{i}$ is $\max\{d-|I|,0\}$ for all $I\subseteq[r]$ . and let $\mathcal{S}$ be the set of $d$ -wise intersection points of hyperplanes in $\mathcal{H}$ , then when invoked with parameters $(\mathcal{S},r,t)$ , Algorithm HP-reconstruction outputs $\mathcal{H}$ with probability at least $1-r\cdot 2^{-r^{t}}$ and runtime $r^{O(d)+t}$ . In particular, when $t=1$ Algorithm HP-reconstruction runs in time $r^{O(d)}$ and has success probability at least $1-2^{-r}$ .

We defer the proof of the above to the full version [3].

4.3 Step 4: restoring $𝑼$ and $𝑾$ given $𝑸$

Once Step 3 outputs $Q$ , which is a random projection of $V$ , Step 4 aims to learn $U$ and $W$ using $Q$ . That is, we are given a tensor $T=\sum_{i=1}^{r}u_{i}\otimes v_{i}\otimes q_{i}\in\mathbb{R}^{n_{1}\times n_{2% }\times n_{3}},$ one of its components $Q$ , and we want to recover $U$ and $V$ .

We assume that $Q$ has full Kruskal rank $k_{q}=n_{q}\leq\min\{k_{u},k_{v}\}$ , and that the factor matrices satisfy the Kruskal condition. Our approach is to use $Q$ to eliminate $k_{q}-2$ terms from the decomposition while maintaining a Kruskal rank of $2$ in the third mode. This reduction transforms the problem into a Jennrich instance, which can then be solved directly. We formally present the algorithm for this recovery process, followed by its proof of correctness.

Algorithm 5 Decompose

T

given a component

Q

.

Input: $(T,Q)$ where

$\blacksquare$

$T=\sum_{i=1}^{r}u_{i}\otimes v_{i}\otimes q_{i}$ .
$\blacksquare$

$k_{q}=n_{q}$ .
$\blacksquare$

Kruskal’s Condition: $k_{u}+k_{v}+k_{q}\geq 2r+2$

For any matrix $M$ with $r$ columns, denote $M_{1}$ the sub-matrix induced by columns $\{1,...,k_{q}-2\}$ , and $M_{2}$ the sub-matrix induced by columns $\{k_{q}-1,...,r\}$ .

1.

If $k_{q}=2$ apply Jennrich’s Algorithm and output the decomposition.
2.

Else, find full rank $P\in\mathbb{R}^{2\times k_{q}}$ perpendicular to $Q_{1}\in\mathbb{R}^{k_{q}\times(k_{q}-2)}$ (i.e. the rows of $P$ form a basis for the left kernel of $Q_{1}$ ).
3.

Apply Jennrich’s algorithm to $T\times_{q}P=\sum_{i=1}^{r}u_{i}\otimes v_{i}\otimes Pq_{i}=\sum_{i=k_{q}-1}^{% r}u_{i}\otimes v_{i}\otimes Pq_{i}$ to obtain a decomposition

$T\times_{q}P=\llbracket\tilde{U}_{2},\tilde{V}_{2},PQ_{2}\rrbracket.$

Matching $U, V, Q$ : Resolve permutation and scaling ambiguities by aligning the output with the ground-truth matrix $PQ_{2}$ . Apply the resulting permutation and inverse scaling to $\tilde{U}_{2}$ and $\tilde{V}_{2}$ to maintain consistency with $Q$ .
4.

Compute $T_{2}:=\sum_{i=k_{q}-1}^{r}\tilde{u}_{i}\otimes\tilde{v}_{i}\otimes q_{i}=\sum% _{i=k_{q}-1}^{r}u_{i}\otimes v_{i}\otimes q_{i}$ and

$T_{1}:=T-T_{2}=\sum_{i=1}^{k_{q}-2}u_{i}\otimes v_{i}\otimes q_{i}.$
5.

For each $\ell\in[k_{q}-2]$ , find $p_{\ell}\in\mathbb{R}^{k_{q}}$ such that $\langle p_{\ell},q_{j}\rangle=\mathds{1}_{\ell=j}$ for all $j\in[k_{q}-2]$ (for example, take $p_{\ell}$ to be the $\ell$ -th row of $Q_{1}^{\dagger}$ ). Decompose the rank-1 matrices

$T_{1}\times_{q}p_{\ell}=u_{\ell}\otimes v_{\ell}$

via SVD to find $\tilde{U}_{1}$ and $\tilde{V}_{1}$ .

Output: $\tilde{U}$ and $\tilde{V}$ .

Lemma 18.

Let $T=\sum_{i=1}^{r}u_{i}\otimes v_{i}\otimes q_{i}$ be a rank- $r$ tensor. Given the tensor $T$ and the factor matrix $Q=[q_{1},\dots,q_{r}]$ as input, if $k_{q}=n_{q}$ and $k_{u}+k_{v}+k_{q}\geq 2r+2$ , then Algorithm 5 outputs a decomposition of $T$ in time $\mathrm{poly}(n_{u}n_{v}n_{q})$ . Furthermore, under these conditions, the decomposition $\{u_{i},v_{i},q_{i}\}_{i=1}^{r}$ is the only possible rank- $r$ representation of $T$ up to permutation and scaling.

We defer the proof of the above to the full version [3].

4.4 Analysis of DECOMPOSE

As mentioned in Section 2 (Proof Overview), the correctness of DECOMPOSE follows from these 3 facts:

1.

Lemma 19: If an $r$ -decomposition satisfies the Kruskal condition, then the tensor has rank $r$ and every rank-decomposition has the same $k$ .
2.

Lemma 20: At iterations $k^{\prime}\leq k$ , the decomposition algorithm does not output a “redundant” decomposition. i.e. an $r^{\prime}$ -decompositions with $r^{\prime}>r$ .
3.

Theorem 21: At iteration $k$ , the algorithm outputs a (unique) $r$ -decomposition (with high probability).

We now prove these 3 statements by order.

Lemma 19 (Uniqueness of “good” parameters).

Let $T$ be a tensor with $r$ -decomposition $\llbracket V^{(1)},V^{(2)},V^{(3)}\rrbracket$ and Kruskal ranks $(k_{1},k_{2},k_{3})$ . If $(k_{1},k_{2},k_{3})$ satisfies the Kruskal condition then:

1.

$\operatorname{rank}T=r$ , and
2.

all rank decompositions have Kruskal ranks $(k_{1},k_{2},k_{3})$ (and therefore satisfy the Kruskal condition).

We defer the proof of the above to the full version [3].

Lemma 20.

If $k^{\prime}\leq k$ , then the candidate rank $r^{\prime}$ computed by the algorithm at Step 3c satisfies $r^{\prime}\leq r$ , where $r$ is the true rank of the tensor.

We defer the proof of the above to the full version [3]. With the ingredients from the previous sections established, we are now ready to analyze the decomposition algorithm. The full decomposition algorithm includes loops iterating over guesses of $k$ and corresponding mode.

In order to simplify the probability estimates, we assume that $r>9$ . Indeed, for cases where $r\leq 9$ , one can simply apply a worst-case tensor decomposition algorithm [2, 4], which remains functional even without assuming the Kruskal condition.

Theorem 21 (Decomposition algorithm).

Let $T\in\mathbb{R}^{n_{u}\times n_{v}\times n_{w}}$ be a 3-way tensor with an $r$ -decomposition $\llbracket U,V,W\rrbracket$ with $U, V, W$ over $\mathbb{R}$ of appropriate dimensions. Suppose that the decomposition satisfies the Kruskal condition and $r>9$ . Let $k$ be as in Eq.6. Then, we have the following.

1.

Completeness: By iteration $k$ of the outer-loop, the algorithm outputs the components $U, V, W$ (up to scaling and permutation) with probability at least $1-2^{-0.1r}$ .
2.

Soundness: With probability at least $1-2^{-0.1r}$ , the algorithm does not output a redundant decomposition ( $r^{\prime}$ -decomposition with $r^{\prime}>r$ ) at any iteration $k^{\prime}\in\{2,...,k\}$ of the outer-loop.
3.

Time Complexity: The overall time complexity is

$\max(\mathrm{poly}(N),(r)^{O(k)})$

where $N=n_{u}n_{v}n_{w}$ .

We defer the proof of the above to the full version [3].

5 Decomposing high dimensional tensors

In the previous section we presented a decomposition algorithm for 3-way tensors. To deal with $m$ -way tensors with $m>3$ , we reshape the tensor and apply the decomposition algorithm on the reshaped tensor. We now introduce some notation to formalize this process. Let $T=\llbracket V^{(1)},V^{(2)},...,V^{(m)}\rrbracket$ . For all $J\subseteq[m]$ with $|J|\geq 2$ we denote $V^{J}$ the Khatri-Rao product of $\{V^{(j)}\}_{j\in J}$ (see Definition 7), and $k_{J}$ the Kruskal rank of $V^{J}$ . For any partition $I\sqcup J\sqcup L=[m]$ , the 3-reshaping of $T$ (see Definition 8) has components $V^{I},V^{J}$ and $V^{L}$ . If these matrices satisfy the Kruskal condition, then the decomposition algorithm succeeds (w.h.p) and outputs $V^{I},V^{J},V^{L}$ up to permutation and scaling of the columns. The columns of these matrices are vectorized rank one tensors, so we can directly recover the components of the $m$ -way tensor (via SVD).

Theorem 22 (Reshaped Kruskal Theorem).

Let $r\geq 2$ , and $m\geq 3$ . Consider an $m$ -way tensor $T\in\mathbb{R}^{n_{1}\times n_{2}\times\dots\times n_{m}}$ with decomposition:

T=\sum_{j=1}^{r}v_{j}^{(1)}\otimes v_{j}^{(2)}\otimes\dots\otimes v_{j}^{(m)}

(9)

For each subset $\emptyset\neq I\subseteq[m]$ , define $V_{I}$ as the Khatri-Rao product of matrices $\{V^{(i)}\}_{i\in I}$ . If there exists a partition $I\sqcup J\sqcup L=[m]$ and the Kruskal ranks of these partitioned matrices satisfy the Kruskal condition:

k_{I}+k_{J}+k_{L}\geq 2r+2

(10)

then,

1.

$\operatorname{rank}T=r$ , and
2.

the decomposition is unique up to scaling and permutation.

Furthermore, for $r>9$ , there exists a randomized algorithm that recovers the unique components with probability at least $1-2^{-0.1r}$ and runtime $N^{O({k})}$ , where $k:=2r+2-\max\{k_{I}+k_{J},k_{I}+k_{L},k_{J}+k_{L}\}$ and $N:=\prod\limits_{i\in[m]}n_{i}$ is the input size.

We defer the proof of the above to the full version [3].

If the input $m$ -dimensional tensor satisfies the Kruskal condition, then there is an efficient way to perform the 3-reshaping. As a direct consequence, we obtain the following corollary. We defer the reshaping procedure and its correctness to the Appendix, see Lemma 24.

Corollary 23 (Kruskal’s Uniqueness Theorem).

Consider an $m$ -way tensor $T\in\mathbb{R}^{n_{1}\!\times\!n_{2}\!\times\!\dots\!\times n_{m}}$ with decomposition:

T=\sum_{j=1}^{r}V_{j}^{(1)}\otimes V_{j}^{(2)}\otimes\dots\otimes V_{j}^{(m)}

(11)

If the Kruskal condition holds:

\sum_{t=1}^{m}k_{t}\geq 2r+m-1

(12)

then,

1.

$\operatorname{rank}T=r$ , and
2.

the decomposition is unique up to scaling and permutation.

Furthermore, for $r>9$ , there exists a randomized algorithm that outputs the unique components with probability at least $1-2^{-0.1r}$ and runtime $N^{O({k})}$ , where $k:=2r+2-\max\{k_{I}+k_{J},k_{I}+k_{L},k_{J}+k_{L}\}$ and $N:=\prod\limits_{i\in[m]}n_{i}$ .

Again, for cases where $r\leq 9$ , one can simply apply a worst-case tensor decomposition algorithm [2, 4], which will decompose these $m$ -tensors even without the Kruskal condition in $\mathrm{poly}({m,\max{n_{i}}})$ time.

References

[1] M. Bardet, M. Bros, D. Cabarcas, P. Gaborit, R. A. Perlner, D. Smith-Tone, J.-P. Tillich, and J. A. Verbel. Improvements of algebraic attacks for solving the rank decoding and minrank problems. In ASIACRYPT, 2020.
[2] Vishwas Bhargava, Shubhangi Saraf, and Ilya Volkovich. Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits. Technical Report 045, Electronic Colloquium on Computational Complexity (ECCC), 2021. Version with full proofs; subsequently appeared in STOC 2021. URL: https://eccc.weizmann.ac.il/report/2021/045/.
[3] Vishwas Bhargava, Leonard Schulman, and Shiri Sivan. An algorithmic proof of kruskal’s tensor decomposition theorem. Technical Report TR26-073, Electronic Colloquium on Computational Complexity (ECCC), 2026. URL: https://eccc.weizmann.ac.il/report/2026/073/.
[4] Vishwas Bhargava and Devansh Shringi. Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), volume 334 of Leibniz International Proceedings in Informatics (LIPIcs), pages 28:1–28:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ICALP.2025.28.
[5] Aditya Bhaskara, Moses Charikar, Ankur Moitra, and Aravindan Vijayaraghavan. Open problem: Tensor decompositions: Algorithms up to the uniqueness threshold? In Conference on Learning Theory, pages 1280–1282. PMLR, 2014. URL: http://proceedings.mlr.press/v35/bhaskara14b.html.
[6] J.D. Carroll and J.J. Chang. Analysis of individual differences in multidimensional scaling via an n-way generalization of “Eckart-Young” decomposition. Psychometrika, 35:283–319, 1970. doi:10.1007/BF02310791.
[7] Luca Chiantini and Giorgio Ottaviani. On generic identifiability of 3-tensors of small rank. SIAM Journal on Matrix Analysis and Applications, 33(3):1018–1037, 2012. doi:10.1137/110829180.
[8] Luca Chiantini, Giorgio Ottaviani, and Nick Vannieuwenhoven. Effective criteria for specific identifiability of tensors and forms. SIAM Journal on Matrix Analysis and Applications, 38(2):656–681, 2017. doi:10.1137/16M1090132.
[9] David A. Cox, John Little, and Donal O’Shea. Using Algebraic Geometry, volume 185 of Graduate Texts in Mathematics. Springer, New York, 1998.
[10] Harm Derksen. Kruskal’s uniqueness inequality is sharp. Linear Algebra and its Applications, 438(2):708–712, 2013. Tensors and Multilinear Algebra. doi:10.1016/j.laa.2011.05.041.
[11] J. Faugère, M. Safey El Din, and P. Spaenlehauer. Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology. In International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 257–264, 2010. doi:10.1145/1837934.1837984.
[12] Richard A. Harshman. Foundations of the PARAFAC procedure: Models and conditions for an “explanatory” multi-model factor analysis. In UCLA working papers in phonetics, 16(1):84, 1970. URL: https://api.semanticscholar.org/CorpusID:6816804.
[13] Johan Håstad. Tensor rank is NP-complete. Journal of Algorithms, 11(4):644–654, 1990. doi:10.1016/0196-6774(90)90014-6.
[14] Christopher J Hillar and Lek-Heng Lim. Most tensor problems are NP-hard. Journal of the ACM (JACM), 60(6):1–39, 2013. doi:10.1145/2512329.
[15] Doug Ierardi. Quantifier elimination in the theory of an algebraically-closed field. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pages 138–147, 1989. doi:10.1145/73007.73020.
[16] Pravesh K Kothari, Ankur Moitra, and Alexander S Wein. Overcomplete tensor decomposition via Koszul-Young flattenings. arXiv preprint arXiv:2411.14344, 2024. doi:10.48550/arXiv.2411.14344.
[17] J. B. Kruskal. More factors than subjects, tests and treatments: an indeterminacy theorem for canonical decomposition and individual differences scaling. Psychometrica, 41(3):281–293, 1976.
[18] J. B. Kruskal. Rank, decomposition and uniqueness for 3-way and n-way arrays. In Multiway data analysis, pages 7–18. Elsevier Science Publishers B.B. (North-Holland, 1989.
[19] Joseph B. Kruskal. Three-way arrays: Rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics. Linear Algebra and its Applications, 18(2):95–138, 1977. doi:10.1016/0024-3795(77)90069-6.
[20] Yagati N Lakshman and Daniel Lazard. On the complexity of zero-dimensional algebraic systems. In Effective methods in algebraic geometry, pages 217–225. Springer, 1991.
[21] Joseph M Landsberg. Tensors: geometry and applications: geometry and applications, volume 128. American Mathematical Soc., 2011.
[22] Benjamin Lovitz and Fedor Petrov. A generalization of Kruskal’s theorem on tensor decomposition. In Forum of Mathematics, Sigma, volume 11, page e27. Cambridge University Press, 2023.
[23] Tengyu Ma, Jonathan Shi, and David Steurer. Polynomial-time tensor decompositions with sum-of-squares. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 438–446. IEEE, 2016. doi:10.1109/FOCS.2016.54.
[24] S. Rabanser, O. Shchur, and S. Günnemann. Introduction to tensor decompositions and their applications in machine learning, 2017. arXiv:1711.10781.
[25] John A. Rhodes. A concise proof of Kruskal’s theorem on tensor decomposition. Linear Algebra and its Applications, 432(7):1818–1824, 2010. doi:10.1016/j.laa.2009.11.033.
[26] Marcus Schaefer and Daniel Štefankovič. The complexity of tensor rank. Theory of Computing Systems, 62(5):1161–1174, 2018. doi:10.1007/S00224-017-9800-Y.
[27] Nicholas D Sidiropoulos and Rasmus Bro. On the uniqueness of multilinear decomposition of n-way arrays. Journal of Chemometrics: A Journal of the Chemometrics Society, 14(3):229–239, 2000.
[28] Charles Spearman. “General intelligence” objectively determined and measured. In J. J. Jenkins & D. G. Paterson, editor, Studies in individual differences: The search for intelligence, pages 59–73. Appleton-Century-Crofts, 1961. Reprint from American Journal of Psychology, 1904, Vol 15[2], 201-293. doi:10.1037/11491-006.
[29] Alwin Stegeman and Nicholas D Sidiropoulos. On Kruskal’s uniqueness condition for the Candecomp/Parafac decomposition. Linear Algebra and its applications, 420(2-3):540–552, 2007.

Appendix A Reshaping into 3-tensors

Lemma 24.

If $T$ is an $m$ -way tensor satisfying the Kruskal condition, then there exists a partition of $[m]$ into disjoint subsets $J\sqcup K\sqcup L=[m]$ s.t. $\llbracket V^{J},V^{K},V^{L}\rrbracket$ satisfies the Kruskal condition, namely,

k_{J}+k_{K}+k_{L}\geq 2r+2.

We defer the proof of the above to the full version [3].

A.1 General position statements

In the first step of the decomposition algorithm (Algorithm DECOMPOSE) we apply a random matrix on one of the components of the tensor we are trying to decompose. We obtain a component $Q\in\mathbb{R}^{k\times r}$ and define, for every column, the orthogonal hyperplane: $H_{i}:=\{z\in\mathbb{R}^{d}|\;\langle[z,1],q_{i}^{|}\rangle=0\}$ . We denote the full set of hyperplanes by

\mathcal{H}=\{H_{1},...,H_{r}\}.

Lemma 25.

If $Q\in\mathbb{R}^{k\times r}$ has Kruskal rank $k$ , and $Q([d],[r])$ has Kruskal rank $d=k-1$ , then $\mathcal{H}$ is in general position in $\mathbb{R}^{d}$ . That is, for all $I\subseteq[r]$ , the affine dimension of $\bigcap\limits_{i\in I}H_{i}$ is $\max\{d-|I|,0\}$ .

We defer the proof of the above to the full version [3].

When $\mathcal{H}$ is in general position, we can count the number of $d$ -wise intersection points on the flats defined by $\mathcal{H}$ :

Corollary 26.

If $\mathcal{H}$ is in general position in $\mathbb{R}^{d}$ , then

\mathcal{S}:=\{\bigcap_{i\in I}H_{i}\;|\;I\subseteq[r]\;,|I|=d\}

has size $\binom{r}{d}$ . More generally, for any $I\subseteq[r]$ , $|I|=t\leq d$ ,

|\bigcap_{i\in I}H_{i}\cap\mathcal{S}|=\binom{r-t}{d-t}.

We defer the proof of the above to the full version [3].

Lemma 27.

Let $r>d$ , $d\geq 2$ . We have

$\blacksquare$

$\mathcal{H}$ , a set of $r$ hyperplanes of dimension $d-1$ in general position in $\mathbb{R}^{d}$ .
$\blacksquare$

$\mathcal{S}$ , the set of $d$ -wise intersections of hyperplanes in $\mathcal{H}$ .

If $H$ is a $(d-1)$ -dimensional hyperplane, and

|H\cap\mathcal{S}|>\frac{r}{d}\binom{r-2}{d-2},

then $H\in\mathcal{H}$ .

We defer the proof of the above to the full version [3].

Corollary 28.

For any hyperplane $H$ ,

|H\cap\mathcal{S}|\leq\binom{r-1}{d-1}

We defer the proof of the above to the full version [3].

Lemma 29.

Let $\mathcal{P}=\{s_{1},...,s_{d}\}$ be a set of points chosen uniformly at random from $\mathcal{S}$ . Then, for any $H_{\ell}\in\mathcal{H}$ , $\mathcal{P}$ spans $H_{\ell}$ with probability at least $\frac{1}{r^{2d}}$ .

We defer the proof of the above to the full version [3].

[bib.bib1] [1] M. Bardet, M. Bros, D. Cabarcas, P. Gaborit, R. A. Perlner, D. Smith-Tone, J.-P. Tillich, and J. A. Verbel. Improvements of algebraic attacks for solving the rank decoding and minrank problems. In ASIACRYPT, 2020.

[bib.bib2] [2] Vishwas Bhargava, Shubhangi Saraf, and Ilya Volkovich. Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits. Technical Report 045, Electronic Colloquium on Computational Complexity (ECCC), 2021. Version with full proofs; subsequently appeared in STOC 2021. URL: https://eccc.weizmann.ac.il/report/2021/045/.

[bib.bib3] [3] Vishwas Bhargava, Leonard Schulman, and Shiri Sivan. An algorithmic proof of kruskal’s tensor decomposition theorem. Technical Report TR26-073, Electronic Colloquium on Computational Complexity (ECCC), 2026. URL: https://eccc.weizmann.ac.il/report/2026/073/.

[bib.bib4] [4] Vishwas Bhargava and Devansh Shringi. Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), volume 334 of Leibniz International Proceedings in Informatics (LIPIcs), pages 28:1–28:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ICALP.2025.28.

[bib.bib5] [5] Aditya Bhaskara, Moses Charikar, Ankur Moitra, and Aravindan Vijayaraghavan. Open problem: Tensor decompositions: Algorithms up to the uniqueness threshold? In Conference on Learning Theory, pages 1280–1282. PMLR, 2014. URL: http://proceedings.mlr.press/v35/bhaskara14b.html.

[bib.bib6] [6] J.D. Carroll and J.J. Chang. Analysis of individual differences in multidimensional scaling via an n-way generalization of “Eckart-Young” decomposition. Psychometrika, 35:283–319, 1970. doi:10.1007/BF02310791.

[bib.bib7] [7] Luca Chiantini and Giorgio Ottaviani. On generic identifiability of 3-tensors of small rank. SIAM Journal on Matrix Analysis and Applications, 33(3):1018–1037, 2012. doi:10.1137/110829180.

[bib.bib8] [8] Luca Chiantini, Giorgio Ottaviani, and Nick Vannieuwenhoven. Effective criteria for specific identifiability of tensors and forms. SIAM Journal on Matrix Analysis and Applications, 38(2):656–681, 2017. doi:10.1137/16M1090132.

[bib.bib9] [9] David A. Cox, John Little, and Donal O’Shea. Using Algebraic Geometry, volume 185 of Graduate Texts in Mathematics. Springer, New York, 1998.

[bib.bib10] [10] Harm Derksen. Kruskal’s uniqueness inequality is sharp. Linear Algebra and its Applications, 438(2):708–712, 2013. Tensors and Multilinear Algebra. doi:10.1016/j.laa.2011.05.041.

[bib.bib11] [11] J. Faugère, M. Safey El Din, and P. Spaenlehauer. Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology. In International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 257–264, 2010. doi:10.1145/1837934.1837984.

[bib.bib12] [12] Richard A. Harshman. Foundations of the PARAFAC procedure: Models and conditions for an “explanatory” multi-model factor analysis. In UCLA working papers in phonetics, 16(1):84, 1970. URL: https://api.semanticscholar.org/CorpusID:6816804.

[bib.bib13] [13] Johan Håstad. Tensor rank is NP-complete. Journal of Algorithms, 11(4):644–654, 1990. doi:10.1016/0196-6774(90)90014-6.

[bib.bib14] [14] Christopher J Hillar and Lek-Heng Lim. Most tensor problems are NP-hard. Journal of the ACM (JACM), 60(6):1–39, 2013. doi:10.1145/2512329.

[bib.bib15] [15] Doug Ierardi. Quantifier elimination in the theory of an algebraically-closed field. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pages 138–147, 1989. doi:10.1145/73007.73020.

[bib.bib16] [16] Pravesh K Kothari, Ankur Moitra, and Alexander S Wein. Overcomplete tensor decomposition via Koszul-Young flattenings. arXiv preprint arXiv:2411.14344, 2024. doi:10.48550/arXiv.2411.14344.

[bib.bib17] [17] J. B. Kruskal. More factors than subjects, tests and treatments: an indeterminacy theorem for canonical decomposition and individual differences scaling. Psychometrica, 41(3):281–293, 1976.

[bib.bib18] [18] J. B. Kruskal. Rank, decomposition and uniqueness for 3-way and n-way arrays. In Multiway data analysis, pages 7–18. Elsevier Science Publishers B.B. (North-Holland, 1989.

[bib.bib19] [19] Joseph B. Kruskal. Three-way arrays: Rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics. Linear Algebra and its Applications, 18(2):95–138, 1977. doi:10.1016/0024-3795(77)90069-6.

[bib.bib20] [20] Yagati N Lakshman and Daniel Lazard. On the complexity of zero-dimensional algebraic systems. In Effective methods in algebraic geometry, pages 217–225. Springer, 1991.

[bib.bib21] [21] Joseph M Landsberg. Tensors: geometry and applications: geometry and applications, volume 128. American Mathematical Soc., 2011.

[bib.bib22] [22] Benjamin Lovitz and Fedor Petrov. A generalization of Kruskal’s theorem on tensor decomposition. In Forum of Mathematics, Sigma, volume 11, page e27. Cambridge University Press, 2023.

[bib.bib23] [23] Tengyu Ma, Jonathan Shi, and David Steurer. Polynomial-time tensor decompositions with sum-of-squares. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 438–446. IEEE, 2016. doi:10.1109/FOCS.2016.54.

[bib.bib24] [24] S. Rabanser, O. Shchur, and S. Günnemann. Introduction to tensor decompositions and their applications in machine learning, 2017. arXiv:1711.10781.

[bib.bib25] [25] John A. Rhodes. A concise proof of Kruskal’s theorem on tensor decomposition. Linear Algebra and its Applications, 432(7):1818–1824, 2010. doi:10.1016/j.laa.2009.11.033.

[bib.bib26] [26] Marcus Schaefer and Daniel Štefankovič. The complexity of tensor rank. Theory of Computing Systems, 62(5):1161–1174, 2018. doi:10.1007/S00224-017-9800-Y.

[bib.bib27] [27] Nicholas D Sidiropoulos and Rasmus Bro. On the uniqueness of multilinear decomposition of n-way arrays. Journal of Chemometrics: A Journal of the Chemometrics Society, 14(3):229–239, 2000.

[bib.bib28] [28] Charles Spearman. “General intelligence” objectively determined and measured. In J. J. Jenkins & D. G. Paterson, editor, Studies in individual differences: The search for intelligence, pages 59–73. Appleton-Century-Crofts, 1961. Reprint from American Journal of Psychology, 1904, Vol 15[2], 201-293. doi:10.1037/11491-006.

[bib.bib29] [29] Alwin Stegeman and Nicholas D Sidiropoulos. On Kruskal’s uniqueness condition for the Candecomp/Parafac decomposition. Linear Algebra and its applications, 420(2-3):540–552, 2007.

An Algorithmic Proof of Kruskal’s Tensor Decomposition Theorem

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our contribution

Theorem 1 (Algorithmic Kruskal for 3-tensors).

Theorem 2 (Reshaped Kruskal Theorem).

1.2 Related Work

2 Proof Overview

The identifiability test

The tensor decomposition algorithm

Step 1. Apply a random projection

Step 2. Generate a MinRank instance

Step 3. Solve the MinRank instance

Step 4. Reconstruct the projected component

Step 5. Restore the remaining components 𝑽(𝒋) and 𝑽(ℓ)

Step 6. Recover 𝑽(𝒊)

Generalization to 𝒎-way tensors

2.1 Outline of the paper

3 Preliminaries

Definition 3 (Kruskal rank).

Definition 4 (mode-i slices).

Definition 5 (mode-i product).

Definition 6 (mode-V contractions).

Definition 7 (Khatri-Rao product).

Definition 8 (d-reshaping).

Lemma 9 (Jennrich).

Lemma 10 (Making Tensor Concise).

Theorem 11 (Lakshman–Lazard [20]).

Lemma 12 (Shape Lemma [9, Ch. 2, Exercise 16]).

4 The decomposition algorithm

Lemma 13 (General Position of Projected Hyperplanes).

4.1 Step 2: finding the 𝒅-wise intersection points

Theorem 14.

Proof.

Case 1: 𝒓−𝒕≤𝒌𝒖.

Case 2: 𝒓−𝒕>𝒌𝒖.

Lemma 15.

4.2 Step 3: Reconstructing 𝓗

Lemma 16 (Hyperplane Identification Criterion).

Lemma 17.

4.3 Step 4: restoring 𝑼 and 𝑾 given 𝑸

Lemma 18.

4.4 Analysis of DECOMPOSE

Lemma 19 (Uniqueness of “good” parameters).

Lemma 20.

Theorem 21 (Decomposition algorithm).

5 Decomposing high dimensional tensors

Theorem 22 (Reshaped Kruskal Theorem).

Corollary 23 (Kruskal’s Uniqueness Theorem).

References

Appendix A Reshaping into 3-tensors

Lemma 24.

A.1 General position statements

Lemma 25.

Corollary 26.

Lemma 27.

Corollary 28.

Lemma 29.

Step 5. Restore the remaining components $V^{(j)}$ and $V^{(\ell)}$

Step 6. Recover $V^{(i)}$

Generalization to $𝒎$ -way tensors

Definition 4 (mode- $i$ slices).

Definition 5 (mode- $i$ product).

Definition 6 (mode- $V$ contractions).

Definition 8 ( $d$ -reshaping).

4.1 Step 2: finding the $𝒅$ -wise intersection points

Case 1: $r-t\leq k_{u}$ .

Case 2: $r-t>k_{u}$ .

4.2 Step 3: Reconstructing $\mathcal{H}$

4.3 Step 4: restoring $𝑼$ and $𝑾$ given $𝑸$