Truncated Power Method for Sparse Eigenvalue Problems

2011/12/12 by Xiao–Tong Yuan, Tong Zhang, Yuan, Xiao-Tong +1 · 9 citations
Computer Science · Engineering · Mathematics · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.1112.2679

openalex publication_date 2011/12/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• On the distribution of the largest eigenvalue in principal components analysis
• Sparse Principal Component Analysis
• Generalized power method for sparse principal component analysis
• Augmented sparse principal component analysis for high dimensional data

Cited by

• The Convergence and Error Analysis of Coordinate Descent Methods with Compression for Full Configuration Interaction
• Sparse Principal Component Analysis with Energy Profile Dependent Sample Complexity
• A Scalable and Exact Relaxation for Densest k-Subgraph via Error Bounds
• On the Worst-Case Approximability of Sparse PCA
• An Inverse-free Truncated Rayleigh-Ritz Method for Sparse Generalized\n Eigenvalue Problem
• Non-negative Principal Component Analysis: Message Passing Algorithms\n and Sharp Asymptotics
• The Sparse Principal Component of a Constant-rank Matrix
• Fast One-Pass Sparse Approximation of the Top Eigenvectors of Huge Low-Rank Matrices? Yes, MAM^*!
• Projection Algorithms for Non-Convex Minimization with Application to Sparse Principal Component Analysis

Related

• An Inverse-free Truncated Rayleigh-Ritz Method for Sparse Generalized\n Eigenvalue Problem
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems
• An Inverse Power Method for Nonlinear Eigenproblems with Applications in\n 1-Spectral Clustering and Sparse PCA
• A simple extrapolation method for clustered eigenvalues
• New Power Method for Solving Eigenvalue Problems