PaperlayerView exact revision on arXiv

Source-linked AI summary

Polynomial-time Tensor Decompositions with Sum-of-Squares

Tengyu Ma, Jonathan Shi, David Steurer

arXiv:1610.01980v1cs.DScs.LG

TL;DR

Overcomplete tensor decomposition asks when moment information permits efficient, robust recovery, but some cases required quasi-polynomial time and robust smoothed fourth-moment guarantees were unknown. The paper augments sum-of-squares relaxations with entropy constraints and uses a robust analysis of Jennrich-based rounding, obtaining polynomial-time improvements for random overcomplete 3-tensors and a robust analysis for overcomplete 4-tensors in the smoothed setting.

  • Problem

    Overcomplete tensor decomposition asks when moments permit efficient, robust recovery; some cases required quasi-polynomial time, and robust smoothed fourth-moment guarantees were unknown.

    Source: §1 · pp. 4–5, §1.1 · p. 7

  • Method

    The authors encode surrogate high entropy directly in sum-of-squares relaxations and use a robust sum-of-squares analysis of Jennrich’s algorithm for rounding.

    Source: §1 · p. 5

  • Results

    The framework gives polynomial-time improvements for random overcomplete 3-tensor decomposition and the first robust analysis for overcomplete 4-tensor decomposition in the smoothed setting.

    Source: §1 · pp. 4–5

  • Takeaways & Limitations

    The unified framework achieves—and in many cases surpasses—the previous best guarantees for polynomial-time overcomplete tensor decomposition.

    Source: §1 · p. 4

    The rounding analysis uses simultaneous diagonalization, whose noise tolerance is unlikely to exceed inverse-polynomial in d, and no such tolerance guarantee had previously been shown explicitly.

    Source: §2.2 · p. 14

Abstract

from arXiv · show

We give new algorithms based on the sum-of-squares method for tensor decomposition. Our results improve the best known running times from quasi-polynomial to polynomial for several problems, including decomposing random overcomplete 3-tensors and learning overcomplete dictionaries with constant relative sparsity. We also give the first robust analysis for decomposing overcomplete 4-tensors in the smoothed analysis model. A key ingredient of our analysis is to establish small spectral gaps in moment matrices derived from solutions to sum-of-squares relaxations. To enable this analysis we augment sum-of-squares relaxations with spectral analogs of maximum entropy constraints.

1 Introduction

This part develops a unified sum-of-squares framework for overcomplete tensor decomposition, using robust rounding and entropy-augmented relaxations to obtain polynomial-time results across several settings, and applies it to dictionary learning and polynomial optimization with certifiably unique solutions. For polynomial constraints with ℓ-certifiably unique solutions, it gives a d^O(ℓ)-time algorithm that approximates their images under a polynomial map within 0.1 in Hausdorff distance.

1 Introduction

  • The framework analyzes Jennrich's algorithm as robust sum-of-squares rounding, and its relaxations encode a surrogate notion of maximum entropy for pseudo-distributions.SoS relaxations hallucinate higher-degree moments from lower-degree moments; high pseudo-distribution entropy helps ensure rounding yields a useful solution, and the paper presents this as the first direct encoding of an entropy surrogate in the SoS proof system.Source: §1 · p. 5

