Friday, December 19, 2014

Video: A Statistical Model for Tensor Principal Component Analysis


A Statistical Model for Tensor Principal Component Analysis
I will discuss the Principal Component Analysis problem for large tensors of arbitrary order k under a single-spike (or rank-one plus noise) model. On the one hand, using information theory, and recent results in probability theory I will provide necessary and sufficient conditions under  which the principal component can be estimated using unbounded computational resources. It turns out that this is possible as soon as the signal-to-noise ratio \beta becomes larger than C\sqrt{k\log k} (and in particular \beta can remain bounded has the problem dimensions increase). On the other hand, I will analyze several polynomial-time estimation algorithms, based on various approaches:
  1. Tensor matricization and spectral analysis, 
  2. Semidefinite relaxations,
  3. Power iteration.
I will show that, unless the signal-to-noise ratio diverges in the system dimensions, none of these approaches succeeds. This is possibly related to a fundamental limitation of polynomial estimators for this problem. While complexity theory suggests that intractability holds from a worst case point of view, no analogous result has been proved  under statistical models of the data.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

No comments: