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

with Sam Hopkins, Tselil Schramm, Jonathan Shi. STOC 2016.

abstract

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 \Omega(\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.125$ ) that approximately recovers a component of a random 3-tensor over $\mathbb R^n$ of rank up to $\tilde \Omega(n^{4/3})$ . The best previous algorithm for this problem due to Ge and Ma (RANDOM 2015) works up to rank $\tilde \Omega(n^{3/2})$ but requires quasipolynomial time.

keywords

sum-of-squares method
eigenvalues
tensor computations
machine learning