Paper · 2021 · Open access
The Complexity of Sparse Tensor PCA
Repository for Publications and Research Data (ETH Zurich), 34 · Published 1 January 2021 · DOI 10.3929/ethz-b-000520768
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
| Year | Citations | Share of the best year |
|---|---|---|
| 2022 | 3 | |
| 2023 | 1 | |
| 2024 | 3 | |
| 2025 | 4 | |
| 2026 | 2 |
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
- ImageNet classification with deep convolutional neural networksAlex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton · Communications of the ACM · 2017 · 114,726 citations
- Long Short-Term MemorySepp Hochreiter, Jürgen Schmidhuber · Neural Computation · 1997 · 109,097 citations
- A Mathematical Theory of CommunicationClaude E. Shannon · Bell System Technical Journal · 1948 · 91,736 citations
- Deep learningYann LeCun, Yoshua Bengio, Geoffrey E. Hinton · Nature · 2015 · 90,226 citations
- Faster R-CNN: Towards Real-Time Object Detection with Region Proposal NetworksShaoqing Ren, Kaiming He, Ross Girshick and 1 more · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2016 · 74,143 citations
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.