The Complexity of Sparse Tensor PCA
Authors: Davin Choo, Tommaso d'Orsi
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of sparse tensor principal component analysis: given a tensor Y = W + λx p with W p Rn having i.i.d. Gaussian entries, the goal is to recover the k-sparse unit vector x Rn. The model captures both sparse PCA (in its Wigner form) and tensor PCA. For the highly sparse regime of k n, we present a family of algorithms that smoothly interpolates between a simple polynomial-time algorithm and the exponential-time exhaustive search algorithm. [...] 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. |
| Researcher Affiliation | Academia | Davin Choo Department of Computer Science National University of Singapore davin@u.nus.edu Tommaso d Orsi Department of Computer Science ETH Zürich tommaso.dorsi@inf.ethz.ch |
| Pseudocode | Yes | Algorithm 1 Preprocessing [...] Algorithm 2 Single spike limited brute force [...] Algorithm 3 Multi-spike limited brute force |
| Open Source Code | No | The paper does not provide any statement or link indicating that source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and does not involve empirical studies using datasets, thus no dataset for training is mentioned or made public. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical studies using datasets, thus no dataset splits for validation are mentioned. |
| Hardware Specification | No | The paper is theoretical and does not report on computational experiments that would require specific hardware, so no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithmic design and analysis; it does not mention any specific software dependencies or versions. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithmic design and analysis; it does not describe an experimental setup with hyperparameters or system-level training settings. |