The Complexity of Sparse Tensor PCA

Dec 6, 2021



We study the problem of sparse tensor principal component analysis: given a tensor Y = W + λ x^⊗ p with W ∈⊗^p ℝ^n having i.i.d. Gaussian entries, the goal is to recover the k-sparse unit vector x ∈ℝ^n. 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. For any 1 ≤ t ≤ k, our algorithms recovers the sparse vector for signal-to-noise ratio λ≥𝒪̃ (√(t)· (k/t)^p/2) in time 𝒪̃(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 λ≥𝒪̃(k · r) while our algorithms require λ≥𝒪̃(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.


About NeurIPS 2021

Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.

Store presentation

Should this presentation be stored for 1000 years?

How do we store presentations

Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%


Recommended Videos

Presentations on similar topic, category or speaker

Interested in talks like this? Follow NeurIPS 2021