PaperlayerView exact revision on arXiv

Source-linked AI summary

Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method

Boaz Barak, Jonathan A. Kelner, David Steurer

arXiv:1407.1543v2cs.DScs.LGstat.ML

TL;DR

The paper addresses recovery of an unknown dictionary from sparse, noisy linear observations, especially when the signals are denser than prior guarantees allowed. It uses a Sum of Squares semidefinite-programming approach to noisy tensor decomposition and achieves approximate recovery with polynomial time for inverse-polynomial sparsity and quasipolynomial time for sufficiently small constant sparsity. The work also demonstrates the potential of SOS for unsupervised learning problems.

  • Problem

    Dictionary learning seeks to recover an unknown dictionary from observations with sparse coefficients and bounded noise, while prior comparable guarantees required extremely sparse signals.

  • Method

    The paper designs a noisy tensor decomposition algorithm based on the Sum of Squares semidefinite programming hierarchy and applies it to dictionary learning.

  • Results

    Approximate dictionary recovery is polynomial-time when τ = n^-δ and quasipolynomial-time when τ is a sufficiently small constant.

  • Takeaways & Limitations

    The results indicate that Sum of Squares can address unsupervised learning problems in regimes that have eluded other algorithms.

  • Takeaways & Limitations

    Exact recovery is not possible under the paper’s assumptions, and achievable precision is limited without incoherence assumptions.

Abstract

from arXiv · show

We give a new approach to the dictionary learning (also known as "sparse coding") problem of recovering an unknown $n\times m$ matrix $A$ (for $m \geq n$) from examples of the form \[ y = Ax + e, \] where $x$ is a random vector in $\mathbb R^m$ with at most $τm$ nonzero coordinates, and $e$ is a random noise vector in $\mathbb R^n$ with bounded magnitude. For the case $m=O(n)$, our algorithm recovers every column of $A$ within arbitrarily good constant accuracy in time $m^{O(\log m/\log(τ^{-1}))}$, in particular achieving polynomial time if $τ= m^{-δ}$ for any $δ>0$, and time $m^{O(\log m)}$ if $τ$ is (a sufficiently small) constant. Prior algorithms with comparable assumptions on the distribution required the vector $x$ to be much sparser---at most $\sqrt{n}$ nonzero coordinates---and there were intrinsic barriers preventing these algorithms from applying for denser $x$. We achieve this by designing an algorithm for noisy tensor decomposition that can recover, under quite general conditions, an approximate rank-one decomposition of a tensor $T$, given access to a tensor $T'$ that is $τ$-close to $T$ in the spectral norm (when considered as a matrix). To our knowledge, this is the first algorithm for tensor decomposition that works in the constant spectral-norm noise regime, where there is no guarantee that the local optima of $T$ and $T'$ have similar structures. Our algorithm is based on a novel approach to using and analyzing the Sum of Squares semidefinite programming hierarchy (Parrilo 2000, Lasserre 2001), and it can be viewed as an indication of the utility of this very general and powerful tool for unsupervised learning problems.

1 Introduction

