Fourier PCA and Robust Tensor Decomposition

Abstract

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.

Extensively revised; details added; minor errors corrected; exposition improved

References in corpus (9)

• A Spectral Algorithm for Latent Dirichlet Allocation
• Polynomial Learning of Distribution Families
• A Spectral Algorithm for Learning Hidden Markov Models
• New Algorithms for Learning Incoherent and Overcomplete Dictionaries
• Settling the Polynomial Learnability of Mixtures of Gaussians
• The More, the Merrier: the Blessing of Dimensionality for Learning Large Gaussian Mixtures
• Structure from Local Optima: Learning Subspace Juntas via Higher Order PCA
• Smoothed Analysis of Tensor Decompositions
• How close is the sample covariance matrix to the actual covariance matrix?

Cited by in corpus (4)

• New Algorithms for Learning Incoherent and Overcomplete Dictionaries
• Sample Complexity Analysis for Learning Overcomplete Latent Variable Models through Tensor Methods
• Optimal Low-Rank Tensor Recovery from Separable Measurements: Four Contractions Suffice
• Smoothed Analysis of Tensor Decompositions