Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders
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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2017
|
| Online Access: | http://hdl.handle.net/1721.1/106898 https://orcid.org/0000-0001-7047-0495 |
| _version_ | 1811081992492548096 |
|---|---|
| author | Arora, Sanjeev Ge, Rong Moitra, Ankur Sachdeva, Sushant |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Arora, Sanjeev Ge, Rong Moitra, Ankur Sachdeva, Sushant |
| author_sort | Arora, Sanjeev |
| collection | MIT |
| description | 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 one by one via local search. |
| first_indexed | 2024-09-23T11:55:40Z |
| format | Article |
| id | mit-1721.1/106898 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:55:40Z |
| publishDate | 2017 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1068982022-10-01T07:02:48Z Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders Arora, Sanjeev Ge, Rong Moitra, Ankur Sachdeva, Sushant Massachusetts Institute of Technology. Department of Mathematics Moitra, Ankur 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 one by one via local search. 2017-02-10T18:18:21Z 2017-02-10T18:18:21Z 2015-03 2016-05-23T12:14:16Z Article http://purl.org/eprint/type/JournalArticle 0178-4617 1432-0541 http://hdl.handle.net/1721.1/106898 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 (March 4, 2015): 215–236. https://orcid.org/0000-0001-7047-0495 en http://dx.doi.org/10.1007/s00453-015-9972-2 Algorithmica Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer Science+Business Media New York application/pdf Springer US Springer US |
| spellingShingle | Arora, Sanjeev Ge, Rong Moitra, Ankur Sachdeva, Sushant Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders |
| title | Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders |
| title_full | Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders |
| title_fullStr | Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders |
| title_full_unstemmed | Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders |
| title_short | Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders |
| title_sort | provable ica with unknown gaussian noise and implications for gaussian mixtures and autoencoders |
| url | http://hdl.handle.net/1721.1/106898 https://orcid.org/0000-0001-7047-0495 |
| work_keys_str_mv | AT arorasanjeev provableicawithunknowngaussiannoiseandimplicationsforgaussianmixturesandautoencoders AT gerong provableicawithunknowngaussiannoiseandimplicationsforgaussianmixturesandautoencoders AT moitraankur provableicawithunknowngaussiannoiseandimplicationsforgaussianmixturesandautoencoders AT sachdevasushant provableicawithunknowngaussiannoiseandimplicationsforgaussianmixturesandautoencoders |