1.1 Results for tensor decomposition

  • For orthogonal vectors, recovery requires only error ∥E∥{1},{2,3} ≪ 1, improving on the previous requirement ∥E∥{1},{2},{3} ≪ 1/d.Here ∥E∥{1},{2,3} is the spectral norm of the error tensor viewed as a d-by-d^2 matrix.Source: §1.1 · p. 6
  • For random order-3 tensors, the polynomial-time algorithm improves on quasi-polynomial methods in the rank range between d^4/3 and d^3/2, up to logarithmic factors.Prior work found decompositions in quasi-polynomial time up to rank d^3/2/log^O(1)(d), or in subquadratic input-size time up to d^4/3/log^O(1)(d) [GM15, HSSS16].Source: §1.1 · p. 7
  • For smoothed vectors, a sum-of-squares variant of FOOBI robustly decomposes overcomplete 4-tensors, tolerating polynomial input error with exponentially small failure probability over the smoothing.The algorithm's relative recovery error scales linearly with the relative input error and condition number κ; for smoothed vectors, κ is at least inverse polynomial with exponentially high probability.Source: §1.1 · p. 7
  • For separated vectors, the algorithm tolerates constant spectral error using moments of higher order by a logarithmic factor in the desired accuracy, enabling dictionary learning at constant sparsity.The previous method required moments of order (log n)/log ρ.Source: §1.1 · p. 8
  • For general unit vectors, the algorithm improves runtime to polynomial in input size while requiring the same tensor order as the previous best algorithm.The stated runtime is d^poly((log σ)/ε), versus d^O((log σ)/ε^O(1)+log n) previously [BKS15, Theorem 4.3]; the method can handle 1/3 spectral-norm error.Source: §1.1 · p. 9

1.2 Applications of tensor decomposition

  • For nice sparse-vector distributions, dictionary learning takes polynomial time at constant accuracy and constant dictionary overcompleteness when the relative sparsity parameter is sufficiently small.Theorem 1.7 uses k = O((log σ)/η), τ ≤ k^-O(k), and n^O(k) samples and runtime to recover columns within O(η)^1/2.Source: §1.2 · p. 10

1.3 Polynomial optimization with few global optima

  • For polynomial constraints with solutions that are certifiably unique under a polynomial map P, the paper gives an efficient method to find those solutions under P.Certifiable uniqueness means the solutions' images under P are approximately orthonormal and every feasible solution maps close to one of them, with the implication having a degree-ℓ sum-of-squares proof.Source: §1.3 · p. 10
  • For ℓ-certifiably unique solutions a1, …, an to constraints A, a d^O(ℓ)-time algorithm finds vectors 0.1-close to P(a1), …, P(an) in Hausdorff distance.The guarantee applies to a polynomial map P.Source: §1.3 · p. 10

2 Techniques

The techniques use sum-of-squares relaxations to construct higher-degree moments and adapt classical rounding to settings where direct recovery is difficult. They develop matrix-diagonalization rounding, a robust fourth-order method, and an embedding-based approach for random overcomplete third-order tensors.

2 Techniques

  • Pseudo-distributions matching known moments provide an efficient route to higher moments, while transferring uniqueness from true distributions addresses whether those moments reflect the target decomposition.The paper identifies both computing a matching distribution and ensuring its higher moments are relevant as obstacles.Source: §2 · p. 11

2.1 Rounding pseudo-distributions by matrix diagonalization

  • Jennrich rounding extracts a singular vector from a random-contraction moment matrix, avoiding the strong concentration required by earlier mean-based rounding.A maximum-entropy constraint limits arbitrary bias in the relaxation; the earlier reweighting approach requires logarithmic-degree moments and quasi-polynomial time.Source: §2.1 · pp. 11–13

2.2 Overcomplete fourth-order tensor

  • The fourth-order approach recasts FOOBI’s proof in sum-of-squares form and uses an approximate subspace constraint to handle noise, then whitens a derived tensor to recover the components.The method’s motivation is that FOOBI’s simultaneous-diagonalization subprocedure had no explicit noise-tolerance guarantee.Source: §2.2 · pp. 14–15

2.3 Random overcomplete third-order tensor

  • For uniform unit-sphere vectors with d < n ≤ d^1.5/(log d)^O(1), embedding them via tensor powers into a larger ambient space yields linearly independent vectors.The method generates a sum-of-squares pseudo-distribution on the unit sphere with T as its third-order moments tensor, then extracts order-6 pseudo-moments estimating the moment tensor P.Source: §2.3 · p. 15
  • Constant-degree sum-of-squares arguments verify a required higher-moment condition for rounding, while a spectral-norm condition holds up to a removable spurious eigenspace.The higher-power bound includes an additive term of ˜O(n/d^1.5).Source: §2.3 · pp. 15–16

