PaperlayerView exact revision on arXiv

Source-linked AI summary

Truncated Power Method for Sparse Eigenvalue Problems

Xiao-Tong Yuan, Tong Zhang

arXiv:1112.2679v1stat.MLcs.AI

TL;DR

The paper addresses the non-convex, NP-hard problem of extracting dominant sparse eigenvectors and the limited generality of existing theoretical guarantees. It proposes truncated power iteration, proves sparse recovery under restricted perturbation error, and reports competitive performance across sparse PCA and densest k-subgraph applications.

  • Problem

    Sparse eigenvalue optimization seeks dominant eigenvectors with at most k non-zero components, but the problem is non-convex and NP-hard and prior theory had limited generality.

  • Method

    The truncated power iteration method combines classical power iteration with truncation to maintain sparsity while approximately solving the sparse eigenvalue problem.

  • Results

    TPower has competitive sparse recovery and computational efficiency, with performance comparable to PathSPCA and GPower across synthetic and real datasets.

  • Takeaways & Limitations

    Under appropriate assumptions, TPower can approximately recover sparse dominant eigenvectors when restricted perturbation error is small, including applications in sparse PCA and densest k-subgraph.

  • Takeaways & Limitations

    The analysis intentionally uses the simpler restricted perturbation error ρ(E, s), although sharper results could be obtained with additional quantities.

Abstract

from arXiv · show

This paper considers the sparse eigenvalue problem, which is to extract dominant (largest) sparse eigenvectors with at most $k$ non-zero components. We propose a simple yet effective solution called truncated power method that can approximately solve the underlying nonconvex optimization problem. A strong sparse recovery result is proved for the truncated power method, and this theory is our key motivation for developing the new algorithm. The proposed method is tested on applications such as sparse principal component analysis and the densest $k$-subgraph problem. Extensive experiments on several synthetic and real-world large scale datasets demonstrate the competitive empirical performance of our method.

1 Introduction

The paper studies sparse eigenvalue optimization, which is non-convex and computationally difficult, and introduces TPower with recovery theory and applications.

  • Problem formulation: The largest k-sparse eigenvalue problem maximizes x⊤Ax over unit vectors with at most k non-zero entries.The sparsity level k is a design parameter, and the problem is motivated by sparse principal component analysis.
  • Motivation: Sparse PCA seeks to recover a sparse dominant eigenvector of the true covariance matrix from its noisy empirical covariance estimate.The perturbation E arises from having only finitely many empirical samples.
  • Existing challenges: The sparse eigenvalue problem is non-convex and NP-hard, while prior theoretical guarantees were limited in generality.The cited exception analyzed variable-selection consistency under a specific high-dimensional spiked covariance model.
  • Contribution: TPower approximately solves the problem by combining power iteration with truncation, and its analysis supports sparse recovery under restricted perturbation error.The result applies under relative generality when the true matrix has a sparse or approximately sparse dominant eigenvector.
  • Applications: The method is evaluated on sparse PCA and the densest k-subgraph problem using synthetic and large-scale real-world datasets.The experiments assess sparse recovery performance and computational efficiency.
  • Extensions: TPower also applies to the smallest k-sparse eigenvalue problem, which has machine-learning applications.

2 Truncated Power Method

TPower iteratively applies the power method while preserving k-sparsity through truncation and normalization. The procedure targets sparse dominant eigenvectors and can be adapted to smallest-eigenvalue cases.

  • Motivation: Exhaustive enumeration of all size-k subsets can solve the problem but is impractical because the number of subsets is exponential in k.
  • Algorithm: TPower multiplies the current sparse vector by A, retains the k largest absolute entries, and normalizes the result.Starting from a sparse approximation, it generates a sequence of k-sparse intermediate eigenvectors.
  • Algorithm: The truncation operation restricts a vector to a selected index set by keeping entries on that set and setting the others to zero.
  • Eigenvalue target: For positive semidefinite A, TPower seeks the sparse eigenvector associated with the largest eigenvalue.
  • Eigenvalue target: If the most negative eigenvalue dominates, TPower may instead find the smallest-eigenvalue sparse vector; shifting A can address this detectable case.This situation can occur only when λp(A) < 0.

