Preprint · 2015 · Open access

Tensor principal component analysis via sum-of-squares proofs

Samuel B. Hopkins, Jonathan Jingsheng SHI, David Steurer

arXiv (Cornell University) · Published 12 July 2015 · DOI 10.48550/arxiv.1507.03269

Open PDFView at the publisherCite this paper

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

YearCitationsShare of the best year
201755
201866
201944
20201616
202177
202288
202322
202422
202544
202611

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

All highly cited Mathematics papers

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.