Annealed Langevin dynamics reach the tensor PCA algorithmic threshold
Original title: Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part II: Langevin Dynamics
Part II says spherical Langevin dynamics with annealing and averaging strongly recover from a random start.
The paper studies tensor PCA on the sphere, recovering an unknown vector from a noisy observation of its k-th tensor power for fixed k at least 3. It says spherical Langevin dynamics with annealing and ergodic averaging achieve polynomial-time strong recovery above the algorithmic threshold from a uniform random initialization. With Part I, the authors argue local Markov chains can match global algorithms down to that threshold from an uninformative cold start.
Unconfirmed: The recovery claim is a theoretical result stated by the authors.
- The setting is spherical tensor PCA with fixed order k at least 3.
- Earlier local methods needed a polynomially higher signal-to-noise ratio.
- The method adds annealing and ergodic averaging to Langevin dynamics.
- This continues Part I, cited as arXiv:2610.16705.
From the original article
1 min read at arxiv.orgWe consider the tensor principal components analysis (tensor PCA) problem on the sphere, in which we are asked to recover an unknown vector in $\mathcal{S}_N=\{x\in\mathbb{R}^N:\lVert x\rVert^2=N\}$ from a noisy observation of its $k$-th tensor power, for a fixed $k\ge3$.
By Aniket Das · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.