Max vs Min: Independent Component Analysis with nearly Linear Sample Complexity.
Santosh Vempala, Ying Xiao · arXiv (Cornell University) · 2014
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.