Source-linked AI summary
Smoothed Analysis of Tensor Decompositions
Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan
TL;DR
Tensor decomposition is algorithmically difficult, especially when rank exceeds dimension, and existing efficient methods were largely restricted to full-rank settings. The paper uses smoothed analysis to prove robust multiplication of Kruskal rank and obtains stable decomposition and learning algorithms for highly overcomplete, perturbed models. These guarantees extend tensor methods to settings with polynomially many components, while relying on structured perturbations and constant-order constructions.
Problem
Efficient and stable tensor decomposition beyond the full-rank case is limited, despite tensor methods' usefulness for uniquely identifying generative-model parameters.
Method
The paper analyzes perturbed factor matrices through robust Kruskal-rank and Khatri–Rao-product guarantees, then applies the resulting stability to tensor decomposition and learning algorithms.
Results
The algorithm recovers rank-one terms to additive ε error with polynomial running time and exponentially high success probability, and supports learning with more components than dimensions.
Takeaways & Limitations
Smoothed perturbations make tensor methods applicable to highly overcomplete multiview and Gaussian-mixture models.
Takeaways & Limitations
The prior algorithm requires rank(U) = rank(V) = R, while the robust-product analysis uses only ℓ·nR genuinely random perturbation bits and requires additional induction for higher-order products.
Abstract
from arXiv · showhide
Low rank tensor decompositions are a powerful tool for learning generative models, and uniqueness results give them a significant advantage over matrix decomposition methods. However, tensors pose significant algorithmic challenges and tensors analogs of much of the matrix algebra toolkit are unlikely to exist because of hardness results. Efficient decomposition in the overcomplete case (where rank exceeds dimension) is particularly challenging. We introduce a smoothed analysis model for studying these questions and develop an efficient algorithm for tensor decomposition in the highly overcomplete case (rank polynomial in the dimension). In this setting, we show that our algorithm is robust to inverse polynomial error -- a crucial property for applications in learning since we are only allowed a polynomial number of samples. While algorithms are known for exact tensor decomposition in some overcomplete settings, our main contribution is in analyzing their stability in the framework of smoothed analysis. Our main technical contribution is to show that tensor products of perturbed vectors are linearly independent in a robust sense (i.e. the associated matrix has singular values that are at least an inverse polynomial). This key result paves the way for applying tensor methods to learning problems in the smoothed setting. In particular, we use it to obtain results for learning multi-view models and mixtures of axis-aligned Gaussians where there are many more "components" than dimensions. The assumption here is that the model is not adversarially chosen, formalized by a perturbation of model parameters. We believe this an appealing way to analyze realistic instances of learning problems, since this framework allows us to overcome many of the usual limitations of using tensor methods.
1 Introduction
The paper develops smoothed-analysis methods for robust tensor decomposition beyond the full-rank regime, addressing computational hardness and instability in overcomplete settings. Its central result enables polynomial-time decomposition and learning algorithms when perturbed models contain polynomially many components.
- Motivation: Tensor decomposition is useful because tensor factors can be uniquely identified, but rank computation, best rank-one approximation, and spectral norm computation are NP-hard.Matrix decompositions generally recover factors only up to rotation, whereas tensor decompositions can provide uniqueness under conditions such as Kruskal's theorem.
- Motivation: Existing efficient tensor decomposition algorithms were traditionally limited to the full-rank case, motivating stable methods for R = poly(n).The basic polynomial-time theorem requires rank(A) = rank(B) = R and restricts R to at most n for an n × n × n tensor.
- Core result: In smoothed analysis, the Kruskal rank robustly multiplies, enabling tensor decomposition algorithms in the highly overcomplete case for R = poly(n).The result applies when the tensor order is sufficiently large but remains constant, and supports applications to mixtures of Gaussians and multiview models.
- Applications: The framework yields polynomial-time learning algorithms for mixtures with more components than dimensions, including perturbed spherical and axis-aligned Gaussian mixtures and overcomplete multiview models.For perturbed spherical-Gaussian means, the paper handles k = poly(n); the multiview and axis-aligned Gaussian results provide polynomial running time and sample complexity in their stated regimes.
- Core result: For ρ-perturbed factor matrices with R ≤ n^ℓ/2, the Khatri–Rao product has a robust Kruskal-rank guarantee with τ = (n/ρ)^3ℓ.This robust linear independence is the main technical ingredient for stable decomposition under perturbations.
- Algorithmic guarantee: The resulting decomposition algorithm recovers rank-one terms within additive ε error despite entrywise tensor noise at most ε(ρ/n)^3ℓ, in time n^C3ℓ and with probability at least 1 − exp(−Cn^1/3ℓ).The guarantee holds for constant tensor order and smoothed rank-R tensors.
2 Prior Algorithms
Prior work provides polynomial-time tensor decomposition under rank and Kruskal-rank conditions, and its robust extension tolerates bounded perturbations. Flattening higher-order tensors extends these algorithms beyond the directly limited full-rank regime.
- 2 Prior Algorithms: Polynomial-time decomposition recovers unique tensor factors when rank(U) = rank(V) = R and k-rank(W) ≥2.The algorithm preprocesses the tensor and then uses simultaneous diagonalization to recover U and V, followed by a linear system for W.
- 2 Prior Algorithms: Simultaneous diagonalization pairs columns through eigenvalues of Ta(Tb)^−1 and then solves for the remaining factors.Random contractions Ta and Tb yield diagonal forms whose generalized eigenvectors identify corresponding columns.
- 2 Prior Algorithms: The robust algorithm recovers each rank-one term within additive error ϵ when the tensor perturbation is sufficiently small relative to conditioning parameters.The noisy preprocessing uses leading singular vectors to approximate the factor span before running the decomposition procedure.
- 2 Prior Algorithms: Flattening higher-order tensors circumvents the direct requirement R ≤ min(m,n), enabling decomposition through suitable mode groupings and Khatri-Rao products.The resulting corollary applies to order-ℓ tensors and does not require symmetry, provided the grouped factors satisfy the relevant condition.
- 2 Prior Algorithms: The prior approach is limited by rank(U) = rank(V) = R, while the paper seeks stable algorithms for ranks polynomially larger than the dimension.The paper’s smoothed-analysis goal is to show that robust Kruskal rank multiplies under Khatri-Rao products.
3 The Khatri-Rao Product Robustly Multiplies
This section establishes that perturbed Khatri-Rao products retain robust linear independence, yielding inverse-polynomial singular-value guarantees for highly overcomplete tensor decompositions. The proof uses projection and anti-concentration arguments, with explicit probability and dimension trade-offs.
- 3 The Khatri-Rao Product Robustly Multiplies: For ρ-perturbed n × R matrices with R ≤ δn^2, the Khatri-Rao product has robust Kruskal rank R with probability at least 1 − exp(−√n).The robust threshold is τ = n^O(1)/ρ^2.
- 3 The Khatri-Rao Product Robustly Multiplies: For constant-order ℓ-wise products, robust Kruskal rank supports ranks as large as δn^⌊(ℓ−1)/2⌋, enabling highly overcomplete decomposition.The general result requires additional ideas and a delicate induction because perturbed product entries are not independently perturbed.
- 3 The Khatri-Rao Product Robustly Multiplies: The associated product matrix has smallest singular value at least τ, reducing robust independence to lower-bounding projections of perturbed tensor-product vectors.The leave-one-out distance serves as a proxy for the least singular value up to polynomial factors.
- 3 The Khatri-Rao Product Robustly Multiplies: A perturbed product vector has a substantial projection onto any fixed subspace of dimension δn^ℓ, providing the main anti-concentration theorem for the induction.The theorem constructs unit tensors in the subspace and proves a high-probability projection guarantee.
- 3 The Khatri-Rao Product Robustly Multiplies: The projection proof handles correlated perturbations with only ℓnR random bits, but the available probability bounds cannot generally be improved to exponential in n by these methods.Meaningful guarantees require δ to be a small constant or n^−o(1), and dimension-dependent failure limits remain.
- 3.1 Khatri-Rao Product of Two Matrices: The two-factor proof builds structured matrices with orthogonality properties, proves a singular-value bound for Q(ex), and obtains a nontrivial product-vector inner product.The final averaging step gives |Mi(ex ⊗ ey)| ≥ ρθ/n^6 with probability at least 1 − exp(−r/2).
4 Learning Multi-view Mixture Models
Theorem 1.5 yields polynomial-time learning for smoothed, highly overcomplete multi-view mixtures, where independently perturbed parameters support robust tensor decomposition.
- Model: Multi-view models consist of conditionally independent views generated from a shared mixture component, encompassing topic models, HMMs, and random graph mixtures.
- Motivation: Prior polynomial-time guarantees applied only to non-singular settings and could fail at R = n + 1, whereas this result addresses R ≫ n under perturbation.
- Theorem 4.1: Polynomial-time learning handles R = O(n^(ℓ/2−1)) multi-view components when means receive independent Gaussian perturbations.The algorithm learns weights and perturbed parameter vectors under the stated smoothed model.
- Theorem 4.1: The running time and sample complexity are poly_ℓ(n, 1/ρ, 1/ε).
- Algorithm: The algorithm estimates an order-ℓ moment tensor, applies robust tensor decomposition, then normalizes recovered vectors to obtain mixture weights.
5 Learning Mixtures of Axis-Aligned Gaussians
The paper learns smoothed mixtures of many axis-aligned Gaussians by extracting perturbed means and weights from partitioned moments, then solving for diagonal variances.
- Algorithm: The method estimates a partitioned order-ℓ moment tensor, decomposes it to recover perturbed means and weights, and solves linear systems for diagonal variances.
- Recovering the Means and Mixing Weights: Restricting to ℓ distinct coordinates removes mixed noise contributions, leaving products of perturbed means in the moment tensor.
- Recovering the Means and Mixing Weights: The decomposition recovers perturbed means and weights to arbitrary ε accuracy in time poly_ℓ(n, 1/ε), with details handling errors separately.
- Recovering the Means and Mixing Weights: Perturbations support coordinate matching and ensure perturbed vectors have length at least dρ^2/10 with probability at least 1 − exp(−d).
- Recovering the Variances: The variance-recovery linear system is well-conditioned because the relevant flattened tensor columns have smallest singular value at least 1/poly_ℓ(n/ρ).
A Stability of the recovery algorithm
The recovery analysis shows that approximate tensor inputs still yield approximate factors, using projection and robust uniqueness arguments.
- A Stability of the recovery algorithm: The analysis models tensor error and projects factors onto the leading singular subspace before applying robust Kruskal uniqueness.
- A Stability of the recovery algorithm: Repeating the projection argument across modes reduces the problem to an R × R × p tensor while preserving factor accuracy.
Stability of Decompose
Decompose is stable under inverse-polynomial perturbations when factor matrices are well-conditioned and the eigenvalues used in diagonalization are separated.
- Technical correction: The appendix notes an earlier Bauer–Fike argument was insufficient to establish one-to-one eigenvalue matching, requiring a corrected proof under the same conditions.
- Eigenvalue perturbation: If κ(U)(∥ME∥2 + ∥F∥2) < sep(D)/(2n), the perturbed matrix has distinct eigenvalues and is diagonalizable.
- Perturbation analysis: The stability proof treats the observed tensor as an exact tensor plus additive error and derives perturbation bounds for eigendecomposition and recovered factors.
- Separation: Anti-concentration and pairwise separation arguments provide high-probability lower bounds on denominators and eigenvalue gaps.
- Stability condition: Decompose is stable provided U and V are well-conditioned and the eigenvalues of the diagonalized matrices are separated.
B.1 Leave-One-Out Distance
The leave-one-out distance is equivalent to the smallest singular value up to polynomial factors. This reformulation enables conditioning arguments through projections onto orthogonal complements.
- B.1 Leave-One-Out Distance: Leave-one-out distance characterizes the smallest singular value up to polynomial factors.The proof uses the variational characterization of singular values and identifies a vector with a large coordinate.
- B.1 Leave-One-Out Distance: The distance formulation makes well-conditioning easier to analyze through each vector’s projection away from the span of the others.This provides the form used in the main proof.
B.2 Proof of Proposition 3.12
The proof establishes robust structure for two-wise products by combining ordered orthogonality lemmas with singular-vector representations. Anti-concentration then yields a non-negligible response for perturbed tensor-product inputs, which transfers to a row of the original matrix.
- B.2 Proof of Proposition 3.12: The proof combines Lemma 3.16 and Lemma 3.15 to establish how Kruskal rank multiplies for two-wise products in the smoothed setting.The intermediate matrices M1, ..., Mr satisfy the (θ, δ′)-orthogonality property, enabling application of Lemma 3.15.
- B.2 Proof of Proposition 3.12: An ρ-perturbed vector produces norm at least ρθ/n^4 after multiplication by Q(ex) with probability at least 1 − exp(−r/2).Consequently, one term satisfies |M_s(ex⊗ey)| ≥ ρθ/n^5.
- B.2 Proof of Proposition 3.12: A matrix in the top δn^2 right-singular subspace can be written as a combination of rows of M with each weight at most n/τ.This representation implies that at least one row inherits the required non-negligible value.
- B.2 Proof of Proposition 3.12: Top singular vectors with σ_t(M) ≥ η can be expressed as column combinations whose coefficient norms are at most 1/η.This follows from the singular value decomposition and supports transferring properties from constructed matrices to the original matrix.
B.3 Constructing the (θ, δ)-Orthogonal System (Proof of Lemma 3.16)
The construction analyzes a large subspace through blockwise projections and singular vectors. It shows that the resulting projected components collectively provide enough robust dimension to build an ordered (θ, δ)-orthogonal system.
- B.3 Constructing the (θ, δ)-Orthogonal System (Proof of Lemma 3.16): The lemma establishes that the average robust dimension of column projections is large whenever the dimension of V is large.This is the stated purpose of Lemma 3.18 within the construction.
- B.3 Constructing the (θ, δ)-Orthogonal System (Proof of Lemma 3.16): A subspace V of dimension d is represented by an orthonormal basis matrix B and decomposed into block projections B_i across the coordinate blocks.Each B_i is formed by restricting B to the rows associated with one block.
- B.3 Constructing the (θ, δ)-Orthogonal System (Proof of Lemma 3.16): The proof shows that the sum of the selected projection dimensions satisfies Σ_i d_i ≥ d.Assuming the sum is smaller produces a nonzero vector in the intersection of complementary singular-vector subspaces, contradicting σ_d(B) = 1.
- B.3 Constructing the (θ, δ)-Orthogonal System (Proof of Lemma 3.16): Top singular vectors of each block projection can be lifted to vectors for the full matrix using the same small coefficient combinations.The coefficient norms are bounded by √p2, and orthonormality of B preserves the corresponding norm bound.
B.4 Implications of Ordered (θ, δ)-Orthogonality: Details of Proof of Lemma 3.15
The proof develops anti-concentration consequences of ordered orthogonality. Gaussian projections onto suitably separated vectors remain unlikely to fall in small intervals, and the argument extends across conditioning and covariance-side formulations.
- B.4 Implications of Ordered (θ, δ)-Orthogonality: Details of Proof of Lemma 3.15: For each vector in an ordered θ-orthogonal system, conditioning on earlier vectors leaves a Gaussian projection with variance at least θ^2.Anti-concentration therefore bounds the probability that the projection lies in a small interval by less than 1/2.
- B.4 Implications of Ordered (θ, δ)-Orthogonality: Details of Proof of Lemma 3.15: The anti-concentration argument remains valid for a shifted Gaussian of the form u + g′.The shift changes the one-dimensional Gaussian mean but preserves the relevant anti-concentration property.
- B.4 Implications of Ordered (θ, δ)-Orthogonality: Details of Proof of Lemma 3.15: The two quadratic-form formulations have identical distributions because M M^T and M^T M share eigenvalues and Gaussians are rotationally invariant.This establishes the correspondence between the vector-space and coordinate-space versions of the argument.
- B.4 Implications of Ordered (θ, δ)-Orthogonality: Details of Proof of Lemma 3.15: Applying the conditional bound across the ordered vectors yields the lemma’s joint anti-concentration conclusion.The proof invokes Lemma B.3 to combine the bounds under successive conditioning.
C.1 Sampling Error Estimates for Multi-view Models
This section derives sampling-error estimates for ℓ-order tensors formed from multi-view models. With bounded sample vectors, O(ε^-2√(ℓ log n)) samples suffice for the stated high-probability accuracy guarantee.
- C.1 Sampling Error Estimates for Multi-view Models: The analysis studies error in the ℓth moment tensor of a multi-view model.
- C.1 Sampling Error Estimates for Multi-view Models: O(ε^-2√(ℓ log n)) samples suffice for the multi-view tensor estimate with high probability.The result assumes n-dimensional sample vectors with ∥x^(j)∥∞≤1.
- C.1 Sampling Error Estimates for Multi-view Models: The proof bounds each tensor entry using sums of independent bounded random variables and Bernstein inequalities.
- C.1 Sampling Error Estimates for Multi-view Models: Similar sampling-error bounds apply when the multi-view samples are generated from a multivariate Gaussian.
C.2 Error Analysis for Multi-view Models
This section relates closeness between rank-one tensor products to the component vectors themselves. The lemma assumes bounded, nonzero vector norms and decomposes each vector into parallel and orthogonal parts.
- C.2 Error Analysis for Multi-view Models: The error analysis assumes ∥u⊗v−u′⊗v′∥F<δ and norms bounded between Lmin and Lmax.
- C.2 Error Analysis for Multi-view Models: Each vector is decomposed into a component parallel to its counterpart and an orthogonal unit-vector component.
- C.2 Error Analysis for Multi-view Models: The proof uses the closeness of the tensored vectors to analyze the resulting vector components.
C.3 Sampling Error Estimates for Gaussians
This section gives sampling-error estimates for ℓ-order tensors from mixtures of axis-aligned Gaussians and then addresses recovery of mixture weights from approximate tensor components.
- C.3 Sampling Error Estimates for Gaussians: Sampling estimates apply to mixtures of R axis-aligned Gaussians with bounded means and diagonal covariances.The stated sample complexity is polynomial in 1/ε, σ², n, and R.
- C.3 Sampling Error Estimates for Gaussians: The Gaussian error analysis bounds tensor-coordinate products using sub-Gaussian tail inequalities.For bounded means, coordinate products are controlled with high probability before applying the concentration bound.
- C.3 Sampling Error Estimates for Gaussians: A separate lemma addresses approximating a Gaussian component weight from an approximation to wµ^⊗ℓ.
- C.3 Sampling Error Estimates for Gaussians: The weight-recovery result assumes a positive weight and a component mean with norm at least Lmin.