An Inverse Power Method for Nonlinear Eigenproblems with Applications in 1-Spectral Clustering and Sparse PCA

Abstract

Many problems in machine learning and statistics can be formulated as (generalized) eigenproblems. In terms of the associated optimization problem, computing linear eigenvectors amounts to finding critical points of a quadratic function subject to quadratic constraints. In this paper we show that a certain class of constrained optimization problems with nonquadratic objective and constraints can be understood as nonlinear eigenproblems. We derive a generalization of the inverse power method which is guaranteed to converge to a nonlinear eigenvector. We apply the inverse power method to 1-spectral clustering and sparse PCA which can naturally be formulated as nonlinear eigenproblems. In both applications we achieve state-of-the-art results in terms of solution quality and runtime. Moving beyond the standard eigenproblem should be useful also in many other applications and our inverse power method can be easily adapted to new problems.

Long version of paper accepted at NIPS 2010

References in corpus (2)

• Generalized power method for sparse principal component analysis
• Optimal Solutions for Sparse Principal Component Analysis

Cited by in corpus (40)

• On the Graph Fourier Transform for Directed Graphs
• Continuum limit of total variation on point clouds
• Accelerated Schemes for the $L_1/L_2$ Minimization
• The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited
• Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering
• Tensor Regression Using Low-rank and Sparse Tucker Decompositions
• General Cheeger inequalities for p-Laplacians on graphs
• Nodal Domains of Eigenvectors for $1$-Laplacian on Graphs
• Hodge Laplacians on graphs
• Community detection in networks via nonlinear modularity eigenvectors
• Quasi-Likelihood and/or Robust Estimation in High Dimensions
• $p$-Laplace Operators for Oriented Hypergraphs
• An Adaptive Total Variation Algorithm for Computing the Balanced Cut of a Graph
• Energy Models for Better Pseudo-Labels: Improving Semi-Supervised Classification with the 1-Laplacian Graph Energy
• Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality
• Tight Continuous Relaxation of the Balanced $k$-Cut Problem
• Nonlinear Power Method for Computing Eigenvectors of Proximal Operators and Neural Networks
• Eigenvalue Problems in ${\mathrm{L}}^{\infty }$: Optimality Conditions, Duality, and Relations with Optimal Transport
• Gradient Flows and Nonlinear Power Methods for the Computation of Nonlinear Eigenfunctions
• Convex variational methods for multiclass data segmentation on graphs
• Homological eigenvalues of graph $p$-Laplacians
• Variational limits of k-NN graph based functionals on data clouds
• Spectrum of the 1-Laplacian and Cheeger's constant on graphs
• Revealing Stable and Unstable Modes of Generic Denoisers through Nonlinear Eigenvalue Analysis
• A Bounded-error Quantum Polynomial Time Algorithm for Two Graph Bisection Problems
• Generalizing diffuse interface methods on graphs: non-smooth potentials and hypergraphs
• Convergence of a Steepest Descent Algorithm for Ratio Cut Clustering
• A note on limit of first eigenfunctions of $p$-Laplacian on graphs
• Non-Negative Spherical Relaxations for Universe-Free Multi-Matching and Clustering
• On the behavior of $1$-Laplacian Ratio Cuts on nearly rectangular domains
• Analysis of The Ratio of ${\ell }_1$ and ${\ell }_2$ Norms in Compressed Sensing
• The $1$-Laplacian Cheeger Cut: Theory and Algorithms
• Linearizability of eigenvector nonlinearities
• A Mathematical Approach to Constraining Neural Abstraction and the Mechanisms Needed to Scale to Higher-Order Cognition
• ${\ell }_1$-minimization method for link flow correction
• The Pseudo-orthogonality for Graph $1$-Laplacian Eigenvectors and Applications to Higher Cheeger Constants and Data Clustering
• Approximation Theorem for Principal Eigenvalue of Discrete $p$-Laplacian
• An iterative coordinate descent algorithm to compute sparse low-rank approximations
• Spectrum of signless 1-Laplacian on simplicial complexes
• The self-consistent field iteration for p-spectral clustering