The Two Parallel Worlds of Algorithms for Tensor Decomposition �
Pravesh Kothari
Princeton
WACT 2026
based on joint work with Alex Wein (UC Davis) and Ankur Moitra (MIT)
Tensor Rank/Decomposition
*of order 3. We’ll focus only on order 3.
Natural generalization of matrix (i.e., tensors of order 2) rank.
Question: Efficient algorithms for computing rank r of T?
…for decomposing into a sum of r rank 1 tensors?
…“canonical polyadic” or CP rank
Captures the circuit complexity of bilinear computation.
[Strassen’60s]
Tensor Rank: Algorithms?
Question: Efficient algorithms for computing rank/rank decomposition of T?
Why?
Learn parameters of a statistical model by estimating its (low-degree) moment tensors from samples.
e.g., Mixture of spherical Gaussians
[Hsu,Kakade’11]
can be computed easily from samples
Method of Moments
[Pearson’1890s]
apply tensor decomposition!
Question: Efficient algorithms for computing rank/rank decomposition of T?
e.g., Mixture of spherical Gaussians
[Hsu,Kakade’11]
Are we done?
Tensor Rank: Algorithms?
Question: Efficient algorithms for computing rank/rank decomposition of T?
e.g., Mixture of spherical Gaussians
[Hsu,Kakade’11]
Tensor Rank: Uniqueness
Rank decomposition may not be unique!
Fact: Tensor rank decompositions are “generically” unique.
Tensor Rank: Algorithms?
Matrix rank is polytime computable (Gaussian elimination).
Question: Efficient algorithms for computing rank/rank decomposition of T?
Tensor rank is NP-hard.
[Håstad’90,…]
Hope: hardness only holds for tensors with “pathological” components.
Tensor Rank: Jennrich’s Algorithm
Tensor Rank: Jennrich’s Algorithm
Tensor Rank: Jennrich’s Algorithm
Obs2: If g,h are random Gaussians then all eigs are distinct.
Note: The eigenvectors are not pairwise orthogonal, in general.
Tensor Rank: Uniqueness
the min rank decomposition is unique up to scaling + permutation.
Further,
[Harshmann’70]
All known algorithmic results for tensor decomposition also establish uniqueness!
Tensor Rank: Uniqueness
[Harshmann’70]
The failure case is when the components are a root of a non-zero polynomial.
Works for almost all inputs. Enough to beat NP-hardness!
“generic components”
overcomplete regime
Tensor Rank: Algorithms vs Explicit Constructions
explicit constructions* imply formula size lower bounds.
[Raz’10]
the min rank decomposition is unique up to scaling + permutation.
Further,
[Harshmann’70]
[Alexeev-Fobes-Tsimerman’11]
Overcomplete tensor decomposition
[Chen-Rademacher’20]
What we know:
[Koiran’24]
[K-Moitra-Wein’24]
“commuting extensions”
“Koszul-Young Flattenings”
completely elementary analysis.
[Kruskal’77]
can finally match/go beyond the Kruskal uniqueness condition
The main idea
Rank Detection
Such certificates are natural in proving, lower bounds for, say, bilinear computation.
[Garg-Kayal-Saha’20] use ideas from lower bound proofs to give reconstruction algorithms
It seems like any decomposition algorithm also naturally yields such certificates*.
Idea: “from certificates to algorithms”
“shifted partial derivative” certificates 🡪 reconstruction algorithms
[Barak,Brandao,Harrow,Kelner,Steurer,Zhou’16]
[Fleming-K-Pitassi’19]
Reminiscent of “sos certificates to algorithms” paradigm:
*We will come back to this later.
Rank Detection
Idea: reduce to matrix rank (reminiscent of Rohit’s talk yesterday!)
(Rank Detector Gadget)
Rank Detection
[Persu’18]
(Rank Detector Gadget)
[K-Moitra-Wein’24]
+ a decomposition algo based on finding rank 1 matrices planted in generic subspaces
Let’s think about constructing such gadgets.
[Strassen’83]
Trivial Flattening
Our goal is to beat this by a factor ~2.
Koszul-Young Flattening
For rank 1 T:
[Landsberg-Ottaviani’13]
Koszul-Young Flattening
For rank 1 T:
[Landsberg-Ottaviani’13]
Koszul-Young Flattening
For rank 1 T:
[Landsberg-Ottaviani’13]
Both proofs are by elementary are linear algebra.
Koszul-Young Flattening
[Landsberg-Ottaviani’13]
Decomposition Algorithm
Input:
Goal:
Obs:
Key:
We are looking for vectors that have a “rank 1” structure (when viewed as matrices)
Fact:
[Johnston-Lovitz-Vijayraghavan’22]
[Barak-K-Steurer’17]
Closely related to the quantum “best separable state” problem.
[Aaronson-Impagliazzo-Moshkovitz’11]
Decomposition Algorithm
Input:
Goal:
Obs:
Key:
We are looking for vectors that have a “rank 1” structure (when viewed as matrices)
Fact:
[Johnston-Lovitz-Vijayraghavan’22]
[Barak-K-Steurer’17]
Closely related to the quantum “best separable state” problem.
[Aaronson-Impagliazzo-Moshkovitz’11]
[Dastidar-Weicht-Wein’25]
Overcomplete tensor decomposition
[K-Moitra-Wein’24]
“Koszul-Young Flattenings”
completely elementary analysis.
can finally match/go beyond the Kruskal uniqueness condition
Lower Bounds
[K-Moitra-Wein’24]
[Efremenko-Garg-Oliveira-Wigderson’18]
[K-Moitra-Wein’24]
Overcomplete tensor decomposition
[K-Moitra-Wein’24]
“Koszul-Young Flattenings”
completely elementary analysis.
can finally match/go beyond the Kruskal uniqueness condition
Lower Bounds
[K-Moitra-Wein’24]
[Efremenko-Garg-Oliveira-Wigderson’18]
[K-Moitra-Wein’24]
Beating 3n will likely allow improving the construction of .
[Alexeev-Forbers-Tsimerman’11]
Overcomplete tensor decomposition
Can stronger assumptions on the components help?
Tensors with Random Components
Theorem
[Ma-Shi-Steurer’15]
How do they go (so far) beyond the results we could prove in the generic setting?
Tensors with Random Components
Theorem
[Ma-Shi-Steurer’15]
Key Idea:
Observation:
This is (very) not true for order 2 tensors (matrices).
Natural algorithm:
NP-hard in general. But instead, take SDP (“sum of squares”) relaxation.
Analysis reduces to giving a “low degree sum of squares proof” of observation.
Tensors with Random Components
Theorem
[Ma-Shi-Steurer’15]
Key Idea:
Observation:
This is (very) not true for order 2 tensors (matrices).
How far can we go beyond “random”?
Such an algorithm does not certify rank (so no “tensor rank” obstruction).
Smoothed Tensor Decomposition?
Theorem
[Ma-Shi-Steurer’15]
Question: Overcomplete tensor decomposition with smoothed components?
Theorem
[Ma-Shi-Steurer’15]
Key Idea:
Observation:
This is (very) not true for order 2 tensors (matrices).
The proof of the observation relies strongly on approximate orthogonality of random vectors (that is not a generic property). Does not extend to smoothed setting.
Smoothed Tensor Decomposition?
Theorem
[Ma-Shi-Steurer’15]
Smoothed Tensor Decomposition?
Any such result will likely need to obtain exact as opposed to approx recovery.
[Kivva-Potechin’21]
Exact recovery with same parameters for asymmetric, random components.
I’ll briefly describe their approach since it seems sensible for smoothed setting too.
The Kivva-Potechin Approach
Def (Injective and Nuclear Norms of Tensors)
Observe: This does NOT certify that the natural decomposition is a min-rank decomposition.
It only certifies that the natural decomposition is the min nuclear norm decomposition.
Question/Conjecture
Def (Injective and Nuclear Norms of Tensors)
Summary/Open Qs
Via “rank detection gadgets”
Are there better rank detection gadgets/flattenings?
Can we beat the tensor rank barrier for tensors with smoothed components?