### Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | Advances in Neural Information Processing Systems 25 |

Subtitle of host publication | 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012 |

Pages | 2375-2383 |

Number of pages | 9 |

State | Published - Dec 1 2012 |

Event | 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012 - Lake Tahoe, NV, United States Duration: Dec 3 2012 → Dec 6 2012 |

### Publication series

Name | Advances in Neural Information Processing Systems |
---|---|

Volume | 3 |

ISSN (Print) | 1049-5258 |

### Other

Other | 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012 |
---|---|

Country | United States |

City | Lake Tahoe, NV |

Period | 12/3/12 → 12/6/12 |

### All Science Journal Classification (ASJC) codes

- Computer Networks and Communications
- Information Systems
- Signal Processing

## Fingerprint Dive into the research topics of 'Provable ICA with unknown Gaussian noise, with implications for Gaussian mixtures and autoencoders'. Together they form a unique fingerprint.

## Cite this

*Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012*(pp. 2375-2383). (Advances in Neural Information Processing Systems; Vol. 3).