Sharp Analysis of Power Iteration for Tensor PCA
Not on the map. Why?
Abstract (arXiv)
We investigate the power iteration algorithm for the tensor PCA model introduced in Richard and Montanari (2014). Previous work studying the properties of tensor power iteration is either limited to a constant number of iterations, or requires a non-trivial data-independent initialization. In this paper, we move beyond these limitations and analyze the dynamics of randomly initialized tensor power iteration up to polynomially many steps. Our contributions are threefold: First, we establish sharp bounds on the number of iterations required for power method to converge to the planted signal, for a broad range of the signal-to-noise ratios. Second, our analysis reveals that the actual algorithmic threshold for power iteration is smaller than the one conjectured in literature by a polylog(n) factor, where n is the ambient dimension. Finally, we propose a simple and effective stopping criterion for power iteration, which provably outputs a solution that is highly correlated with the true signal. Extensive numerical experiments verify our theoretical results.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 29 of its 64 references that are in the map. First posted on arXiv 2 Jan 2024.
Builds on
29 of 64 references.
References · 29
- 2016Tensor Decomposition for Signal Processing and Machine Learningcited by 223
- 2014A statistical model for tensor PCAcited by 72
- 2016Efficient tensor completion for color image and video recovery: Low-rank tensor traincited by 61
- 2017Tensor SVD: Statistical and Computational Limitscited by 52
- 2017Estimation of Low-Rank Matrices via Approximate Message Passingcited by 41
- 2020An Optimal Statistical and Computational Framework for Generalized Tensor Estimationcited by 39
- 2015Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectorscited by 38
- 2015Tensor principal component analysis via sum-of-squares proofscited by 35
- 2019Nonconvex Low-Rank Tensor Completion from Noisy Datacited by 35
- 2017The landscape of the spiked tensor modelcited by 34
- 2020Community Detection on Mixture Multi-layer Networks via Regularized Tensor Decompositioncited by 30
- 2020Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limitscited by 29
17 more
- 2016Spectral algorithms for tensor completioncited by 27
- 2017On Polynomial Time Methods for Exact Low Rank Tensor Completioncited by 27
- 2016Tensor Methods and Recommender Systemscited by 24
- 2013Sparse PCA via Covariance Thresholdingcited by 21
- 2016Finite Sample Analysis of Approximate Message Passing Algorithmscited by 20
- 2018Fundamental limits of detection in the spiked Wigner modelcited by 18
- 2022A Non-Asymptotic Framework for Approximate Message Passing in Spiked Modelscited by 18
- 2017Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squarescited by 17
- 2017Exact tensor completion with sum-of-squarescited by 14
- 2019How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCAcited by 14
- 2016Homotopy Analysis for Tensor PCAcited by 12
- 2020Statistical Query Lower Bounds for Tensor PCAcited by 11
- 2015Sum-of-Squares Lower Bounds for Sparse PCAcited by 10
- 2023Approximate message passing from random initialization with applications to mathbbZ2 synchronizationcited by 9
- 2016Online and Differentially-Private Tensor Decompositioncited by 8
- 2022Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Modelscited by 3
- 2023Heteroskedastic Tensor Clusteringcited by 3
Built on by
Citing papers per year: 2024: 2.
2 papers.