PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors

Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer

arXiv:1512.02337v2cs.DScs.CCcs.LGstat.ML

TL;DR

The paper addresses whether sum-of-squares-level guarantees for planted sparse recovery and overcomplete tensor problems can be obtained without costly semidefinite programming. It develops fast spectral algorithms using the same high-degree information, achieving comparable guarantees with near-linear or linear runtimes.

  • Problem

    Sum-of-squares methods provide strong guarantees for planted sparse vectors and overcomplete tensor problems, but their computational costs are too high for large instances.

  • Method

    The paper replaces semidefinite programming with spectral algorithms that exploit the same high-degree information as corresponding sum-of-squares methods.

  • Results

    Across the studied problems, the algorithms achieve the same or similar guarantees as sum-of-squares with significantly faster running times, including near-linear planted sparse recovery and tensor decomposition up to approximately d^4/3 components.

  • Takeaways & Limitations

    Spectral algorithms can use information associated with higher sum-of-squares degrees without incurring the corresponding n^O(d) runtime.

  • Takeaways & Limitations

    The paper notes that SoS lower bounds for tensor PCA, tensor prediction, and sparse PCA indicate limits on stronger spectral guarantees, while several other SoS applications remain open for acceleration.

Abstract

from arXiv · show

We consider two problems that arise in machine learning applications: the problem of recovering a planted sparse vector in a random linear subspace and the problem of decomposing a random low-rank overcomplete 3-tensor. For both problems, the best known guarantees are based on the sum-of-squares method. We develop new algorithms inspired by analyses of the sum-of-squares method. Our algorithms achieve the same or similar guarantees as sum-of-squares for these problems but the running time is significantly faster. For the planted sparse vector problem, we give an algorithm with running time nearly linear in the input size that approximately recovers a planted sparse vector with up to constant relative sparsity in a random subspace of $\mathbb R^n$ of dimension up to $\tilde Ω(\sqrt n)$. These recovery guarantees match the best known ones of Barak, Kelner, and Steurer (STOC 2014) up to logarithmic factors. For tensor decomposition, we give an algorithm with running time close to linear in the input size (with exponent $\approx 1.086$) that approximately recovers a component of a random 3-tensor over $\mathbb R^n$ of rank up to $\tilde Ω(n^{4/3})$. The best previous algorithm for this problem due to Ge and Ma (RANDOM 2015) works up to rank $\tilde Ω(n^{3/2})$ but requires quasipolynomial time.

1 Introduction

The paper develops fast spectral algorithms that exploit high-degree information used by sum-of-squares methods without semidefinite programming. Across planted sparse recovery, overcomplete tensor decomposition, and tensor PCA, the algorithms retain comparable guarantees with quasi-linear or linear running times.

  • 1 Introduction: The motivation is that SoS runtimes grow as n^O(d), and even constant-degree semidefinite programs are prohibitively slow for large instances.The paper positions spectral methods as a way to use higher-degree information without paying the full hierarchy cost.
  • 1 Introduction: The algorithms match or closely match sum-of-squares guarantees while avoiding semidefinite programming and achieving quasi-linear or near-linear running times.They exploit the same high-degree information as corresponding sum-of-squares algorithms.
  • 1.1 Planted sparse vector in random linear subspace: Nearly linear time recovers planted sparse vectors with constant relative sparsity in random subspaces of dimension up to approximately sqrt(n), matching prior guarantees up to polylogarithmic factors.The stated runtime is approximately O~(nd), with accuracy η ≤ O(ε^1/4) + o_n→∞(1).
  • 1.2 Overcomplete tensor decomposition: Close-to-linear-time tensor decomposition handles random overcomplete 3-tensors with up to approximately d^4/3 components, approaching the d^1.5 regime of a quasipolynomial-time method.For the single-component problem, the runtime is O~(min{d^(1+ω), d^3.257}).
  • 1.3 Tensor principal component analysis: Linear-time tensor PCA achieves the stated signal-to-noise guarantee with runtime O(d^3), improving the previous near-linear-time complexity while matching its signal-to-noise guarantees.The theorem requires τ ≥ O(n^3/4/η · log^1/2 n).
  • 1.4 Related work: The methods remain bounded by known SoS lower bounds for tensor PCA, tensor prediction, and sparse PCA, limiting expectations for stronger spectral guarantees.The authors also identify speeding up additional SoS applications as an open direction.

2 Techniques

