Paper · 2021 · Open access

The Complexity of Sparse Tensor PCA

Davin Choo, Tommaso d'Orsi

Repository for Publications and Research Data (ETH Zurich), 34 · Published 1 January 2021 · DOI 10.3929/ethz-b-000520768

Open full textView at the publisherCite this paper

In brief

“The Complexity of Sparse Tensor PCA” is a 2021 paper by Davin Choo and Tommaso d'Orsi, published in Repository for Publications and Research Data (ETH Zurich). OpenAlex counts 13 citations as of 18 November 2026. It is open access: the full text is free to read at Repository for Publications and Research Data (ETH Zurich).

Citations
13
Most cited in
2025 (4)
Field-weighted impact
0.89
References
42
Authors
2

Abstract

We study the problem of sparse tensor principal component analysis: given a tensor $\pmb Y = \pmb W + λx^{\otimes p}$ with $\pmb W \in \otimes^p\mathbb{R}^n$ having i.i.d. Gaussian entries, the goal is to recover the $k$-sparse unit vector $x \in \mathbb{R}^n$. The model captures both sparse PCA (in its Wigner form) and tensor PCA. For the highly sparse regime of $k \leq \sqrt{n}$, we present a family of algorithms that smoothly interpolates between a simple polynomial-time algorithm and the exponential-time exhaustive search algorithm. For any $1 \leq t \leq k$, our algorithms recovers the sparse vector for signal-to-noise ratio $λ\geq \tilde{\mathcal{O}} (\sqrt{t} \cdot (k/t)^{p/2})$ in time $\tilde{\mathcal{O}}(n^{p+t})$, capturing the state-of-the-art guarantees for the matrix settings (in both the polynomial-time and sub-exponential time regimes). Our results naturally extend to the case of $r$ distinct $k$-sparse signals with disjoint supports, with guarantees that are independent of the number of spikes. Even in the restricted case of sparse PCA, known algorithms only recover the sparse vectors for $λ\geq \tilde{\mathcal{O}}(k \cdot r)$ while our algorithms require $λ\geq \tilde{\mathcal{O}}(k)$. Finally, by analyzing the low-degree likelihood ratio, we complement these algorithmic results with rigorous evidence illustrating the trade-offs between signal-to-noise ratio and running time. This lower bound captures the known lower bounds for both sparse PCA and tensor PCA. In this general model, we observe a more intricate three-way trade-off between the number of samples $n$, the sparsity $k$, and the tensor power $p$.

Cite this paper

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

APA 7

Choo, D., & d'Orsi, T. (2021). The Complexity of Sparse Tensor PCA. Repository for Publications and Research Data (ETH Zurich), 34. https://doi.org/10.3929/ethz-b-000520768

MLA 9

Choo, Davin, and Tommaso d'Orsi. “The Complexity of Sparse Tensor PCA.” Repository for Publications and Research Data (ETH Zurich), vol. 34, 2021. https://doi.org/10.3929/ethz-b-000520768.

Chicago

Choo, Davin and Tommaso d'Orsi. 2021. “The Complexity of Sparse Tensor PCA.” Repository for Publications and Research Data (ETH Zurich) 34. https://doi.org/10.3929/ethz-b-000520768.

Harvard

Choo, D. and d'Orsi, T. (2021) ‘The Complexity of Sparse Tensor PCA’, Repository for Publications and Research Data (ETH Zurich), 34. doi:10.3929/ethz-b-000520768.

IEEE

D. Choo and T. d'Orsi, “The Complexity of Sparse Tensor PCA,” Repository for Publications and Research Data (ETH Zurich), vol. 34, 2021, doi: 10.3929/ethz-b-000520768.

BibTeX

@article{choo2021complexity,
  title     = {{The Complexity of Sparse Tensor PCA}},
  author    = {Choo, Davin and d'Orsi, Tommaso},
  journal   = {Repository for Publications and Research Data (ETH Zurich)},
  year      = {2021},
  volume    = {34},
  doi       = {10.3929/ethz-b-000520768},
  url       = {https://doi.org/10.3929/ethz-b-000520768}
}

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

Citations by year

YearCitationsShare of the best year
202233
202311
202433
202544
202622

Its field-weighted citation impact is 0.89: it has been cited 0.89 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 › Computer Science › Signal Processing › Sparse and Compressive Sensing Techniques

  • sparse principal component analysis
  • sparse vector recovery
  • polynomial-time algorithms
  • signal-to-noise ratio
  • lower bounds
  • high-dimensional statistics

Work with this paper

Most-cited papers in Computer Science

All highly cited Computer Science papers

Questions about this paper

How do I cite this paper in APA style?

Choo, D., & d'Orsi, T. (2021). The Complexity of Sparse Tensor PCA. Repository for Publications and Research Data (ETH Zurich), 34. https://doi.org/10.3929/ethz-b-000520768

How many times has this paper been cited?

13 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 Repository for Publications and Research Data (ETH Zurich): sign in and open the full text from this page.

Who wrote this paper?

Davin Choo, Tommaso d'Orsi.

What is the DOI of this paper?

10.3929/ethz-b-000520768, permanently at https://doi.org/10.3929/ethz-b-000520768. 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.