Eigenvectors of Orthogonally Decomposable Functions and Applications

Eigendecomposition of quadratic forms guaranteed by the spectral theorem is the foundation for many important algorithms in computer science, data analysis, and machine learning. In this talk I will discuss our recent work on generalizations from quadratic forms to a broad class of functions based on an analogue of the spectral decomposition in an orthogonal basis. We call such functions “orthogonally decomposable”. It turns out that many inferential problems of recent interest including orthogonal tensor decompositions, Independent Component Analysis (ICA), topic models, spectral clustering, and Gaussian mixture learning can be viewed as recovering basis elements from non-quadratic functions of this type. We identify a key role of convexity in extending traditional characterizations of eigenvectors to the more generic setting of orthogonally decomposable functions. We focus on extending two traditional characterizations of eigenvectors: First, that the eigenvectors of a quadratic form arise from the optima structure of the quadratic form on the sphere, and second that the eigenvectors are the fixed points of the power iteration. Our generalization of the power iteration is a simple first order algorithm, “gradient iteration”. This gradient iteration leads to efficient and easily implementable methods for basis recovery, including such methods as cumulant-based FastICA and the tensor power iteration for orthogonally decomposable tensors as special cases. I will discuss our theoretical analysis of gradient iteration using the structure theory of discrete dynamical systems to show almost sure convergence and fast (super-linear) convergence rates. The analysis is extended to the case when the observed function is only approximately orthogonally decomposable, with bounds that are polynomial in dimension and other relevant parameters, such as perturbation size. The results can be considered as a non-linear version of the classical Davis-Kahan theorem for perturbations of eigenvectors of symmetric matrices. Finally, I will go over some new applications of the proposed framework to spectral clustering. Joint work with L. Rademacher and J. Voss.