The paper develops an SOS-based approach to dictionary learning that approximately recovers dictionary columns for substantially denser signals and under broader noise and dictionary settings than prior rigorous methods. Its noisy tensor decomposition algorithm provides the core tool, with polynomial or quasipolynomial runtime depending on sparsity.

  • Problem: Dictionary learning recovers an unknown dictionary A from observations y = Ax + e, where x is sparse and e has bounded magnitude.The problem is nonlinear because both A and x are unknown, and it remains computationally challenging even without noise.
  • Problem: Prior rigorous guarantees generally required fewer than O(√n) nonzero coordinates, whereas this work handles signals with up to τn nonzero coordinates in some settings.The paper identifies denser signals as a central regime not covered by earlier comparable algorithms.
  • Method: The method uses the Sum of Squares semidefinite programming hierarchy and gives the first rigorous running-time bounds for SOS on a natural unsupervised learning problem.The approach applies SOS to a new noisy tensor decomposition algorithm that underlies dictionary recovery.
  • Results: For τ = n^-δ, a polynomial-time algorithm recovers a set ε-close to the dictionary from n^O(1) samples with probability at least 0.9.The guarantee applies to σ-dictionaries and (d, τ)-nice coefficient distributions, for every ε > 0, σ ≥ 1, and δ > 0.
  • Results: For sufficiently small constant τ, the algorithm still recovers the dictionary but requires quasipolynomial time n^O(log n).The result extends approximate recovery to a relatively dense regime at increased computational cost.
  • Results: The noisy tensor decomposition algorithm tolerates much larger noise than prior approaches, although it requires a higher tensor degree and can produce local minima unrelated to those of the underlying polynomial.This noise tolerance is described as crucial for the dictionary learning application, while exact recovery is not possible under the paper’s assumptions.

Organization of this paper

Sections 4–6 prove the dictionary-learning and tensor-decomposition results in quasipolynomial time, while Section 7 gives polynomial time for sparser coefficients.

  • Sections 4–6 contain the full quasipolynomial-time proofs for dictionary learning and tensor decomposition when τ is a small constant.
  • Section 7 improves the running time to polynomial time when τ ⩽ n−δ for a constant δ > 0.

2 Overview of algorithm and its analysis

The overview reduces dictionary learning to noisy tensor decomposition and explains how SOS pseudo-distributions support recovery despite constant spectral-norm noise. The analysis first treats genuine distributions, then extends the argument to pseudo-distributions.

  • Noisy tensor decomposition: Dictionary learning reduces to noisy tensor decomposition by estimating a polynomial that is spectrally close to ∥A⊤u∥d.The estimated polynomial is formed from samples and remains bounded away from the target tensor when τ is constant.
  • Noisy tensor decomposition: Constant noise requires tensor decomposition that tolerates substantial spectral-norm error, motivating the use of the Sum-of-Squares algorithm.The SOS algorithm solves polynomial systems through semidefinite programming and provides the central computational framework.
  • The SOS algorithm: SOS returns a degree-k pseudo-distribution rather than an actual distribution, while remaining efficiently optimizable through a positive-semidefinite moment matrix.A degree-k pseudo-distribution is represented by moments up to degree k, with squared-polynomial nonnegativity encoded semidefinitely.
  • The SOS algorithm: Figure 1’s basic algorithm outputs a vector ε-close to a column of A with inverse polynomial probability.The parameters k, d, and τ depend on ε and the top eigenvalue σ of A⊤A.
  • Analysis: If the SOS output were an actual distribution, maximizing the polynomial would concentrate it near columns of A and their negations.The first analysis phase shows that the output vector is close to a dictionary column under this genuine-distribution assumption.
  • Analysis: The technical novelty is proving that the same inequalities extend from actual distributions to degree-k pseudo-distributions using only Sum-of-Squares proofs.The argument avoids requiring higher moments of the pseudo-distribution.

3 Preliminaries

The preliminaries define the paper’s polynomial-ordering, norm, dictionary-distance, and pseudo-distribution machinery. They also give moment-matching and reweighting properties used in the SOS analysis.

  • The notation P ⪯ Q means that Q − P is a sum of squares of polynomials.
  • A σ-dictionary has unit-norm columns and spectral norm of A⊤A at most σ.The parameter σ controls the dictionary’s overcompleteness analytically.
  • Symmetrized Hausdorff closeness compares two vector sets through squared correlation, accounting for permutation and sign or scaling ambiguity.
  • A pseudo-distribution of degree at least two admits an efficiently sampleable Gaussian matching its first two moments.The Gaussian is constructed from a Cholesky factorization of the pseudo-distribution’s second-moment matrix.
  • Reweighting by a positive sum-of-squares polynomial produces a lower-degree pseudo-distribution corresponding to probability reweighting.