3 Sparse Recovery Analysis

The analysis studies recovery of a sparse dominant eigenvector from a noisy high-dimensional matrix using restricted perturbation error. Under eigen-gap, sparsity, and initialization conditions, TPower converges with error controlled by sparse rather than full-matrix perturbations.

  • Assumptions: The relevant noise measure is the restricted perturbation error ρ(E, s), the spectral norm of sparse submatrices, even when the full perturbation norm is large.This distinction is especially important in high-dimensional settings with dense noise matrices.
  • Assumptions: The goal is to recover a unique sparse or approximately sparse dominant eigenvector from a noisy observation of the underlying matrix.The analysis assumes a nondegenerate dominant eigenvalue and sparse eigenvector, while allowing approximate sparsity through a sparse approximation.
  • Recovery theorem: Theorem 1 assumes s = 2k + ¯k, k ≥ 4¯k, and ρ(E, s) ≤ ∆λ/2, together with a sufficiently aligned k-sparse unit-norm initializer.The initialization requirement is expressed through a lower bound on |x0⊤¯x| involving δ(s).
  • Recovery theorem: When ρ(E, s) is smaller than half the eigen-gap, γ(s) < 1 and δ(s) = O(ρ(E, s)), yielding geometric convergence from a suitable initial vector.The iteration converges until reaching an error level determined by the restricted perturbation error.
  • Interpretation: The resulting bound replaces the full error ρ(E) with ρ(E, s), which can be significantly smaller when s ≪ p and provides theoretical justification for TPower.The paper presents this as a sparse recovery result in a relatively general setting.
  • Consequences and limits: Under the spiked covariance consequence, meaningful recovery can occur with n = O(¯k ln p) when a sufficiently large coordinate enables initialization.If no large initial coordinate is available, the analysis may require larger k, increasing ρ(E, s) and potentially preventing convergence to the target.

4 Applications

The applications section evaluates TPower on sparse principal component analysis and the densest k-subgraph problem, with reproducible Matlab code made available online.

  • Applications: TPower is illustrated on sparse PCA and the densest k-subgraph finding problem.The section states that these applications are used to demonstrate the method’s effectiveness.

4.1 Sparse PCA

The sparse PCA application uses TPower to optimize a cardinality-constrained formulation and obtain sparse loading vectors. The paper contrasts its covariance-based formulation and analyzable recovery guarantees with related power-truncation and greedy methods.

  • Problem formulation: Sparse PCA seeks sparse loading vectors that capture the maximum amount of variance in high-dimensional data.It extends PCA while retaining a sparsity objective.
  • TPower for sparse PCA: TPower directly applies to the sparse PCA formulation and addresses the cardinality constraint k when computing sparse loading vectors.Multiple sparse loadings can be obtained through iterative deflation.
  • Relation to prior methods: GPower and sPCA-rSVD use power-truncation procedures on data-matrix approximations, whereas TPower performs rank-1, semidefinite, sparse approximation of the covariance matrix.The methods differ in initialization and post-processing, while GPower and sPCA-rSVD are otherwise described as closely related.
  • Relation to prior methods: A key benefit of TPower is that its solution quality and sparse recovery capability can be analyzed, unlike analogous results reported for GPower and sPCA-rSVD.PathSPCA is instead characterized as greedy forward selection followed by re-estimation, and both methods output exact cardinality k solutions.

4.1.2 On Initialization

