Polynomial Time and Sample Complexity for NonGaussian Component Analysis: Spectral Methods
[edit]
Proceedings of the 31st Conference On Learning Theory, PMLR 75:498534, 2018.
Abstract
The problem of NonGaussian Component Analysis (NGCA) is about finding a maximal lowdimensional subspace $E$ in $\mathbb{R}^n$ so that data points projected onto $E$ follow a nonGaussian distribution. Vempala and Xiao (2011) proposed a local search algorithm, and showed that it was able to estimate $E$ accurately with polynomial time and sample complexity, if the dimension of $E$ is treated as a constant and with the assumption that all onedimensional marginals of the nonGaussian distribution over $E$ have nonGaussian moments. In this paper, we propose a simple spectral algorithm called \textsc{Reweighted PCA}, and prove that it possesses the same guarantee. The principle that underlies this approach is a new characterization of multivariate Gaussian distributions.
Related Material


