Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part II: Langevin Dynamics
We 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$. Tensor PCA exhibits a well-studied information-computation gap: global algorithms such as spectral methods and sum-of-squares work above an algorithmic threshold, below which we know matching lower bounds (against these and some other restricted models of computation). In contrast, local algorithms such as Markov chains…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.38206
curl -X POST /api/v1/records/arxiv/2610.38206/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.38206/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'