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

By Boaz Barak, Jonathan A. Kelner, David Steurer. 2014

197 citations recorded by the source corpus.

We give a new approach to the dictionary learning (also known as "sparse coding") problem of recovering an unknown n x m matrix A (for m ≥ n) from examples of the form [y = Ax + e,] where x is a random vector in Rm with at most τ m nonzero coordinates, and e is a random noise vector in Rn with bounded magnitude. For the case m=O(n), our algorithm recovers every column of A within arbitrarily good constant accuracy in time mO(log m/log(τ-1)), in particular achieving polynomial time if τ = m-δ for any δ>0, and time mO(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 √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.

Subfields: Computational Mathematics, Computational Mechanics, Representation & Self-Supervised Learning, Mathematical Optimization, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

In Computational Mechanics

In Representation & Self-Supervised Learning

In Mathematical Optimization

In Signal Processing

Citations in the corpus

Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, background): “There are many existing theoretical works studying algorithm for sparse coding [9, 17, 43, 47, 54, 68, 85, 91, 94], however, these algorithms share little similarity to training a neural network.”
Outlier-robust moment-estimation via sum-of-squares (2017, background): “(Often, a key ingredient of these algorithms in the high-dimensional setting is tensor decomposition [MR05, AFH + 12, AGH + 14, HK13b, BCMV14, BKS15, GM15, MSS16a].)”
Complete dictionary recovery over the sphere (2015, methodology): “2Recent works, including [13, 14], guarantee recovery with (almost) linear sparsity, but run in super-polynomial (quasipolynomial) time.”
Mixture models, robustness, and sum of squares proofs (2017, methodology): “There has been much recent interest in using the SoS method to solve unsupervised learning problems in generative models [7, 8, 31, 36, 49, 56].”
Polynomial-Time Tensor Decompositions with Sum-of-Squares (2016, methodology): “These algorithms lead to the best known provable guarantees for a wide range of unsupervised learning problems [8]– [11], including learning mixtures of Gaussians [12], Latent Dirichlet topic modeling [13], and dictionary learning [14].”