The paper replaces expensive sum-of-squares searches with carefully designed spectral matrices, then compresses those matrices using partial traces while preserving planted-signal information. This yields faster algorithms for planted sparse vectors, overcomplete tensor decomposition, and tensor PCA.

  • Spectral algorithms construct specific matrix polynomials and compute top eigenvectors, accessing higher-degree information without searching over matrix representations by semidefinite programming.The construction is inspired by SoS certificates but avoids the SDP optimization step.
  • Compressing matrices with partial traces: Partial traces compress large SoS-inspired matrices while, in favorable random-noise settings, preserving the signal-to-noise ratio and reducing eigenvector computation to smaller matrices.For a planted rank-one signal plus tensor-product noise, a d^2 × d^2 matrix can become a d × d matrix when the traced noise remains controlled.
  • 2.1 Planted sparse vector in random linear subspace: For planted sparse vectors, centering the partial-trace matrix makes the no-case noise norm at most O(d/n^3/2), enabling distinction when k ≪ n and d ≪ √n.In the yes case, the planted vector produces a Rayleigh quotient at least 1/k, while centering causes cancellations in the no case.
  • 2.2 Overcomplete tensor decomposition: For overcomplete tensor decomposition, the spectral method is a low-degree analogue of the SoS algorithm and handles tensors with up to n = ˜Ω(d^1.5) components in the stated robustness analysis.The method is designed to recover a component despite noise and can apply to less well-behaved components.
  • 2.3 Tensor principal component analysis: For tensor PCA, partial-trace improvements reduce the previous subquadratic approach to a linear-time algorithm while retaining the signal-to-noise threshold τ ≫ d^3/4 log(d)^1/4.The earlier d^2 × d^2 eigenvector computation required ˜O(d^4 log n) time for input size d^3; the improvement is described as linear time.

3 Preliminaries

The preliminaries establish notation for vectors, matrices, tensors, norms, inner products, probability, and asymptotic bounds used throughout the paper.

  • Vectors and tensors are represented over R^n, with standard basis, orthogonal complements, tensor products, and multilinear evaluations defined explicitly.
  • Tensor flattening reinterprets a tensor as a matrix, with three possible flattenings for an order-3 tensor.
  • The paper uses standard inner-product, ℓ_p-norm, operator-norm, Gaussian-distribution, overwhelming-probability, and polylogarithmic asymptotic notation.

4 Planted sparse vector in random linear subspace

This section develops a nearly-linear-time spectral algorithm for recovering a sparse vector planted in a random linear subspace. Under a dimension bound near sqrt(n), the top eigenvector achieves high correlation with the planted vector.

  • 4 Planted sparse vector in random linear subspace: The algorithm recovers the planted sparse vector in nearly-linear time by computing leverage scores and the top eigenvector of a constructed matrix.The implementation computes leverage scores in O(nd), while repeated matrix-vector multiplication yields the top eigenvector efficiently.
  • 4 Planted sparse vector in random linear subspace: When d <= n^1/2/polylog(n), the top eigenvector u satisfies ⟨Su, v0⟩^2 >= 1 − O(ε^1/4) − o(1) with overwhelming probability.
  • 4 Planted sparse vector in random linear subspace: The analysis assumes a sparse planted direction together with independent Gaussian random directions spanning the remaining subspace.
  • 4 Planted sparse vector in random linear subspace: The proof shows robustness to replacing a favorable non-orthogonal basis with an arbitrary orthogonal basis for the same subspace.

Let a′

The proof establishes concentration and orthogonalization properties that connect the algorithm’s arbitrary orthogonal basis to a favorable basis exposing the planted vector. These bounds yield the final correlation guarantee.

  • Let a′: A near-identity Gram-matrix bound implies that the orthogonalization error is negligible when d is o(n).
  • Let a′: The top eigenvector of the constructed matrix correlates with the rotated planted coefficient vector, producing correlation at least 1 − O(ε^1/4) − o(1) with v0.
  • Let a′: The proof bounds the principal submatrix and cross terms separately, then combines them by triangle inequalities to establish the needed operator-norm estimates.
  • Let a′: Matrix Bernstein and Gaussian concentration bounds control the random blocks contributing to the leverage-score matrix when d <= n^1/2/polylog(n).
  • Let a′: Orthogonalization changes the leverage-score structure only mildly, allowing the analysis to transfer from the favorable basis to the basis supplied to the algorithm.The proof uses concentration to show the relevant Gram matrices are close to identity and controls the resulting basis transformation.

5 Overcomplete tensor decomposition

