Max vs Min: Independent Component Analysis with nearly Linear Sample Complexity
We present an efficient algorithm for standard ICA that needs only a nearly linear number of samples and has polynomial time complexity. The algorithm is a recursive version of the Fourier PCA method of Goyal et al. Its analysis is based on properties of random polynomials, namely the spacings of an ensemble of polynomials.