3 Preliminaries

The preliminaries introduce pseudo-distributions as efficiently optimizable moment objects and sum-of-squares proofs as a way to reason about their constraints. They also give the matrix-constraint notation and soundness rule used later.

3 Preliminaries

  • The preliminaries fix tensor notation for contractions, unfoldings, and their spectral norms, alongside standard vector and matrix norm conventions.For symmetric third-order tensors, the three one-mode-versus-two-mode unfolding norms coincide.Source: §3 · p. 16

3.1 Pseudo-distributions

  • Pseudo-distributions relax pointwise nonnegativity to tests on squared low-degree polynomials, enabling efficient optimization over low-degree moments.Algorithms operate on their moment tensors and associated linear functionals rather than directly on the finitely supported functions.Source: §3.1 · p. 17

3.2 Sum of squares proofs

  • Sum-of-squares proofs provide a sound and complete framework for reasoning about polynomial constraints satisfied by pseudo-distributions.The stated soundness rule transfers a degree-ℓ′ proof of B under A to satisfaction of B at degree ℓ·ℓ′.Source: §3.2 · pp. 18–19

3.3 Matrix constraints and sum-of-squares proofs

  • Matrix positivity can be expressed through sum-of-squares proofs, and a satisfying pseudo-distribution has a positive-semidefinite pseudo-expectation of the certified matrix.The matrix-proof treatment is abridged and simplified for the paper’s purposes.Source: §3.3 · p. 19

4 Rounding pseudo-distributions

The rounding analysis shows when a random contraction of pseudo-moments yields a matrix whose leading eigenvector approximates a target component. It also gives a sum-of-squares accuracy-boosting step for a vector already close to a solution.

4.1 Rounding by matrix diagonalization

  • With probability at least 1/d^O(k), the top eigenvector of a random contraction has squared correlation at least 1−O(ε) with the target vector, under the theorem’s correlation-versus-covariance condition.The condition compares the target’s (k+2)-moment correlation with the pseudo-distribution covariance spectral norm.Source: §4.1 · p. 20
  • The rounding proof separates a target-aligned rank-one contribution from noise and bounds their spectral effects to obtain the eigenvector guarantee.The analysis uses concentration bounds for Gaussian matrix series to control random contractions.Source: §4.1 · pp. 20–22

4.2 Improving accuracy of a found solution

  • A simple boosting technique removes the prior exponential dependence on 1/ε and achieves polynomially small error for a found solution.For nearly isotropic unit vectors, the sum-of-squares argument turns a sufficiently correlated candidate into one with squared correlation at least 1−10ε.Source: §4.2 · pp. 22–23

5 Decomposition with sum-of-squares

The section develops a general SoS decomposition algorithm that uses polynomial transforms to make solutions nearly orthogonal, then applies it to orthogonal and separated tensor components.

5 Decomposition with sum-of-squares

  • The generic SoS algorithm is presented as a reusable building block for orthogonal, separated, random 3-tensor, and robust FOOBI settings.Its key input is a suitable polynomial transformation of the formal variables.Source: §5 · p. 23, §5.1 · p. 24

5.1 General algorithm for tensor decomposition

  • The general algorithm uses a polynomial transform P to make the desired solutions nearly orthogonal, then recovers their images by solving SoS relaxations and rounding pseudo-distributions.The runtime challenge is making the nearly-orthogonal case polynomial-time when P is the identity.Source: §5.1 · p. 24

5.2 Tensors with orthogonal components

  • For orthogonal components, the algorithm recovers each vector up to sign with O(ε^1/2) error, and the sign is determined using the tensor.The theorem states a polynomial-time algorithm for symmetric 3-tensors and orthonormal component sets.Source: §5.2 · pp. 26–27

5.3 Tensors with separated components

  • For separated components, the section gives a polynomial-time algorithm under bounded aggregate covariance and pairwise inner-product conditions, with tensor order constrained by those parameters.The reduction lifts vectors to higher-dimensional tensor powers; reshaping and taking top left singular vectors recovers the original vectors up to sign.Source: §5.3 · p. 28

