Poster
Provable ICA with Unknown Gaussian Noise, with Implications for Gaussian Mixtures and Autoencoders
Sanjeev Arora · Rong Ge · Ankur Moitra · Sushant Sachdeva
Harrah’s Special Events Center 2nd Floor
[
Abstract
]
Abstract:
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+ηy=Ax+η where AA is an unknown n×nn×n matrix and xx is chosen uniformly at random from {+1,−1}n{+1,−1}n, ηη is an nn-dimensional Gaussian random variable with unknown covariance ΣΣ: We give an algorithm that provable recovers AA and ΣΣ up to an additive ϵϵ whose running time and sample complexity are polynomial in nn and 1/ϵ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 AA one by one via local search.
Live content is unavailable. Log in and register to view live content