The section develops a spectral algorithm for random overcomplete 3-tensor decomposition by separating signal and crossterms in a carefully constructed matrix. It recovers components for rank up to approximately d^4/3/polylog d with substantially faster runtimes than quasipolynomial SoS-based approaches.

  • 5 Overcomplete tensor decomposition: The algorithm solves random tensor decomposition for d ≤ n ≤ d^4/3/polylog d in time approximately n·min{d^(1+ω), d^3.257} for all components.The single-component runtime is approximately min{d^(1+ω), d^3.257}.
  • 5 Overcomplete tensor decomposition: Local search can improve the initial recovered vectors to arbitrarily high precision and provides a polynomial-time refinement procedure.The spectral algorithm supplies the initialization required by local convergence analyses.
  • 5 Overcomplete tensor decomposition: The method constructs a matrix whose diagonal terms reveal one component while cross terms are controlled when n ≪ d^4/3.The analysis decomposes M into Mdiag and Mcross, showing the cross-term spectral norm is negligible relative to the diagonal spectral gap.
  • 5 Overcomplete tensor decomposition: The top eigenvector is correlated with some a_i⊗a_i, enabling recovery of a component and then vectors close to the original a_i.Theorem 5.3 provides the spectral correlation guarantee, while the algorithmic reduction obtains vectors close to the components.

6 Tensor principal component analysis

The section presents a partial-trace spectral algorithm for recovering a planted component in the order-3 spiked tensor model. It achieves linear time and sublinear space while recovering the signal at the stated signal-to-noise threshold.

  • 6 Tensor principal component analysis: Compared with prior near-linear algorithms, the partial-trace approach simplifies the analysis and improves runtime by a factor of log n.The signal-to-noise guarantees match the prior result cited in the section.
  • 6 Tensor principal component analysis: The partial-trace algorithm recovers v with correlation at least 1−O(ε) when τ ≥ Cn^3/4 log(n)^1/2/ε.The guarantee holds with high probability over the Gaussian noise.
  • 6 Tensor principal component analysis: The algorithm runs in linear time and sublinear space for an input tensor of size n^3.It computes an n×n partial-trace matrix and returns its top eigenvector.
  • 6 Tensor principal component analysis: The partial trace converts the tensor into a matrix whose signal dominates the noise and has a usable spectral gap.The matrix power method then computes the top eigenvector efficiently.

A.1 Linear algebra

This appendix section collects linear-algebra tools used to analyze spectral algorithms, including inequalities for PSD matrices, gapped matrices, and tensor-to-matrix reshaping. These lemmas connect quadratic-form or tensor correlations to eigenvector and singular-vector correlations.

  • A.1 Linear algebra: PSD Cauchy–Schwarz bounds control sums of matrix blocks and quadratic forms in the spectral analyses.The appendix applies the inequality to block-matrix expressions involving sums such as Σ p_iq_i.
  • A.1 Linear algebra: The auxiliary concentration tools rely on standard Gaussian concentration and matrix inequalities for controlling random matrix spectra.These results support the later spectral-gap arguments.
  • A.1 Linear algebra: The top-eigenvector lemma converts a quadratic-form gap into a lower bound on correlation with a target vector.For a symmetric matrix with a top singular vector u, a suitable bound implies ⟨u,v⟩^2 ≥ ε·∥v∥^2.
  • A.1 Linear algebra: A reshaped vector close to v⊗v has singular vectors correlated with the underlying vector v.The lemma applies when ⟨Mu,v⊗v⟩ is sufficiently large relative to ∥u∥ and ∥v∥.

A.2.1 For scalar-valued polynomials of Gaussians

This appendix develops concentration tools for Gaussian polynomials and random matrices. It combines Gaussian moment and tail estimates with a truncated matrix Bernstein inequality for sums whose summands may have unfavorable tails.

  • A.2.1 For scalar-valued polynomials of Gaussians: Standard Gaussian tail estimates are recorded to support the concentration arguments.The appendix repeats the proofs for reference.
  • A.2.1 For scalar-valued polynomials of Gaussians: Gaussian polynomial concentration supplies polylogarithmic tail bounds for constant-degree polynomials evaluated on independent Gaussian variables.The appendix uses these bounds for operator norms and related matrix-valued quantities.
  • A.2.1 For scalar-valued polynomials of Gaussians: The appendix computes expectations of Gaussian polynomial expressions using symmetry and moments of chi-squared variables.These calculations provide explicit formulas for matrix expectations involving norms and outer products.
  • A.2.1 For scalar-valued polynomials of Gaussians: The resulting bounds are evaluated at polylogarithmic truncation levels to make the tail contribution negligible.The construction uses R=polylog n in the matrix concentration framework.
  • A.2.1 For scalar-valued polynomials of Gaussians: The truncated Matrix Bernstein proposition bounds the operator norm of sums of independent random matrices after controlling summand tails and variance parameters.The proof truncates centered summands and applies a noncommutative Bernstein inequality.

B Concentration bounds for planted sparse vector in random linear subspace

