In this paper we show that very large mixtures of Gaussians are efficiently
learnable in high dimension. More precisely, we prove that a mixture with known
identical covariance matrices whose number of components is a polynomial of any
fixed degree in the dimension n is polynomially learnable as long as a certain
non-degeneracy condition on the means is satisfied. It turns out that this
condition is generic in the sense of smoothed complexity, as soon as the
dimensionality of the space is high enough. Moreover, we prove that no such
condition can possibly exist in low dimension and the problem of learning the
parameters is generically hard. In contrast, much of the existing work on
Gaussian Mixtures relies on low-dimensional projections and thus hits an
artificial barrier. Our main result on mixture recovery relies on a new
"Poissonization"-based technique, which transforms a mixture of Gaussians to a
linear map of a product distribution. The problem of learning this map can be
efficiently solved using some recent results on tensor decompositions and
Independent Component Analysis (ICA), thus giving an algorithm for recovering
the mixture. In addition, we combine our low-dimensional hardness results for
Gaussian mixtures with Poissonization to show how to embed difficult instances
of low-dimensional Gaussian mixtures into the ICA setting, thus establishing
exponential information-theoretic lower bounds for underdetermined ICA in low
dimension. To the best of our knowledge, this is the first such result in the
literature. In addition to contributing to the problem of Gaussian mixture
learning, we believe that this work is among the first steps toward better
understanding the rare phenomenon of the "blessing of dimensionality" in the
computational aspects of statistical inference.

本文证明已知的具有相同协方差矩阵和组成部分数量为固定次数多项式的高维混合高斯成分是多项式可学习的，但在低维空间下这种情况不可能存在。通过一种称为 Poissonization 的技术，将高维混合高斯成分变换为直接解决线性映射的问题。最后，我们将高维困难实例嵌入 ICA 设置中，建立了低维 ICA 的指数信息论下界。