4 Dictionary Learning

The dictionary-learning result assumes moment conditions on coefficient distributions and reduces recovery to noisy tensor decomposition. It provides quasipolynomial recovery generally and polynomial recovery for inverse-polynomial sparsity.

  • Nice distributions: Nice distributions impose low-order moment, variance, rescaling, symmetry, sparsity, correlation, and cancellation conditions supporting recovery.The conditions include polynomial variance and degree-d non-square-monomial bounds controlled by τ.
  • Dictionary-learning theorem: Theorem 4.2 recovers dictionary columns within ε in symmetrized Hausdorff distance using n^(1/ε)O(1)(d+log m) time and nO(d)/poly(τ) samples.The guarantee applies to σ-overcomplete dictionaries and (d,τ)-nice distributions under the theorem’s degree and τ conditions.
  • Dictionary learning via tensor decomposition: The tensor polynomial is a noisy proxy for the dictionary’s moment structure, with its noise magnitude controlled by the coefficient distribution’s niceness.
  • Noisy tensor decomposition: Noisy tensor decomposition recovers columns within ε when the input degree-d polynomial is τ-close to ∥A⊤u∥d in spectral norm.The algorithm runs in n^(1/ε)O(1)(d+log m) time for degree and noise parameters satisfying the theorem’s conditions.
  • Dictionary learning via tensor decomposition: Sampling sufficiently many examples makes the empirical polynomial close enough to the expected polynomial to apply noisy tensor decomposition and recover A.The proof uses coefficient concentration and obtains the required polynomial approximation from samples.

5 Sampling pseudo-distributions

This section develops a randomized method for extracting vectors correlated with a target direction from low-degree pseudo-distributions. The method uses sum-of-squares polynomials and yields an efficient sampling procedure with quantified runtime and success probability.

  • Algorithm and guarantee: The algorithm applies to any low-degree pseudo-distribution, unlike the generally impossible task of sampling directly from such distributions.This property is a key ingredient in the noisy tensor decomposition algorithm.
  • Algorithm and guarantee: Theorem 5.1 gives a randomized algorithm for sampling pseudo-distributions that outputs a vector c′ correlated with c by at least 1 − O(ε).It applies to degree-k pseudo-distributions satisfying ∥u∥2^2 = 1 and a sufficiently large kth moment in direction c.
  • Runtime and probability: The randomized implementation runs in time n^O(k) and succeeds with probability 2^−k/poly(ε).Independent Gaussian samples are used to construct the output polynomial W0, with the stated probability guarantee.
  • Polynomial construction: The construction forms W from independent Gaussian-derived polynomials conditioned on large projections onto c, then proves its desired expectation and second-moment bounds.The analysis uses a nonnegative univariate polynomial, sum-of-squares reasoning, and a second-moment inequality.
  • Low-degree conversion: A degree-2 pseudo-distribution with squared correlation at least 1 − ε can be converted into a randomized polynomial-time sampler producing unit vectors with constant probability of squared correlation at least 1 − 2ε.The conversion matches the first two moments with a Gaussian distribution and normalizes the sampled vector.

6 Noisy tensor decomposition

This section applies pseudo-distribution sampling to noisy tensor decomposition by iteratively finding vectors associated with dictionary columns. The resulting algorithm achieves approximate recovery under spectral-norm noise with quasi-polynomial dependence on the problem parameters.

  • Column extraction: Large values of ∥Aᵀu∥_d^d imply that some dictionary column c has a large kth pseudo-expectation ⟨c,u⟩^k.Lemma 6.1 formalizes this connection for σ-overcomplete dictionaries.
  • Iterative algorithm: The algorithm iteratively searches for a pseudo-distribution satisfying the sphere constraint and separation constraints from previously found vectors, then samples a new vector c′.The new vector is added to the set S and is required to remain separated from existing elements.
  • Iterative algorithm: The sampled vector c′ is close to a column of A while remaining separated from previously found vectors, enabling progress through the dictionary columns.The proof uses correlation bounds and tensorized vector distances to establish these properties.
  • Termination: The algorithm terminates after at most m iterations because each iteration covers at least one additional column of A.At termination, every column has a nearby vector in S.
  • Varying norms: With varying column norms, the unmodified method generally reconstructs vectors close to maximum-norm columns, while recovering smaller-norm columns requires incoherence assumptions.A modified thresholding procedure can recover smaller-norm columns under sufficiently strong incoherence conditions.

