Eigenvectors of Orthogonally Decomposable Functions
From MaRDI portal
Abstract: The Eigendecomposition of quadratic forms (symmetric matrices) guaranteed by the spectral theorem is a foundational result in applied mathematics. Motivated by a shared structure found in inferential problems of recent interest---namely orthogonal tensor decompositions, Independent Component Analysis (ICA), topic models, spectral clustering, and Gaussian mixture learning---we generalize the eigendecomposition from quadratic forms to a broad class of "orthogonally decomposable" functions. We identify a key role of convexity in our extension, and we generalize two traditional characterizations of eigenvectors: First, the eigenvectors of a quadratic form arise from the optima structure of the quadratic form on the sphere. Second, the eigenvectors are the fixed points of the power iteration. In our setting, we consider a simple first order generalization of the power method which we call gradient iteration. It leads to efficient and easily implementable methods for basis recovery. It includes influential Machine Learning methods such as cumulant-based FastICA and the tensor power iteration for orthogonally decomposable tensors as special cases. We provide a complete 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 also extends 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. Our perturbation results can be considered as a non-linear version of the classical Davis-Kahan theorem for perturbations of eigenvectors of symmetric matrices.
Recommendations
- Eigenvalues of functions of orthogonal projectors
- Orthogonal compactly supported functions in eigenvalue problems
- Decomposition of two functions in the orthogonality equation
- scientific article; zbMATH DE number 5499041
- Eigenvectors of Order-Preserving Linear Operators
- Spectral decomposition and matrix-valued orthogonal polynomials
- Eigenvectors of Jacobi matrices
- Inverse unitary eigenproblems and related orthogonal functions
- Decompositions and eigenvectors of Riordan matrices
- Eigenvectors and functions of the discrete Fourier transform
Cites work
- A spectral algorithm for latent Dirichlet allocation
- Adaptive blind separation of independent sources: A deflation approach
- Adaptive estimation of a quadratic functional by model selection.
- Eigenvalues of a real supersymmetric tensor
- Fourier PCA and robust tensor decomposition
- scientific article; zbMATH DE number 52737 (Why is no real title available?)
- scientific article; zbMATH DE number 1022658 (Why is no real title available?)
- scientific article; zbMATH DE number 782094 (Why is no real title available?)
- Independent component analysis by general nonlinear Hebbian-like learning rules
- Independent component analysis, a new concept?
- Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures
- Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (extended abstract)
- Learning spectral clustering, with application to speech separation
- Linear and nonlinear programming.
- Provable ICA with unknown Gaussian noise, and implications for Gaussian mixtures and autoencoders
- Regularity and complexity in dynamical systems
- Tensor Decompositions for Learning Latent Variable Models (A Survey for ALT)
- The Rotation of Eigenvectors by a Perturbation. III
Cited in
(5)- Inference for low-rank tensors -- no need to debias
- Decomposition of two functions in the orthogonality equation
- Overparameterized neural networks implement associative memory
- Eigenprojections and functions of a square matrix
- Large-dimensional independent component analysis: statistical optimality and computational tractability
This page was built for publication: Eigenvectors of Orthogonally Decomposable Functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4641586)
