# Sharp Analysis of Power Iteration for Tensor PCA

arXiv: https://arxiv.org/abs/2401.01047 · HTML: https://mlsanity.com/paper/2401.01047/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 64 references that are in the map.
- First posted on arXiv 2 Jan 2024.

## Builds on (most cited first, 29 of 29)

- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014)
- [Efficient tensor completion for color image and video recovery: Low-rank tensor train](https://mlsanity.com/paper/1606.01500/) (2016)
- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [Estimation of Low-Rank Matrices via Approximate Message Passing](https://mlsanity.com/paper/1711.01682/) (2017)
- [An Optimal Statistical and Computational Framework for Generalized Tensor Estimation](https://mlsanity.com/paper/2002.11255/) (2020)
- [Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors](https://mlsanity.com/paper/1512.02337/) (2015)
- [Tensor principal component analysis via sum-of-squares proofs](https://mlsanity.com/paper/1507.03269/) (2015)
- [Nonconvex Low-Rank Tensor Completion from Noisy Data](https://mlsanity.com/paper/1911.04436/) (2019)
- [The landscape of the spiked tensor model](https://mlsanity.com/paper/1711.05424/) (2017)
- [Community Detection on Mixture Multi-layer Networks via Regularized Tensor Decomposition](https://mlsanity.com/paper/2002.04457/) (2020)
- [Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits](https://mlsanity.com/paper/2005.10743/) (2020)
- [Spectral algorithms for tensor completion](https://mlsanity.com/paper/1612.07866/) (2016)
- [On Polynomial Time Methods for Exact Low Rank Tensor Completion](https://mlsanity.com/paper/1702.06980/) (2017)
- [Tensor Methods and Recommender Systems](https://mlsanity.com/paper/1603.06038/) (2016)
- [Sparse PCA via Covariance Thresholding](https://mlsanity.com/paper/1311.5179/) (2013)
- [Finite Sample Analysis of Approximate Message Passing Algorithms](https://mlsanity.com/paper/1606.01800/) (2016)
- [A Non-Asymptotic Framework for Approximate Message Passing in Spiked Models](https://mlsanity.com/paper/2208.03313/) (2022)
- [Fundamental limits of detection in the spiked Wigner model](https://mlsanity.com/paper/1806.09588/) (2018)
- [Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squares](https://mlsanity.com/paper/1705.02973/) (2017)
- [Exact tensor completion with sum-of-squares](https://mlsanity.com/paper/1702.06237/) (2017)
- [How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCA](https://mlsanity.com/paper/1905.12294/) (2019)
- [Homotopy Analysis for Tensor PCA](https://mlsanity.com/paper/1610.09322/) (2016)
- [Statistical Query Lower Bounds for Tensor PCA](https://mlsanity.com/paper/2008.04101/) (2020)
- [Sum-of-Squares Lower Bounds for Sparse PCA](https://mlsanity.com/paper/1507.06370/) (2015)
- [Approximate message passing from random initialization with applications to mathbbZ2 synchronization](https://mlsanity.com/paper/2302.03682/) (2023)
- [Online and Differentially-Private Tensor Decomposition](https://mlsanity.com/paper/1606.06237/) (2016)
- [Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models](https://mlsanity.com/paper/2211.03827/) (2022)
- [Heteroskedastic Tensor Clustering](https://mlsanity.com/paper/2311.02306/) (2023)

## Built on by (most cited first, 2 of 2)

- [A non-asymptotic distributional theory of approximate message passing for sparse and robust regression](https://mlsanity.com/paper/2401.03923/) (2024)
- [Permutation recovery of spikes in noisy high-dimensional tensor estimation](https://mlsanity.com/paper/2412.14650/) (2024)

## 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.