Selective Multiple Power Iteration for Tensor PCA

par Mohamed Ouerfelli (LIST, CEA Saclay)

mercredi 13 oct. 2021, 14:00 → 15:00 Europe/Paris

https://greenlight.lal.cloud.math.cnrs.fr/b/fab-49u-gkt

We will present Selective Multiple Power Iterations (SMPI), a new gradient descent-based algorithm that we introduced recently to address the important Tensor PCA problem. This problem consists in recovering a spike $\mathbf{v}_0^{\otimes k}$ corrupted by a Gaussian noise tensor $\mathbf{Z} \in (\mathbb{R}^n)^{\otimes k}$ such that $\mathbf{T}=\sqrt{n} \beta \mathbf{v}_0^{\otimes k} + \mathbf{Z}$ where $\beta$ is the signal-to-noise ratio. Various numerical simulations 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 appearing at low $\beta$ and in which the noise plays a key role for the signal recovery.

These remarkable results may have strong impact on both practical and theoretical applications of Tensor PCA. (i) We provide multiple variants 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 spin glass models and in various machine learning problems. (iii) We expect that these results may help the discussion concerning the existence of the conjectured statistical-algorithmic gap.