7 Polynomial-time algorithms

The section develops polynomial-time dictionary-learning algorithms by combining SOS-based pseudo-distribution sampling with reweighted sparse-mixture samples. Under suitable niceness and sparsity conditions, the algorithms recover dictionary columns approximately.

  • Polynomial-time dictionary learning: τ = n^−Ω(1) yields a polynomial-time dictionary-learning algorithm for sufficiently nice distributions.The result is stated as Theorem 7.6 for distributions satisfying the required (d, τ)-niceness conditions.
  • Refined sampling: The refined sampling theorem outputs a unit vector c′ under stated pseudo-distribution and SOS-polynomial conditions, with a quantified success guarantee.Its analysis uses moment comparisons and second-moment bounds for a random SOS polynomial.
  • Column identification: A pseudo-distribution satisfying the dictionary correlation constraint guarantees the existence of a column c with sufficiently large higher and second moments.Lemma 7.3 supplies the column-level correlation needed by the sampling procedure.
  • Reweighting construction: Reweighting products of squared sample correlations produces an SOS-polynomial distribution meeting the refined sampling conditions.The construction uses independent samples and coordinate-square reweighting; its variance is polynomially bounded under (4, τ)-niceness.
  • Single-vector recovery: For k = (1/ε) log σ + log(1/τ), the single-vector algorithm runs in n^O(k) time and returns a vector correlated with a dictionary column.For noise τ ≤ O(ε), it uses k samples and succeeds with probability n^−O(k)/poly(ε).
  • Polynomial-time dictionary learning: The polynomial-time theorem outputs an ε-close set of dictionary columns from n^O(d)/poly(τ) samples.The output distance is measured using symmetrized Hausdorff distance.

8 Conclusions and Open Problems

The conclusion presents SOS as useful for unsupervised learning in regimes that have eluded other algorithms, while emphasizing that its generality imposes a steep efficiency cost.

  • Conclusions: The work demonstrates SOS potential for unsupervised learning problems in regimes that have so far eluded other algorithms.The authors identify finding additional problems solvable with SOS as an open direction.
  • Open problems: The generality of SOS comes at a steep cost of efficiency, motivating the search for practically efficient algorithms inspired by the approach.The authors describe this as an open problem and express optimism about pursuing it.

A Proof of Lemma 2.3

The appendix proves a sum-of-squares form of the AM-GM inequality through a sequence of symmetric polynomial inequalities whose successive differences are sums of squares.

  • SOS AM-GM lemma: Lemma 2.3 follows from an SOS version of the AM-GM inequality for nonnegative polynomials.The appendix attributes the first SOS proof of AM-GM to Hurwitz and uses the result as a supporting lemma.
  • Reduction to AM-GM: The proof represents a monomial indexed by a multi-index as a product of repeated polynomial factors, then applies the SOS AM-GM lemma.The factorization enables the desired inequality for the multi-index expression.
  • Chain of inequalities: A chain R0 ⪰ ⋯ ⪰ Rn−1 is established by proving each difference Rk−1 − Rk is a sum of squares.The construction pairs terms differing in two exponents and reduces the argument to a two-variable SOS inequality.
  • Two-variable step: The two-variable reduction is completed because the relevant factors are sums of squares and the squared difference is itself a sum of squares.This establishes the nonnegativity required for every successive difference.
Loading 1407.1543v2…