UnsolvedMajor Unsolved Problem
Computational Threshold for Tensor PCA
Posed by Richard & Montanari (2014)
§ Problem Statement
Setup
Unsolved Problem
§ Discussion
Loading discussion…
§ Significance & Implications
§ Known Partial Results
§ References
[1]
A statistical model for tensor PCA
Emile Richard, Andrea Montanari (2014)
NeurIPS
📍 Section 1 (Introduction), in the “We next summarize our results” discussion contrasting “Ideal estimation” with “Tractable estimators: Unfolding/Power iteration” (computational-statistical gap), p. 2 (NeurIPS 2014 PDF)
[2]
Tensor principal component analysis via sum-of-squares proofs
Samuel Hopkins, Jonathan Shi, David Steurer (2015)
COLT
[3]
Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio
Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira (2019)
📍 Section 2.3 (Tensor PCA), Conjecture 2.4 (low-degree polynomial lower bound at the spectral threshold n^{-(k-1)/4}), p. 12.