Tensor PCA
A high-dimensional statistical estimation problem whose goal is to recover an unknown vector from noisy tensor power observations. It exhibits the information-computation gap phenomenon.
Timeline (last 90 days)
The tensor PCA problem is defined on the sphere S_N: given noisy observations of the k-th order tensor power of an unknown vector (k≥3 fixed), the goal is to recover that unknown vector.
Tensor PCA exhibits an information-computation gap: when the signal-to-noise ratio is above the algorithmic threshold, global algorithms such as spectral methods and sum-of-squares can successfully recover in polynomial time; below that threshold, lower bounds for these algorithms and for certain restricted computational models show that they must fail.
Previously the community generally believed that local algorithms (such as Markov chains) perform far worse than global algorithms in tensor PCA, and it was only known that under random initialization they require a polynomially higher signal-to-noise ratio to succeed.
In tensor PCA, spectral methods succeed when the signal-to-noise ratio is above the algorithmic threshold, SoS also succeeds at the same threshold, and SoS lower bounds show that below this threshold any SoS algorithm fails.
All Facts (4)
The tensor PCA problem is defined on the sphere S_N: given noisy observations of the k-th order tensor power of an unknown vector (k≥3 fixed), the goal is to recover that unknown vector.
50%UnverifiedTensor PCA exhibits an information-computation gap: when the signal-to-noise ratio is above the algorithmic threshold, global algorithms such as spectral methods and sum-of-squares can successfully recover in polynomial time; below that threshold, lower bounds for these algorithms and for certain restricted computational models show that they must fail.
50%UnverifiedPreviously the community generally believed that local algorithms (such as Markov chains) perform far worse than global algorithms in tensor PCA, and it was only known that under random initialization they require a polynomially higher signal-to-noise ratio to succeed.
50%UnverifiedIn tensor PCA, spectral methods succeed when the signal-to-noise ratio is above the algorithmic threshold, SoS also succeeds at the same threshold, and SoS lower bounds show that below this threshold any SoS algorithm fails.
50%