Journal article · 2020 · Open access

Algorithmic thresholds for tensor PCA

Gérard Ben Arous, Reza Gheissari, Aukosh Jagannath

The Annals of Probability, 48(4), 2052–2087 · Published 1 July 2020 · DOI 10.1214/19-aop1415

Open PDFView at the publisherCite this paper

In brief

“Algorithmic thresholds for tensor PCA” is a 2020 journal article by Gérard Ben Arous and 2 co-authors, published in The Annals of Probability. OpenAlex counts 143 citations as of 18 November 2026, which puts it in the top 2% of works published in 2020 by citations. It is open access: the full text is free to read at The Annals of Probability.

Citations
143
Most cited in
2026 (31)
Field-weighted impact
8.37
References
46
Authors
3

Abstract

We study the algorithmic thresholds for principal component analysis of Gaussian $k$-tensors with a planted rank-one spike, via Langevin dynamics and gradient descent. In order to efficiently recover the spike from natural initializations, the signal-to-noise ratio must diverge in the dimension. Our proof shows that the mechanism for the success/failure of recovery is the strength of the “curvature” of the spike on the maximum entropy region of the initial data. To demonstrate this, we study the dynamics on a generalized family of high-dimensional landscapes with planted signals, containing the spiked tensor models as specific instances. We identify thresholds of signal-to-noise ratios above which order 1 time recovery succeeds; in the case of the spiked tensor model, these match the thresholds conjectured for algorithms such as approximate message passing. Below these thresholds, where the curvature of the signal on the maximal entropy region is weak, we show that recovery from certain natural initializations takes at least stretched exponential time. Our approach combines global regularity estimates for spin glasses with pointwise estimates to study the recovery problem by a perturbative approach.

Cite this paper

Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.

APA 7

Arous, G. B., Gheissari, R., & Jagannath, A. (2020). Algorithmic thresholds for tensor PCA. The Annals of Probability, 48(4), 2052–2087. https://doi.org/10.1214/19-aop1415

MLA 9

Arous, Gérard Ben, et al. “Algorithmic thresholds for tensor PCA.” The Annals of Probability, vol. 48, no. 4, 2020, pp. 2052–2087. https://doi.org/10.1214/19-aop1415.

Chicago

Arous, Gérard Ben, Reza Gheissari, and Aukosh Jagannath. 2020. “Algorithmic thresholds for tensor PCA.” The Annals of Probability 48 (4): 2052–2087. https://doi.org/10.1214/19-aop1415.

Harvard

Arous, G. B., Gheissari, R. and Jagannath, A. (2020) ‘Algorithmic thresholds for tensor PCA’, The Annals of Probability, 48(4), pp. 2052–2087. doi:10.1214/19-aop1415.

IEEE

G. B. Arous, R. Gheissari, and A. Jagannath, “Algorithmic thresholds for tensor PCA,” The Annals of Probability, vol. 48, no. 4, pp. 2052–2087, 2020, doi: 10.1214/19-aop1415.

BibTeX

@article{arous2020algorithmic,
  title     = {{Algorithmic thresholds for tensor PCA}},
  author    = {Arous, Gérard Ben and Gheissari, Reza and Jagannath, Aukosh},
  journal   = {The Annals of Probability},
  year      = {2020},
  volume    = {48},
  number    = {4},
  pages     = {2052--2087},
  doi       = {10.1214/19-aop1415},
  url       = {https://doi.org/10.1214/19-aop1415}
}

Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)

Citations by year

YearCitationsShare of the best year
20191010
20201616
20211010
20221919
20232020
20241313
20252424
20263131

Its field-weighted citation impact is 8.37: it has been cited 8.37 times as often as the average work of the same field, type and year (1.00 is the world average).

Topic and keywords

Physical Sciences › Mathematics › Statistics and Probability › Random Matrices and Applications

  • tensor principal component analysis
  • Langevin dynamics
  • gradient descent
  • signal-to-noise ratio
  • spin glass
  • approximate message passing
  • high-dimensional inference
  • perturbation analysis

Work with this paper

Most-cited papers in Mathematics

All highly cited Mathematics papers

Questions about this paper

How do I cite this paper in APA style?

Arous, G. B., Gheissari, R., & Jagannath, A. (2020). Algorithmic thresholds for tensor PCA. The Annals of Probability, 48(4), 2052–2087. https://doi.org/10.1214/19-aop1415

How many times has this paper been cited?

143 times, according to OpenAlex on 18 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.

Is this paper free to read?

Yes. It is open access at The Annals of Probability: sign in and open the PDF from this page.

Who wrote this paper?

Gérard Ben Arous, Reza Gheissari, Aukosh Jagannath.

What is the DOI of this paper?

10.1214/19-aop1415, permanently at https://doi.org/10.1214/19-aop1415. Sign in and open it from this page.

Bibliographic data from OpenAlex (CC0), last checked 18 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.