Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity
This provides a more efficient method for ICA and related problems in machine learning and signal processing, with incremental improvements in sample complexity.
The paper tackles the problem of high sample complexity in tensor decomposition algorithms for Independent Component Analysis (ICA) and other applications, achieving a polynomial-time algorithm with sample complexity nearly linear in dimension, which substantially improves previous bounds.
We present a simple, general technique for reducing the sample complexity of matrix and tensor decomposition algorithms applied to distributions. We use the technique to give a polynomial-time algorithm for standard ICA with sample complexity nearly linear in the dimension, thereby improving substantially on previous bounds. The analysis is based on properties of random polynomials, namely the spacings of an ensemble of polynomials. Our technique also applies to other applications of tensor decompositions, including spherical Gaussian mixture models.