Skip to main content

Provable ICA with Unknown Gaussian Noise, with Implications for Gaussian Mixtures and Autoencoders

Author(s): Arora, Sanjeev; Ge, Rong; Moitra, Ankur; Sachdeva, Sushant

To refer to this page use:
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 = A x + η where A is an unknown n × n matrix and x is chosen uniformly at random from { + 1 , − 1 } n , η is an n -dimensional Gaussian random variable with unknown covariance Σ : We give an algorithm that provable recovers A and Σ up to an additive ϵ 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.
Publication Date: 2012
Citation: Arora, Sanjeev, Rong Ge, Ankur Moitra, and Sushant Sachdeva. "Provable ICA with Unknown Gaussian Noise, with Implications for Gaussian Mixtures and Autoencoders." In Advances in Neural Information Processing Systems 25 (2012).
Type of Material: Conference Article
Journal/Proceeding Title: Advances in Neural Information Processing Systems
Version: Final published version. Article is made available in OAR by the publisher's permission or policy.
Notes: Supplemental Information:

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.