# Selective Multiple Power Iteration: from Tensor PCA to gradient-based exploration of landscapes

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 43 references that are in the map.
- First posted on arXiv 23 Dec 2021.

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

- [The Loss Surfaces of Multilayer Networks](https://mlsanity.com/paper/1412.0233/) (2014)
- [TensorLy: Tensor Learning in Python](https://mlsanity.com/paper/1610.09555/) (2016)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014)
- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors](https://mlsanity.com/paper/1512.02337/) (2015)
- [The landscape of the spiked tensor model](https://mlsanity.com/paper/1711.05424/) (2017)
- [CP-decomposition with Tensor Power Method for Convolutional Neural Networks Compression](https://mlsanity.com/paper/1701.07148/) (2017)
- [Statistical limits of spiked tensor models](https://mlsanity.com/paper/1612.07728/) (2016)
- [Passed & Spurious: Descent Algorithms and Local Minima in Spiked Matrix-Tensor Models](https://mlsanity.com/paper/1902.00139/) (2019)
- [Who is Afraid of Big Bad Minima? Analysis of Gradient-Flow in a Spiked Matrix-Tensor Model](https://mlsanity.com/paper/1907.08226/) (2019)
- [Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inference](https://mlsanity.com/paper/1812.09066/) (2018)
- [Complex energy landscapes in spiked-tensor and simple glassy models: ruggedness, arrangements of local minima and phase transitions](https://mlsanity.com/paper/1804.02686/) (2018)
- [The Kikuchi Hierarchy and Tensor PCA](https://mlsanity.com/paper/1904.03858/) (2019)
- [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)
- [Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection](https://mlsanity.com/paper/2009.05870/) (2020)
- [Online and Differentially-Private Tensor Decomposition](https://mlsanity.com/paper/1606.06237/) (2016)
- [Classical and Quantum Algorithms for Tensor Principal Component Analysis](https://mlsanity.com/paper/1907.12724/) (2019)
- [Tensor decomposition to Compress Convolutional Layers in Deep Learning](https://mlsanity.com/paper/2005.13746/) (2020)
- [Average-Case Integrality Gap for Non-Negative Principal Component Analysis](https://mlsanity.com/paper/2012.02243/) (2020)

## Abstract (arXiv)

We propose Selective Multiple Power Iterations (SMPI), a new algorithm to address the important Tensor PCA problem that consists in recovering a spike bfv0otimes k corrupted by a Gaussian noise tensor bfZ ∈ (ℝn)otimes k such that bfT=√n β bfv0otimes k + bfZ where β is the signal-to-noise ratio (SNR). SMPI consists in generating a polynomial number of random initializations, performing a polynomial number of symmetrized tensor power iterations on each initialization, then selecting the one that maximizes langle bfT, bfvotimes k rangle. Various numerical simulations for k=3 in the conventionally considered range n ≤ 1000 show that the experimental performances of SMPI improve drastically upon existent algorithms and becomes comparable to the theoretical optimal recovery. We show that these unexpected performances are due to a powerful mechanism in which the noise plays a key role for the signal recovery and that takes place at low β. Furthermore, this mechanism results from five essential features of SMPI that distinguish it from previous algorithms based on power iteration. These remarkable results may have strong impact on both practical and theoretical applications of Tensor PCA. (i) We provide a variant of this algorithm to tackle low-rank CP tensor decomposition. These proposed algorithms also outperforms existent methods even on real data which shows a huge potential impact for practical applications. (ii) We present new theoretical insights on the behavior of SMPI and gradient descent methods for the optimization in high-dimensional non-convex landscapes that are present in various machine learning problems. (iii) We expect that these results may help the discussion concerning the existence of the conjectured statistical-algorithmic gap.