6 Spectral norms and tensor operations

This section establishes spectral-norm bounds for pseudo-distribution moments and Gaussian tensor contractions, tools used in the paper’s analyses.

6 Spectral norms and tensor operations

  • The section develops spectral-norm bounds for moments of lifted vectors and for random tensor contractions, which it identifies as crucial to the preceding analyses.It also directs readers focused on applications to the random 3-tensor and robust FOOBI sections.Source: §6 · p. 29

6.1 Spectral norms and pseudo-distributions

  • For degree-bounded pseudo-distributions constrained to the unit ball, Theorem 6.1 and its supporting lemmas bound spectral norms of moment matrices.The section also notes that tensoring with a vector of norm at most one does not increase the spectral norm.Source: §6.1 · pp. 29–30

6.2 Spectral norm of random contraction

  • The section derives bounds for Gaussian contractions of order-3 tensors and extends them to contractions across multiple modes under covariance constraints.The stated results include Gaussian vectors with covariance bounded above by the identity.Source: §6.2 · pp. 31–32

7 Decomposition of random overcomplete 3-tensors

This section applies the SoS framework to random overcomplete 3-tensors by lifting component vectors into a symmetric second-order space. The analysis assumes independently sampled unit vectors and bounded spectral noise, and states a high-probability output guarantee.

7 Decomposition of random overcomplete 3-tensors

  • The stated model has n ≤ d^1.5/(log d)^O(1), independently sampled unit vectors, and error tensor spectral norm at most ε.Theorem 1.2 states a high-probability output guarantee over the random vectors.Source: §7 · pp. 32–33
  • The algorithm lifts each component to a symmetric second-order tensor space and projects away the trace direction when defining its transform.The transformed components are used to meet the generic algorithm’s requirements.Source: §7 · p. 33
  • With probability 1−d^−ω(1), the algorithm’s transform and constraints satisfy the requirements of the generic SoS theorem.The proposition identifies the transformed component vectors as projected symmetric tensor squares.Source: §7 · p. 33

8 Robust decomposition of overcomplete 4-tensors

The section gives a robust SoS version of FOOBI for overcomplete 4-tensor decomposition, with error controlled by a condition number. Under smoothed perturbations, the analysis shows the relevant condition numbers are at least inverse-polynomial with high probability.

8 Robust decomposition of overcomplete 4-tensors

  • The proposed SoS version of FOOBI gives a noise-tolerance guarantee governed by condition numbers rather than directly by dimension, unlike prior formal robustness results for FOOBI.The cited discussion says prior FOOBI robustness to noise had not been formally shown.Source: §8 · p. 35

8.3 Condition number under smooth analysis

  • Under the smoothed analysis model, the relevant condition numbers are at least inverse-polynomial with high probability over the random perturbations.The model independently perturbs each component by Gaussian noise.Source: §8 · p. 35, §8.3 · pp. 41, 43

8 Robust decomposition of overcomplete 4-tensors

  • If the noise norm is at most δσ_n(AAT), the recovered vectors have O(δκ(A)) approximation error.The guarantee is stated for the output of Algorithm 3.Source: §8 · pp. 36–37

8.2 Noisy case

  • The noisy-case proof first establishes a noiseless counterpart, then relates the noisy constraints to that noiseless version to obtain the desired conclusion.The section identifies these as the two steps needed to handle noise.Source: §8.2 · p. 39

9 Tensor decomposition with general components

The section develops an improved pseudo-distribution rounding scheme and applies it iteratively to decompose tensors with general components. Its rounding uses moments logarithmic in overcompleteness, enabling a polynomial-time algorithm under the theorem’s stated conditions.

