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.We make this method algorithmic by developing a tensor
decomposition method for a pair of tensors sharing the same vectors in rank-$1$
decompositions. Our main application is the first provably polynomial-time
algorithm for underdetermined ICA, i.e., learning an $n \times 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.
