Skip to main content

Provable ICA with Unknown Gaussian Noise, and 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 which has provable performance guarantees. In particular, suppose we are given samples of the form 𝑦=𝐴π‘₯+πœ‚ where 𝐴 is an unknown but non-singular 𝑛×𝑛 matrix, π‘₯ is a random variable whose coordinates are independent and have a fourth order moment strictly less than that of a standard Gaussian random variable and πœ‚ is an 𝑛-dimensional Gaussian random variable with unknown covariance 𝛴: We give an algorithm that provably recovers 𝐴 and 𝛴 up to an additive πœ– and whose running time and sample complexity are polynomial in 𝑛 and 1/πœ–. To accomplish this, we introduce a novel β€œquasi-whitening” step that may be useful in other applications where there is additive Gaussian noise whose covariance is unknown. 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 𝐴 one by one via local search.
Publication Date: 2015
Citation: Arora, Sanjeev, Rong Ge, Ankur Moitra, and Sushant Sachdeva. "Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders." Algorithmica 72, no. 1 (2015): 215-236. doi:10.1007/s00453-015-9972-2
DOI: 10.1007/s00453-015-9972-2
ISSN: 0178-4617
EISSN: 1432-0541
Pages: 215 - 236
Type of Material: Journal Article
Journal/Proceeding Title: Algorithmica
Version: Author's manuscript

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