Preprint · 2015 · Open access
Tensor principal component analysis via sum-of-squares proofs
arXiv (Cornell University) · Published 12 July 2015 · DOI 10.48550/arxiv.1507.03269
In brief
“Tensor principal component analysis via sum-of-squares proofs” is a 2015 preprint by Samuel B. Hopkins and 2 co-authors, published in arXiv (Cornell University). OpenAlex counts 66 citations as of 18 November 2026. It is open access: the full text is free to read at arXiv (Cornell University).
- Citations
- 66
- Most cited in
- 2020 (16)
- References
- 20
- Authors
- 3
Abstract
We study a statistical model for the tensor principal component analysis problem introduced by Montanari and Richard: Given a order-$3$ tensor $T$ of the form $T = τ\cdot v_0^{\otimes 3} + A$, where $τ\geq 0$ is a signal-to-noise ratio, $v_0$ is a unit vector, and $A$ is a random noise tensor, the goal is to recover the planted vector $v_0$. For the case that $A$ has iid standard Gaussian entries, we give an efficient algorithm to recover $v_0$ whenever $τ\geq ω(n^{3/4} \log(n)^{1/4})$, and certify that the recovered vector is close to a maximum likelihood estimator, all with high probability over the random choice of $A$. The previous best algorithms with provable guarantees required $τ\geq Ω(n)$. In the regime $τ\leq o(n)$, natural tensor-unfolding-based spectral relaxations for the underlying optimization problem break down (in the sense that their integrality gap is large). To go beyond this barrier, we use convex relaxations based on the sum-of-squares method. Our recovery algorithm proceeds by rounding a degree-$4$ sum-of-squares relaxations of the maximum-likelihood-estimation problem for the statistical model. To complement our algorithmic results, we show that degree-$4$ sum-of-squares relaxations break down for $τ\leq O(n^{3/4}/\log(n)^{1/4})$, which demonstrates that improving our current guarantees (by more than logarithmic factors) would require new techniques or might even be intractable. Finally, we show how to exploit additional problem structure in order to solve our sum-of-squares relaxations, up to some approximation, very efficiently. Our fastest algorithm runs in nearly-linear time using shifted (matrix) power iteration and has similar guarantees as above. The analysis of this algorithm also confirms a variant of a conjecture of Montanari and Richard about singular vectors of tensor unfoldings.
Cite this paper
Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.
APA 7
Hopkins, S. B., SHI, J. J., & Steurer, D. (2015). Tensor principal component analysis via sum-of-squares proofs. arXiv (Cornell University). https://doi.org/10.48550/arxiv.1507.03269
MLA 9
Hopkins, Samuel B., et al. “Tensor principal component analysis via sum-of-squares proofs.” arXiv (Cornell University), 2015. https://doi.org/10.48550/arxiv.1507.03269.
Chicago
Hopkins, Samuel B., Jonathan Jingsheng SHI, and David Steurer. 2015. “Tensor principal component analysis via sum-of-squares proofs.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.1507.03269.
Harvard
Hopkins, S. B., SHI, J. J. and Steurer, D. (2015) ‘Tensor principal component analysis via sum-of-squares proofs’, arXiv (Cornell University). doi:10.48550/arxiv.1507.03269.
IEEE
S. B. Hopkins, J. J. SHI, and D. Steurer, “Tensor principal component analysis via sum-of-squares proofs,” arXiv (Cornell University), 2015, doi: 10.48550/arxiv.1507.03269.
BibTeX
@misc{hopkins2015tensor,
title = {{Tensor principal component analysis via sum-of-squares proofs}},
author = {Hopkins, Samuel B. and SHI, Jonathan Jingsheng and Steurer, David},
howpublished = {arXiv (Cornell University)},
year = {2015},
doi = {10.48550/arxiv.1507.03269},
url = {https://doi.org/10.48550/arxiv.1507.03269}
}
Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)
Citations by year
| Year | Citations | Share of the best year |
|---|---|---|
| 2017 | 5 | |
| 2018 | 6 | |
| 2019 | 4 | |
| 2020 | 16 | |
| 2021 | 7 | |
| 2022 | 8 | |
| 2023 | 2 | |
| 2024 | 2 | |
| 2025 | 4 | |
| 2026 | 1 |
Topic and keywords
Physical Sciences › Mathematics › Computational Mathematics › Tensor decomposition and applications
- tensor principal component analysis
- sum-of-squares relaxation
- maximum likelihood estimation
- convex relaxation
- signal-to-noise ratio
Work with this paper
Most-cited papers in Mathematics
- Random ForestsLeo Breiman · Machine Learning · 2001 · 142,830 citations
- Controlling the False Discovery Rate: A Practical and Powerful Approach to Multiple TestingYoav Benjamini, Yosef Hochberg · Journal of the Royal Statistical Society Series B (Statistical Methodology) · 1995 · 113,923 citations
- Fitting Linear Mixed-Effects Models Using lme4Douglas M. Bates, Martin Maechler, Benjamin M. Bolker and 1 more · Journal of Statistical Software · 2015 · 100,328 citations
- The moderator-mediator variable distinction in social psychological research: Conceptual, strategic, and statistical considerations.Reuben M. Baron, David A. Kenny · Journal of Personality and Social Psychology · 1986 · 95,866 citations
- Using multivariate statisticsBarbara Gerson Tabachnick, Linda S. Fidell · 1983 · 79,867 citations
Questions about this paper
How do I cite this paper in APA style?
Hopkins, S. B., SHI, J. J., & Steurer, D. (2015). Tensor principal component analysis via sum-of-squares proofs. arXiv (Cornell University). https://doi.org/10.48550/arxiv.1507.03269
How many times has this paper been cited?
66 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 arXiv (Cornell University): sign in and open the PDF from this page.
Who wrote this paper?
Samuel B. Hopkins, Jonathan Jingsheng SHI, David Steurer.
What is the DOI of this paper?
10.48550/arxiv.1507.03269, permanently at https://doi.org/10.48550/arxiv.1507.03269. 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.