Tensor principal component analysis via sum-of-squares proofs

Abstract

We study a statistical model for the tensor principal component analysis problem introduced by Montanari and Richard: Given a order-$3$ tensor $T$ of the form $T=\tau \cdot v_0^{\otimes 3}+A$, where $\tau \ge 0$ is a signal-to-noise ratio, $v_0$ is a unit vector, and $A$ is a random noise tensor, the goal is to recover the planted vector $v_0$. For the case that $A$ has iid standard Gaussian entries, we give an efficient algorithm to recover $v_0$ whenever $\tau \ge \omega (n^{3/4}\log (n{)}^{1/4})$, and certify that the recovered vector is close to a maximum likelihood estimator, all with high probability over the random choice of $A$. The previous best algorithms with provable guarantees required $\tau \ge \Omega (n)$. In the regime $\tau \le o(n)$, natural tensor-unfolding-based spectral relaxations for the underlying optimization problem break down (in the sense that their integrality gap is large). To go beyond this barrier, we use convex relaxations based on the sum-of-squares method. Our recovery algorithm proceeds by rounding a degree-$4$ sum-of-squares relaxations of the maximum-likelihood-estimation problem for the statistical model. To complement our algorithmic results, we show that degree-$4$ sum-of-squares relaxations break down for $\tau \le O(n^{3/4}/\log (n{)}^{1/4})$, which demonstrates that improving our current guarantees (by more than logarithmic factors) would require new techniques or might even be intractable. Finally, we show how to exploit additional problem structure in order to solve our sum-of-squares relaxations, up to some approximation, very efficiently. Our fastest algorithm runs in nearly-linear time using shifted (matrix) power iteration and has similar guarantees as above. The analysis of this algorithm also confirms a variant of a conjecture of Montanari and Richard about singular vectors of tensor unfoldings.

arXiv commentpublished in Conference on Learning Theory (COLT) 2015 (submitted February 2015)

References in corpus (1)

• Convergence of SDP hierarchies for polynomial optimization on the hypersphere

Cited by in corpus (19)

• Algorithmic thresholds for tensor PCA
• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• Computational Barriers to Estimation from Low-Degree Polynomials
• On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition
• Subexponential-Time Algorithms for Sparse PCA
• Field theoretical approach for signal detection in nearly continuous positive spectra II: Tensorial data
• Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere
• Homotopy Analysis for Tensor PCA
• A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration
• Statistical Query Lower Bounds for Tensor PCA
• Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks
• Power Iteration for Tensor PCA
• Mixture Models, Robustness, and Sum of Squares Proofs
• Learning Polynomials of Few Relevant Dimensions
• Matrix Neural Networks
• Positivity-preserving extensions of sum-of-squares pseudomoments over the hypercube
• Strongly Refuting Random CSPs Below the Spectral Threshold
• Deep Markov Spatio-Temporal Factorization
• Algorithms for an Efficient Tensor Biclustering