Fourier PCA and Robust Tensor Decomposition
This provides the first provably polynomial-time algorithm for underdetermined ICA, addressing a fundamental challenge in signal processing and machine learning for separating mixed sources.
The paper tackles the problem of underdetermined Independent Component Analysis (ICA) by introducing Fourier PCA, a method that uses higher-order derivatives of the Fourier transform for polynomial-time learning of an n x m matrix A from observations y=Ax with arbitrary non-Gaussian components, where m can be arbitrarily higher than n, and also applies to learning mixtures of spherical Gaussians with linearly independent means, even in the presence of Gaussian noise.
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.