Smoothed analysis for tensor methods in unsupervised learning.

Smoothed analysis is a powerful paradigm in overcoming worst-case intractability in high-dimensional data analysis and unsupervised learning. While polynomial time smoothed analysis guarantees have been obtained for worst-case intractable problems like tensor decomposition and learning mixtures of Gaussians, such guarantees have been hard to obtain for several other important problems in data analysis. A core technical challenge in analyzing algorithms is obtaining lower bounds on the least singular value for random matrix ensembles with dependent entries, that are given by low-degree polynomials of a few base underlying random variables. In this work, we address this challenge by obtaining high-confidence lower bounds on the least singular value of new classes of structured random matrix ensembles of the above kind. We then use these bounds to design algorithms with polynomial time smoothed analysis guarantees for the following three important problems in high-dimensional data analysis: Higher order tensor decompositions, where we generalize and analyze the so-called FOOBI algorithm of Cardoso. This allows us to obtain polynomially robust decomposition algorithms for 2 ℓ 'th order tensors with rank O (n ℓ) . Learning overcomplete hidden markov models, where the size of the state space is any polynomial in the dimension of the observations. This gives the first polynomial time guarantees for learning overcomplete HMMs in the smoothed analysis model. Robust subspace recovery, when the fraction α of inliers in the d-dimensional subspace T ⊂ R n is at least α > (d / n) ℓ for any constant ℓ ∈ Z + . This contrasts with the known worst-case intractability when α < d / n , and the previous smoothed analysis result which needed α > d / n ([33]). [ABSTRACT FROM AUTHOR]