Research map / Learning theory and algorithms / Matrix and tensor methods
The Complexity of Sparse Tensor PCA
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a t-sparse search rather than an exhaustive k-sparse search | Limited brute force for single-spike sparse tensor PCA · Sparse tensor PCA, single spike | signal strength threshold for exact support recovery: \lambda \gtrsim \sqrt{ t \left( \frac{2 A^2 k}{t} \right)^p \ln n}; exhaustive search succeeds when \lambda \gtrsim \sqr | Helped |
| Increase the search parameter t | Limited brute force for single-spike sparse tensor PCA · Sparse tensor PCA, single spike | signal strength threshold versus running time: \widetilde{\mathcal{O}} (\sqrt{t} \cdot (k/t)^{p/2}); \widetilde{\mathcal{O}}(n^{p+t}) | Mixed |
| Apply limited brute force to highly sparse signals | Sparse tensor PCA · Single spike, k \lesssim \sqrt{n} | signal strength threshold for support recovery: \widetilde{\mathcal{O}}(k^{p/2}) versus \widetilde{\mathcal{O}}(n^{p/4}) | Helped |
| Remove the polynomial dependency on tensor order p in the signal-strength guarantee | Limited brute force for sparse tensor PCA · Single spike, k \lesssim \sqrt{n} | signal strength threshold for support recovery: \lambda \gtrsim \sqrt{p k^p\log n} versus the proposed guarantee for A=1 and fixed t | Helped |
| Use the proposed multi-spike algorithm for disjoint supports | Sparse PCA multiple-spike recovery · Sparse PCA, multiple disjoint spikes | signal strength threshold for recovery: \widetilde{\mathcal{O}}(k) versus \widetilde{\mathcal{O}}(k \cdot r) | Helped |
| Use the low-degree likelihood-ratio analysis to bound distinguishability | Sparse tensor PCA · Single-spike low-degree distinguishing | signal strength threshold below which degree-D polynomials cannot distinguish: \lambda \lesssim \frac{\sqrt{D}}{2^p} \min \left\{ \Paren{ \frac{n}{pD} }^{p/4},\; \Paren{ \frac{k}{pD} \Paren{ 1 + \Abs | Mixed |
| Use limited brute force with \ell distinct t-sparse vectors for a general tensor signal | Sparse tensor PCA · Single spike general tensor with \ell distinct sparse vectors | signal strength threshold for support recovery: \lambda \gtrsim \sqrt{\ell t (k/t)^p \log n} | Helped |
Closest papers by meaning
- Fast and Provable Algorithms for Sparse PCA with Improved Sample Complexity (ICML 2025 · similarity 0.92)
- A Kernel Random Matrix-Based Approach for Sparse PCA (ICLR 2019 · similarity 0.91)
- Efficient Sparse PCA via Block-Diagonalization (ICLR 2025 · similarity 0.91)
- Tensor Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Tensors via Convex Optimization (CVPR 2016 · similarity 0.91)
- Sharp Recovery Thresholds of Tensor PCA Spectral Algorithms (NeurIPS 2023 · similarity 0.91)
- Oja's Algorithm for Streaming Sparse PCA (NeurIPS 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.