Fourier PCA and Robust Tensor Decomposition

Fourier PCA is Principal Component Analysis of a matrix obtained from higher order derivatives of the logarithm of the Fourier transform of a distribution. To make this algorithmic, we develop a robust tensor decomposition method; this is also of independent interest. Our main application is the first provably polynomial-time algorithm for underdetermined ICA, i.e., learning an n x m matrix A from observations y = Ax where x is drawn from an unknown product distribution with arbitrary non-Gaussian components. The number of component distributions m can be arbitrarily higher than the dimension n and the columns of A only need to satisfy a natural and efficiently verifiable nondegeneracy condition. As a second application, we give an alternative algorithm for learning mixtures of spherical Gaussians with linearly independent means. These results also hold in the presence of Gaussian noise.