Conference on Learning Theory · 2015 · 95 citations · 18 references
ComputingComputer ScienceMathematicsAlgorithmsMachine LearningProbability TheoryConvex OptimizationMatrix ComputationMaximum Likelihood EstimationPrincipal Component AnalysisConvex RelaxationsMaximum Likelihood EstimatorRandom Matrix TheoryRandom NoiseSignal-to-noise RatioSum-of-squares ProofsTensor DecompositionsTensor Factorization
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 = τ · v⊗3 0 + A, where τ > 0 is a signal-to-noise ratio, v0 is a unit vector, and A is a random noise tensor, the goal is to recover the planted vector v0. For the case that A has iid standard Gaussian entries, we give an efficient algorithm to recover v0 whenever τ > ω(n3/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 τ > Ω(n). In the regime τ 6 o(n), natural tensor-unfolding-based spectral relaxations for the underlying optimization problem break down. 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-ofsquares 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 τ 6 O(n3/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-ofsquares 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.
18
A Tensor Spectral Approach to Learning Mixed Membership Community Models
Animashree Anandkumar, Rong Ge, Daniel Hsu et al. · arXiv (Cornell University) · 2013 · 110 citations · Full text
Rounding sum-of-squares relaxations
Boaz Barak, Jonathan A. Kelner, David Steurer · 2014 · 103 citations