Source-linked AI summary
An Inverse Power Method for Nonlinear Eigenproblems with Applications in 1-Spectral Clustering and Sparse PCA
Matthias Hein, Thomas Bühler
TL;DR
The paper addresses the restriction that standard eigenvalue formulations use quadratic objectives and constraints. It models ratios of p-homogeneous functions as nonlinear eigenproblems and generalizes the inverse power method, which converges to nonlinear eigenvectors and achieves state-of-the-art solution quality and runtime in 1-spectral clustering and sparse PCA.
Problem
Standard eigenvalue formulations rely on quadratic objectives and constraints, limiting modeling flexibility, while sparse PCA additionally seeks interpretable components with few nonzero features that retain variance.
Method
The paper formulates ratios of p-homogeneous functions as nonlinear eigenproblems and develops a general inverse power method, including application-specific adaptations.
Results
The inverse power method is guaranteed to converge to a nonlinear eigenvector and achieves state-of-the-art solution quality and runtime in 1-spectral clustering and sparse PCA.
Takeaways & Limitations
Moving beyond standard eigenproblems provides a framework adaptable to applications such as 1-spectral clustering and sparse PCA.
Takeaways & Limitations
For the 1-Laplacian application, convergence to the second eigenvector cannot be guaranteed, so multiple random initializations are recommended.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper generalizes eigenvalue modeling beyond ratios of quadratic functions by introducing nonlinear eigenproblems and an efficient inverse power method. It applies this method to 1-spectral clustering and sparse PCA.
- Eigenvalue problems are abundant in machine learning and statistics, but quadratic objectives and constraints restrict modeling flexibility.
- The paper formulates ratios of p-homogeneous functions as nonlinear eigenvalue problems associated with nonlinear operators.
- The proposed inverse power method is general-purpose and can be adapted to particular applications.
- For 1-spectral clustering, the method efficiently computes 1-Laplacian eigenvectors and improves runtime and Cheeger cuts over prior p-spectral clustering.Unlike the cited alternative, the method is guaranteed to converge to a 1-Laplacian eigenvector.
- Sparse PCA is formulated as a nonlinear eigenvalue problem and efficiently solved with the inverse power method to balance interpretability and explained variance.The goal is to retain only a few nonzero features while explaining most of the variance.
2 Nonlinear Eigenproblems
The paper extends the standard quadratic eigenproblem to ratios of convex, Lipschitz, even, positively p-homogeneous functions. It connects nonlinear eigenvectors to critical points and develops the associated nonsmooth formulation.
- The standard eigenproblem characterizes eigenvectors as critical points of a quadratic ratio, but this ratio imposes a severe modeling restriction.
- The generalized functional uses convex, Lipschitz continuous, even, positively p-homogeneous functions R and S, with S(f)=0 only when f=0.The standard eigenvalue functional is a special case of this formulation.
- In the differentiable case, critical points satisfy a nonlinear eigenproblem involving the gradient operators r(f)=∇R(f) and s(f)=∇S(f).When both functions are quadratic, these operators become linear and recover the standard eigenproblem.
- For nonsmooth functionals, critical points are defined through the generalized gradient, with 0 ∈ ∂F characterizing criticality.This extends the differentiable condition that a gradient vanishes at a critical point.
- The generalized Euler identity links p-homogeneity to the relation ⟨x,r*⟩=pR(x), supporting the eigenvalue characterization.The nonsmooth operators may be set-valued, but are single-valued almost everywhere under the stated Lipschitz assumptions.
- A nonlinear eigenproblem is necessary for a critical point, and becomes sufficient when S is continuously differentiable at that point.
3 The inverse power method for nonlinear Eigenproblems
The inverse power method generalizes inverse iteration to convex, positively p-homogeneous nonlinear eigenproblems. Its iterates decrease the objective and converge to a nonlinear eigenvector, although convergence to the smallest eigenvector is not guaranteed.
- Generalization: The inverse power method extends inverse iteration from quadratic eigenproblems to nonlinear objectives built from convex, positively p-homogeneous functionals.For p = 1, the method uses a ball constraint; for p > 1, it uses a direct generalization of the inner optimization problem.
- Practical use: The method is not guaranteed to find the smallest eigenvector, so multiple initializations can be used and the eigenvector with the smallest eigenvalue selected.The authors report that experiments often find the smallest eigenvector despite the lack of a guarantee.
- Algorithms: Algorithm 1 computes nonlinear eigenvectors for p = 1, while Algorithm 2 handles convex positively p-homogeneous functions with p > 1.Both algorithms solve convex inner optimization problems.
- Convergence: Each iteration decreases F(f^k), unless the sequence terminates, establishing monotonic descent for both algorithms.The decrease follows from the inner optimization step and the algorithms’ update rules.
- Convergence: The generated sequences converge to a nonlinear eigenvector with an associated eigenvalue.When S is continuously differentiable at the limit, the limit is also a critical point of F.
- Convergence: The limiting eigenvalue is no greater than the initial objective value, because the objective sequence is decreasing and bounded below.The proof uses compactness and subsequence convergence to identify the limiting eigenvector.
4 Application 1: 1-spectral clustering and Cheeger cuts
The paper applies its nonlinear inverse power method to 1-spectral clustering, where the 1-Laplacian targets Cheeger cuts and avoids linear eigenvector orthogonality assumptions. The method converges to a nonconstant 1-Laplacian eigenvector and guarantees a cut at least as good as standard spectral clustering.
- 4 Application 1: 1-spectral clustering and Cheeger cuts: 1-spectral clustering generalizes spectral clustering through the graph p-Laplacian, recovering the standard graph Laplacian at p = 2.For p close to one, prior work found better cuts but higher runtime.
- 4 Application 1: 1-spectral clustering and Cheeger cuts: The 1-Laplacian formulation connects its second eigenvalue exactly to the ratio Cheeger cut on connected graphs.Every nonconstant 1-Laplacian eigenvector has median zero, and Proposition 4.1 states λ2 = hRCC.
- 4.1 Modification of the IPM for computing the second eigenvector of the 1-Laplacian: Computing the second nonlinear eigenvector requires a modified inverse power method because nonlinear eigenvectors need not be orthogonal to the constant eigenvector.Direct minimization instead returns the constant first eigenvector.
- 4.1 Modification of the IPM for computing the second eigenvector of the 1-Laplacian: The method cannot guarantee convergence to the second eigenvector, so the paper recommends multiple random initializations and selecting the best ratio Cheeger cut.This contrasts with the convergence guarantee to some nonconstant eigenvector.
- 4.2 Quality guarantee for 1-spectral clustering: 1-spectral clustering always produces a ratio Cheeger cut at least as good as the one found by standard spectral clustering.The guarantee does not imply that the optimal ratio Cheeger cut is obtained.
5 Application 2: Sparse PCA
The paper formulates sparse PCA as a nonlinear eigenproblem by replacing the standard quadratic formulation with a sparsity-controlled 1-homogeneous functional. Its inverse power method yields an efficient sparse-component algorithm with an eigenvalue-dependent threshold.
- 5 Application 2: Sparse PCA: Sparse PCA seeks a small set of nonzero features that captures substantial variance, trading interpretability against explained variance.Standard PCA components are typically dense and difficult to interpret.
- 5 Application 2: Sparse PCA: Cardinality-constrained PCA is NP-hard, while simple thresholding can be misleading; prior alternatives include L1-penalized methods.The paper motivates a convex formulation instead of directly enforcing cardinality.
- 5 Application 2: Sparse PCA: The sparse PCA functional uses a convex combination of L1 and L2 norms in the numerator, controlled by α ∈[0, 1].α = 0 recovers standard PCA, whereas α = 1 gives the sparsest non-trivial solution.
- 5 Application 2: Sparse PCA: The resulting numerator and denominator are 1-homogeneous, so sparse PCA fits the paper’s nonlinear eigenproblem framework.The inner inverse-power subproblem has a closed-form solution.
- 5 Application 2: Sparse PCA: The sparse PCA algorithm uses a thresholding parameter that depends on the current eigenvalue estimate rather than remaining fixed.Empirically, this formulation requires slightly fewer iterations to converge than the compared formulation.
6 Experiments
The experiments evaluate the inverse power method (IPM) for 1-spectral clustering and sparse PCA. IPM matches or improves competing methods in clustering quality and runtime, while achieving a similar sparsity–variance trade-off in sparse PCA.
- 1-Spectral Clustering: IPM and the TV-based method yield similar two-moons results, slightly outperforming 1.1-spectral clustering and clearly outperforming standard spectral clustering.In terms of runtime, IPM and the TV-based method are on the same level.
- 1-Spectral Clustering: The USPS and MNIST experiments use recursive partitioning to reach K = 10 clusters, thresholding each subgraph eigenvector to minimize the multicut criterion.The procedure is applied consistently across methods, with specified graph-Laplacian initializations for IPM and the comparison method.
- 1-Spectral Clustering: The three nonlinear eigenvector methods clearly outperform standard spectral clustering on USPS and MNIST.IPM requires 100 runs in this experiment but achieves the best RCut on both datasets.
- 1-Spectral Clustering: A single IPM run initialized with the thresholded second 2-Laplacian eigenvector achieves a cut at least as good as standard spectral clustering for bi-partitions.This guarantee follows from Theorem 4.2 under the stated initialization.
- Sparse PCA: In sparse PCA, IPM, the L1-based single-unit power method, and the EM-based method produce very similar explained-variance versus sparsity trade-off curves.For Lung2, GCM, and Prostate1, the plots of all three methods coincide in one line.