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

Sanjeev Arora, Rong Ge, Ankur Moitra, Sushant Sachdeva

Research output: Contribution to journalArticle

7 Citations (Scopus)

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 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 $$A$$A one by one via local search.

Original languageEnglish (US)
Pages (from-to)215-236
Number of pages22
JournalAlgorithmica
Volume72
Issue number1
DOIs
StatePublished - May 1 2015

Fingerprint

Gaussian Mixture
Independent component analysis
Gaussian Noise
Random variables
Random variable
Unknown
Nonsingular or invertible matrix
Performance Guarantee
Independent Component Analysis
Local Search
Fourth Order
n-dimensional
Strictly
Polynomials
Moment
Polynomial

All Science Journal Classification (ASJC) codes

  • Applied Mathematics
  • Computer Science(all)
  • Computer Science Applications

Cite this

Arora, Sanjeev ; Ge, Rong ; Moitra, Ankur ; Sachdeva, Sushant. / Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders. In: Algorithmica. 2015 ; Vol. 72, No. 1. pp. 215-236.
@article{4e535f93ad714a2f9b524f62cefab16a,
title = "Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders",
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 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 $$A$$A one by one via local search.",
author = "Sanjeev Arora and Rong Ge and Ankur Moitra and Sushant Sachdeva",
year = "2015",
month = "5",
day = "1",
doi = "https://doi.org/10.1007/s00453-015-9972-2",
language = "English (US)",
volume = "72",
pages = "215--236",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer New York",
number = "1",

}

Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders. / Arora, Sanjeev; Ge, Rong; Moitra, Ankur; Sachdeva, Sushant.

In: Algorithmica, Vol. 72, No. 1, 01.05.2015, p. 215-236.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Arora, Sanjeev

AU - Ge, Rong

AU - Moitra, Ankur

AU - Sachdeva, Sushant

PY - 2015/5/1

Y1 - 2015/5/1

N2 - 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 $$A$$A one by one via local search.

AB - 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 $$A$$A one by one via local search.

UR - http://www.scopus.com/inward/record.url?scp=84940003975&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84940003975&partnerID=8YFLogxK

U2 - https://doi.org/10.1007/s00453-015-9972-2

DO - https://doi.org/10.1007/s00453-015-9972-2

M3 - Article

VL - 72

SP - 215

EP - 236

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 1

ER -