Skip to main content
Journal cover image

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

Publication ,  Journal Article
Arora, S; Ge, R; Moitra, A; Sachdeva, S
Published in: Algorithmica
May 1, 2015

We present a new algorithm for independent component analysis which has provable performance guarantees. In particular, suppose we are given samples of the form y=Ax+η where A is an unknown but non-singular n×n matrix, x 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 n-dimensional Gaussian random variable with unknown covariance Σ: We give an algorithm that provably 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 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 AA one by one via local search.

Duke Scholars

Published In

Algorithmica

DOI

EISSN

1432-0541

ISSN

0178-4617

Publication Date

May 1, 2015

Volume

72

Issue

1

Start / End Page

215 / 236

Related Subject Headings

  • Computation Theory & Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Arora, S., Ge, R., Moitra, A., & Sachdeva, S. (2015). Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders. Algorithmica, 72(1), 215–236. https://doi.org/10.1007/s00453-015-9972-2
Journal cover image

Published In

Algorithmica

DOI

EISSN

1432-0541

ISSN

0178-4617

Publication Date

May 1, 2015

Volume

72

Issue

1

Start / End Page

215 / 236

Related Subject Headings

  • Computation Theory & Mathematics