The initialization discussion presents variance-based, warm-start, and greedy backward-elimination schemes for TPower. On a synthetic sparse PCA dataset, TPower and several competitors recover the sparse components reliably, while SPCA and ordinary PCA often fail or always fail.

  • Initialization schemes: A two-stage warm start runs TPower with a larger k, then uses its output to initialize subsequent runs with decreasing cardinality.Other algorithms may also provide warm starts.
  • Initialization schemes: TPower can be initialized at the index of the largest diagonal entry, providing a 1/k-approximation to the optimal sparse objective.Selecting the top k variance entries is an alternative initialization used in sparse PCA.
  • Initialization schemes: For k ≈ p, greedy backward elimination starts from all variables and deletes one variable at a time until k remain, guaranteeing a k/p-approximation.The scheme is described as suitable for relatively small p because it becomes computationally challenging when p is large.
  • Toy dataset: The synthetic experiment uses p = 500, n = 50, two sparse dominant eigenvectors, and eigenvalues λ1 = 400, λ2 = 300, λj = 1 for j = 3, ..., 500.Five hundred data matrices are generated, and the methods compute two unit-norm sparse loading vectors.
  • Toy dataset: Recovery is counted when both |v1⊤u1| and |v2⊤u2| exceed 0.99, with known cardinality k = 10.The comparison includes TPower, PathPCA, GPower, SPCA, and standard PCA.
  • Toy dataset: TPower, PathPCA, and GPower recover the ground-truth sparse components at extremely high rates, whereas SPCA frequently fails and traditional PCA always fails on this dataset.The paper attributes SPCA’s failures partly to initialization by ordinary principal components.

4.1.4 Speed and Scaling Test

TPower’s computational cost is evaluated across datasets with increasing dimensionality and cardinality, using average running time and a convergence threshold. The method exits within seconds or tens of seconds across the tested settings.

  • TPower exits within seconds or tens of seconds across the tested datasets and a broad range of cardinalities k.
  • Table 4.2 measures TPower’s average CPU time for extracting one sparse component as dimensionality p and cardinality k vary.The datasets use fixed n = 500 with exponentially increasing p.

4.1.5 Results on PitProps Data

The experiments evaluate sparse-component extraction on PitProps and biological datasets, emphasizing interpretability, variance–sparsity trade-offs, and comparison with competing methods. TPower produces non-overlapping PitProps components and performance comparable to PathSPCA on gene-expression data.

  • PitProps Data: TPower extracts six PitProps sparse PCs with cardinality setting 7-2-1-1-1-1 and non-overlapping important variables.The resulting components are orthogonal and therefore support clear interpretation.
  • Biological Data: On the Colon cancer and Lymphoma datasets, TPower performs almost identically to PathSPCA, with both methods requiring less than two seconds.The comparison uses variance-versus-cardinality trade-off curves for the 500 genes with the largest variances.
  • Document Data: The first, second, and fifth sparse PCs on the document dataset correspond to figures, computer science, and religion, respectively.The third and fourth PCs are omitted because they overlap with the listed components due to sparse PCs’ non-orthogonality.
  • PitProps Data: TPower, PathSPCA, and GPower perform comparably on sparse PCA’s explained-variance versus representation-sparsity trade-off across synthetic and real datasets.On the Pitprops benchmark, all three outperform SPCA.

4.2 Densest k-Subgraph Finding

