TY - GEN

T1 - Provable ICA with unknown Gaussian noise, with implications for Gaussian mixtures and autoencoders

AU - Arora, Sanjeev

AU - Ge, Rong

AU - Moitra, Ankur

AU - Sachdeva, Sushant

PY - 2012/12/1

Y1 - 2012/12/1

N2 - We present a new algorithm for Independent Component Analysis (ICA) which has provable performance guarantees. In particular, suppose we are given samples of the form y = Ax +η where A is an unknown n × n matrix and x is a random variable whose components are independent and have a fourth moment strictly less than that of a standard Gaussian random variable and η is an n-dimensional Gaussian random variable with unknown covariance ∑ We give an algorithm that provable recovers A and ∑ up to an additive ε and whose running time and sample complexity are polynomial in n and 1/ε To accomplish this, we introduce a novel "quasi-whitening" step that may be useful in other contexts in which the covariance of Gaussian noise is not known in advance. We also give a general framework for finding all local optima of a function (given an oracle for approximately finding just one) and this is a crucial step in our algorithm, one that has been overlooked in previous attempts, and allows us to control the accumulation of error when we find the columns of A one by one via local search.

AB - We present a new algorithm for Independent Component Analysis (ICA) which has provable performance guarantees. In particular, suppose we are given samples of the form y = Ax +η where A is an unknown n × n matrix and x is a random variable whose components are independent and have a fourth moment strictly less than that of a standard Gaussian random variable and η is an n-dimensional Gaussian random variable with unknown covariance ∑ We give an algorithm that provable recovers A and ∑ up to an additive ε and whose running time and sample complexity are polynomial in n and 1/ε To accomplish this, we introduce a novel "quasi-whitening" step that may be useful in other contexts in which the covariance of Gaussian noise is not known in advance. We also give a general framework for finding all local optima of a function (given an oracle for approximately finding just one) and this is a crucial step in our algorithm, one that has been overlooked in previous attempts, and allows us to control the accumulation of error when we find the columns of A one by one via local search.

UR - http://www.scopus.com/inward/record.url?scp=84877781888&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84877781888&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84877781888

SN - 9781627480031

T3 - Advances in Neural Information Processing Systems

SP - 2375

EP - 2383

BT - Advances in Neural Information Processing Systems 25

T2 - 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012

Y2 - 3 December 2012 through 6 December 2012

ER -