# Fourier PCA and Robust Tensor Decomposition

arXiv: https://arxiv.org/abs/1306.5825 · HTML: https://mlsanity.com/paper/1306.5825/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2013.

## Built on by (most cited first, 8 of 8)

- [Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations](https://mlsanity.com/paper/2107.10209/) (2021)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error](https://mlsanity.com/paper/2302.12289/) (2023)
- [Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity](https://mlsanity.com/paper/2309.13993/) (2023)
- [On the Role of Channel Capacity in Learning Gaussian Mixture Models](https://mlsanity.com/paper/2202.07707/) (2022)
- [Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond](https://mlsanity.com/paper/2212.03851/) (2022)
- [Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time](https://mlsanity.com/paper/2311.01435/) (2023)
- [Overcomplete Tensor Decomposition via Koszul-Young Flattenings](https://mlsanity.com/paper/2411.14344/) (2024)

## Abstract (arXiv)

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 × 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.