The paper adapts truncated power methods to densest k-subgraph optimization and evaluates them on web graphs and air-travel networks. TPower-DkS generally finds denser subgraphs than greedy baselines while remaining computationally efficient.

  • Problem setting: Densest k-subgraph seeks k vertices inducing maximum average degree, with weighted variants maximizing average edge weight.The problem is NP-hard across several graph classes and has motivated greedy, linear-programming, and semidefinite-programming approaches.
  • TPower-DkS algorithm: TPower-DkS multiplies the current indicator vector by W and retains the top k entries as the next subgraph indicator.For directed graphs, symmetrizing the adjacency matrix preserves the quadratic objective; the method assumes a symmetric affinity matrix.
  • TPower-DkS algorithm: The shifted quadratic formulation enforces positive semidefiniteness, but excessively large shifts make the objective approximately a squared norm and can prevent movement from the initial iterate.The algorithm therefore increases the shift gradually and only when monotonicity is violated.
  • Initialization: TPower-DkS monotonically improves its initialization, and top-k weighted-degree vertices provide a simple initialization that performed competitively on tested real-world datasets.Existing approximation methods can also supply the initial point.
  • Results on Web Graphs: On web graphs, TPower-DkS consistently produced denser subgraphs than both greedy methods on three datasets and matched Greedy-Ravi while exceeding Greedy-Feige on amazon-2008.Greedy-Feige was fastest, while TPower-DkS was only slightly slower; on hollywood-2009, runtimes were about 10 seconds versus about 1 second for Greedy-Feige.
  • Results on Air-Travel Routine: On the air-travel graph, TPower-DkS consistently outperformed both greedy methods in subgraph density and produced the densest visually inspected 30-city subgraph.It was slightly slower than Greedy-Feige but much faster than Greedy-Ravi, and its sequential outputs were more geographically compact.

5 Conclusion and Future Work

TPower approximately solves the non-convex sparse eigenvalue problem and can recover sparse solutions under perturbation conditions. Experiments in sparse PCA and densest k-subgraph finding support its effectiveness and efficiency.

  • Conclusion: TPower is a truncated power iteration method for approximately solving the non-convex sparse eigenvalue problem.The method combines classical power iteration with truncation to enforce sparsity.
  • Conclusion: Under proper conditions, TPower can approximately recover the true sparse solution when the underlying matrix has sparse eigenvectors.The reconstruction quality depends on restricted perturbation error at a size comparable to the sparsity rather than the full matrix dimension.
  • Experiments: The densest k-subgraph experiments examine density and CPU-time curves on web graphs and route-map-based air-travel data.The web-graph figure varies cardinality k, while the air-travel figure also compares sequentially discovered densest 30-subgraphs.
  • Conclusion: The reconstruction quality depends on restricted matrix perturbation error at size s comparable to the sparsity k̄, instead of the full matrix dimension p.This restricted-error dependence is presented as the theoretical benefit of the method.
  • Experiments: TPower was applied to sparse PCA and densest k-subgraph finding, with extensive synthetic and real-world experiments validating its effectiveness and efficiency.The supplied conclusion identifies both applications but does not provide aggregate numerical results here.

A Proof of Theorem 1

The proof combines perturbation bounds, ordinary power-method progress, and support truncation bounds to show that each sparse power step improves eigenvector estimation. Under restricted perturbation control and initialization conditions, induction establishes the theorem's recovery guarantee.

  • Perturbation bounds: Lemma 1 supplies eigenvalue perturbation bounds for symmetric matrices and their restricted submatrices.The proof applies it with B = Ā_F and U = E_F to bound the leading and non-leading eigenvalues of A_F.
  • Restricted matrices: If ρ(E, s) ≤ Δλ/2, Lemma 2 bounds the spectral ratio of a restricted matrix A_F and controls its leading eigenvector alignment.The restricted support F contains supp(x̄) and has size s.
  • Power iteration: Lemma 3 shows that one normalized power iteration improves alignment with the dominant eigenvector when the eigenvalue ratio γ is below one.It considers x′ = Ax/∥Ax∥ for a unit vector with positive alignment to the dominant eigenvector.
  • Truncation: Lemma 4 bounds the loss from retaining the k largest-magnitude coordinates when the target eigenvector has support size k̄.The argument partitions target and selected supports and uses an alignment condition involving k̄ and k.
  • Sparse power progress: The main lemma states that each sparse power-method step improves eigenvector estimation.Its proof combines restricted-matrix analysis, ordinary power-method progress, and the truncation bound.
  • Induction: The theorem follows by induction after establishing a uniform lower bound on alignment at every iteration.The proof invokes Lemma 5 and the initialization assumption to propagate the bound from iteration t − 1 to t.
Loading 1112.2679v1…