9.1 Improved rounding of pseudo-distributions

  • The improved rounding scheme requires moments of degree logarithmic in the overcompleteness parameter σ.Theorem 9.1 gives a sufficient degree bound of O(1/ε) · log(σ/ε).Source: §9 · p. 43, §9.1 · p. 43
  • With probability at least 1/d^O(s^3), the rounding step returns a top eigenvector whose squared correlation with the target vector is at least 1 − O(ε).The stated probability is over the independent Gaussian vectors used in the rounding step.Source: §9.1 · p. 43

9.2 Finding all components

  • Theorem 1.6 gives a polynomial-time algorithm for decomposing general components under its stated tensor and covariance conditions.The theorem assumes a bound on the sum of component outer products and a sufficiently high even tensor order.Source: §9.2 · p. 47
  • The algorithm iteratively finds a new component within O(ε^1/2) error when a sufficiently separated component remains.The proof uses the rounding theorem at each iteration to obtain a new vector with high probability.Source: §9.2 · p. 49

10 Fast orthogonal tensor decomposition without sum-of-squares

This section presents a fast orthogonal tensor-decomposition algorithm without sum-of-squares, using a Gaussian matrix slice to seed tensor power iteration. It also gives a single-component guarantee under spectral-norm error and an eigenvalue-gap analysis for the slice.

10 Fast orthogonal tensor decomposition without sum-of-squares

  • For spectral norm error at most 1/log d, the algorithm finds a component of an orthogonal 3-tensor in quasi-linear time.The section contrasts this error guarantee with the previous algorithm’s 1/d injective-norm tolerance.Source: §10 · pp. 49, 51
  • The slice’s top eigenvector is O(τ/δ)-close to a component with probability 1/(d^(1+δ)(log d)^O(1)), and its top-to-second eigenvalue ratio is at least 1 + δ/3 − O(τ).These bounds are for the noisy orthogonal-tensor setting stated in Theorem 10.1.Source: §10 · pp. 49–50
  • A Gaussian contraction forms a matrix slice whose leading eigenvector seeds tensor power iteration; repeating the procedure supports finding all components.The analysis states that fast matrix multiplication reduces the runtime for finding all components to d^(1+ω)(log d)^O(1).Source: §10 · pp. 51–52

A Toolbox

The toolbox collects proof ingredients for sum-of-squares reasoning and eigenvector control. It includes an SOS proof of Cauchy–Schwarz and bounds relating nearby vectors and perturbed top eigenvectors.

A Toolbox

  • The appendix records a sum-of-squares proof of the Cauchy–Schwarz inequality for polynomial vectors.The proof notes that the difference between the two sides is a sum of squares.Source: A Toolbox · pp. 55–56
  • A vector close to a unit vector remains nearly orthogonal to vectors constrained to have small correlation with that unit vector.The lemma bounds the correlation after perturbing the reference vector by at most 2δ.Source: A Toolbox · p. 56
  • A matrix close to a rank-one projection along its leading direction has a top eigenvector close to that direction.The proof invokes Davis–Kahan to relate matrix perturbation to eigenvector distance.Source: A Toolbox · pp. 56–57

B Missing proofs in Section 3

These appendices supply missing proofs for the sum-of-squares framework. They explain how to find pseudo-distributions through optimization and how proof derivations and separation arguments support the framework’s claims.

B Missing proofs in Section 3

  • A degree-d pseudo-distribution can be found by optimizing over its moments using linear constraints and semidefinite matrix constraints.The stated runtime is (n + m)^O(d), followed by interpolation to recover the pseudo-distribution.Source: B Missing proofs in Section 3 · p. 57
  • A sum-of-squares derivation of constraints transfers their nonnegativity to pseudo-expectations when the degree bounds are satisfied.The proof expands products of constraints into sums of squares and applies the pseudo-distribution’s defining constraints.Source: B Missing proofs in Section 3 · pp. 57–58
  • Separation of the SOS cone yields a linear functional that, after normalization, defines a pseudo-distribution.The argument uses this construction to obtain a pseudo-distribution satisfying one constraint set but not another.Source: B Missing proofs in Section 3 · p. 58

Related papers

Loading 1610.01980v1…