Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders
This addresses a fundamental challenge in signal processing and machine learning for scenarios with unknown noise, offering theoretical guarantees that could impact applications like Gaussian mixtures and autoencoders.
The paper tackles the problem of Independent Component Analysis (ICA) with unknown Gaussian noise by presenting a new algorithm that provably recovers the mixing matrix and noise covariance up to an additive error ε, with polynomial running time and sample complexity in n and 1/ε.
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 \times 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.