We present a simple, general technique for reducing the sample complexity of matrix and tensor decomposition algorithms applied to distributions. We use the technique to give a polynomial-time algorithm for standard ICA with sample complexity nearly linear in the dimension, thereby improving substantially on previous bounds. The analysis is based on properties of random polynomials, namely the spacings of an ensemble of polynomials. Our technique also applies to other applications of tensor decompositions, including spherical Gaussian mixture models.
The main technique is all these papers can be viewed as efficient tensor decomposition. For a Hermitian matrix @math , one can give an orthogonal decomposition into rank @math components: This decomposition, especially when applied to covariance matrices, is a powerful tool in machine learning and theoretical computer science. The generalization of this to tensors is not straightforward, and many versions of this decomposition lead directly to NP-hard problems . The application of tensor decomposition to ICA was proposed by @cite_6 . Such decompositions were used by @cite_3 and @cite_17 to give provable algorithms for various latent variable models. @cite_7 extended these decompositions to a more general setting where the rank-one factors need not be linearly independent (and thus might be many more than the dimension).
@cite_3 @cite_7 @cite_6 @cite_17
2953337630 2950033149 1533423434 2951439068
The problem of topic modeling can be seen as a generalization of the clustering problem, in that it posits that observations are generated due to multiple latent factors (e.g., the words in each document are generated as a mixture of several active topics, as opposed to just one). This increased representational power comes at the cost of a more challenging unsupervised learning problem of estimating the topic probability vectors (the distributions over words for each topic), when only the words are observed and the corresponding topics are hidden. We provide a simple and efficient learning procedure that is guaranteed to recover the parameters for a wide class of mixture models, including the popular latent Dirichlet allocation (LDA) model. For LDA, the procedure correctly recovers both the topic probability vectors and the prior over the topics, using only trigram statistics (i.e., third order moments, which may be estimated with documents containing just three words). The method, termed Excess Correlation Analysis (ECA), is based on a spectral decomposition of low order moments (third and fourth order) via two singular value decompositions (SVDs). Moreover, the algorithm is scalable since the SVD operations are carried out on @math matrices, where @math is the number of latent factors (e.g. the number of topics), rather than in the @math -dimensional observed space (typically @math ). Fourier PCA is Principal Component Analysis of a matrix obtained from higher order derivatives of the logarithm of the Fourier transform of a distribution.We make this method algorithmic by developing a tensor decomposition method for a pair of tensors sharing the same vectors in rank- @math decompositions. Our main application is the first provably polynomial-time algorithm for underdetermined ICA, i.e., learning an @math matrix @math from observations @math where @math is drawn from an unknown product distribution with arbitrary non-Gaussian components. The number of component distributions @math can be arbitrarily higher than the dimension @math and the columns of @math only need to satisfy a natural and efficiently verifiable nondegeneracy condition. As a second application, we give an alternative algorithm for learning mixtures of spherical Gaussians with linearly independent means. These results also hold in the presence of Gaussian noise. The author presents a simple algebraic method for the extraction of independent components in multidimensional data. Since statistical independence is a much stronger property than uncorrelation, it is possible, using higher-order moments, to identify source signatures in array data without any a priori model for propagation or reception, that is, without directional vector parameterization, provided that the emitting sources are independent with different probability distributions. The author proposes such a blind identification procedure. Source signatures are directly identified as covariance eigenvectors after data have been orthonormalized and nonlinearly weighted. Potential applications to array processing are illustrated by a simulation consisting of a simultaneous range-bearing estimation with a passive array. > This work provides a computationally efficient and statistically consistent moment-based estimator for mixtures of spherical Gaussians. Under the condition that component means are in general position, a simple spectral decomposition technique yields consistent parameter estimates from low-order observable moments, without additional minimum separation assumptions needed by previous computationally efficient estimation procedures. Thus computational and information-theoretic barriers to efficient estimation in mixture models are precluded when the mixture components have means in general position and spherical covariances. Some connections are made to estimation problems related to independent component analysis.