Skip to main content

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

Publication ,  Journal Article
Arora, S; Ge, R; Moitra, A; Sachdeva, S
Published in: Advances in Neural Information Processing Systems
December 1, 2012

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.

Duke Scholars

Published In

Advances in Neural Information Processing Systems

ISSN

1049-5258

Publication Date

December 1, 2012

Volume

3

Start / End Page

2375 / 2383

Related Subject Headings

  • 4611 Machine learning
  • 1702 Cognitive Sciences
  • 1701 Psychology
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Arora, S., Ge, R., Moitra, A., & Sachdeva, S. (2012). Provable ICA with unknown Gaussian noise, with implications for Gaussian mixtures and autoencoders. Advances in Neural Information Processing Systems, 3, 2375–2383.
Arora, S., R. Ge, A. Moitra, and S. Sachdeva. “Provable ICA with unknown Gaussian noise, with implications for Gaussian mixtures and autoencoders.” Advances in Neural Information Processing Systems 3 (December 1, 2012): 2375–83.
Arora S, Ge R, Moitra A, Sachdeva S. Provable ICA with unknown Gaussian noise, with implications for Gaussian mixtures and autoencoders. Advances in Neural Information Processing Systems. 2012 Dec 1;3:2375–83.
Arora, S., et al. “Provable ICA with unknown Gaussian noise, with implications for Gaussian mixtures and autoencoders.” Advances in Neural Information Processing Systems, vol. 3, Dec. 2012, pp. 2375–83.
Arora S, Ge R, Moitra A, Sachdeva S. Provable ICA with unknown Gaussian noise, with implications for Gaussian mixtures and autoencoders. Advances in Neural Information Processing Systems. 2012 Dec 1;3:2375–2383.

Published In

Advances in Neural Information Processing Systems

ISSN

1049-5258

Publication Date

December 1, 2012

Volume

3

Start / End Page

2375 / 2383

Related Subject Headings

  • 4611 Machine learning
  • 1702 Cognitive Sciences
  • 1701 Psychology