This section develops concentration estimates for Gaussian quantities used in the planted sparse vector analysis, including block-matrix components and inverse-matrix approximations.

  • The block matrix has a structured decomposition that supports the subsequent concentration analysis.
  • The Gaussian vector c has norm at most ˜O((d/n)^{1/2}) with overwhelming probability.
  • When d=o(n), the relevant matrix inverse differs from the identity by at most ˜O((d/n)^{1/2}) in spectral norm.
  • The inverse estimates follow by applying elementary expansions for reciprocal and inverse-square-root factors.

Orthogonal subspace basis

This section analyzes an orthogonal-subspace basis through block-matrix inversion and concentration of Gaussian matrix components, yielding high-probability norm estimates.

  • The proof bounds quadratic and cross terms using concentration, Cauchy-Schwarz, and separation of v(i) from b_i.
  • A Neumann-series argument reduces the inverse approximation to controlling a quadratic form, which is bounded by ˜O((1/n)^{1/2}) with overwhelming probability.
  • The key block-matrix calculation uses the Sherman-Morrison formula after inverting a block with a 1 × 1 identity component.
  • For Gaussian vectors a_i=(v(i),b_i), the matrix B is close to the identity and the vector c has norm controlled by d/n with overwhelming probability.
  • Standard concentration gives ∥B−1−I_d∥ at most ˜O((d/n)^{1/2}) when d=o(n).

C Concentration bounds for overcomplete tensor decomposition

This section establishes concentration facts for Gaussian vectors, polynomial expressions, covariance sums, and matrices arising in overcomplete tensor decomposition.

  • The concentration toolkit combines standard Gaussian facts with truncation and matrix Bernstein inequalities for dependent polynomial and matrix-valued terms.
  • Gaussian inner products, norms, and quadratic forms concentrate sufficiently to support uniform bounds after union bounds over indices or pairs.
  • A degree-4 Gaussian polynomial is controlled by its expectation and a polynomial concentration lemma, yielding the required tail bound.
  • Sums of Gaussian outer products concentrate around their expectations when n=Ω(d), using a truncated matrix Bernstein inequality.
  • The tensor proof bounds matrix terms by conditioning on vectors, computing variance, truncating Gaussian polynomials, and applying Bernstein concentration.
  • The resulting bounds apply uniformly with overwhelming probability through concentration of vector norms and a union bound.

C.0.3 Proof of Fact C.4

This section derives the covariance identity for rotationally symmetric Gaussian fourth moments by restricting attention to the symmetric tensor subspace and exploiting rotational invariance.

  • Rotational symmetry implies that the operator acts nontrivially only on the symmetric subspace and has a scalar structure there.
  • The scalar coefficient is characterized using fourth moments along orthogonal unit vectors and rotational invariance.
  • The symmetric-subspace representation uses eigendecomposition, with Frobenius norm and trace determined by the eigenvalues.
  • For Gaussian x, the fourth-moment operator satisfies Σ=2Π_sym+ΦΦ^⊤.
  • The analysis extends from Gaussian vectors to normalized spherical vectors and verifies pseudoinverse identities on the symmetric subspace.
  • These covariance identities support subsequent concentration claims for tensorized Gaussian vectors.

C.0.4 Proof of Lemma 5.9

The proof reduces the general subset case to S = [n], then applies spectral concentration after normalizing quadratic Gaussian vectors into isotropic constant-norm vectors. This yields the stated high-probability spectral bound.

  • The proof first reduces the claim for arbitrary S ⊆ [n] to the case S = [n].
  • The vectors ai ⊗ ai are transformed using covariance normalization and length scaling into independent isotropic vectors with a fixed norm.The normalization uses the pseudoinverse square root of the normalized fourth-moment covariance and the diagonal matrix of sample norms.
  • The normalized samples have low incoherence, with pairwise squared correlations bounded by ˜O(1/d).
  • Spectral concentration for independent columns is then applied to bound the deviation of the normalized Gram-type matrix from the identity.

D Concentration bounds for tensor principal component analysis

This section establishes concentration bounds for matrix expressions involving Gaussian matrices. The proof combines truncated matrix Bernstein inequalities, Gaussian tail bounds, and union bounds to obtain high-probability operator-norm estimates.

  • Lemma 6.5 provides high-probability bounds for the concentration quantities needed in tensor principal component analysis.
  • The term ∑i Tr(Ai)Ai is controlled by truncated matrix Bernstein after bounding the tails of Tr(A) and ∥A∥.The proof uses Gaussian and subgaussian tail estimates for the trace and operator norm of a generic matrix sample.
  • The expectation of Tr(Ai)Ai equals the identity matrix, so the concentration argument bounds deviations around Id.
  • A union-bound and tail-integration argument yields a bound of O(n^3/2 log^2 n) for the relevant second-moment quantity.
  • The remaining Gaussian matrix terms are handled with standard operator-norm and trace concentration estimates.
Loading 1512.02337v2…