Truncated Power Method for Sparse Eigenvalue Problems

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.

References in corpus (4)

• Generalized power method for sparse principal component analysis
• Sparse principal component analysis and iterative thresholding
• Sparse PCA: Optimal rates and adaptive estimation
• Augmented sparse principal component analysis for high dimensional data

Cited by in corpus (89)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Guaranteed Matrix Completion via Non-convex Factorization
• Sparse principal component analysis and iterative thresholding
• Sparse PCA: Optimal rates and adaptive estimation
• DSD: Dense-Sparse-Dense Training for Deep Neural Networks
• Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization
• New Algorithms for Learning Incoherent and Overcomplete Dictionaries
• Active, Continual Fine Tuning of Convolutional Neural Networks for Reducing Annotation Efforts
• Statistical and computational trade-offs in estimation of sparse principal components
• A Tight Bound of Hard Thresholding
• Orthogonal Sparse PCA and Covariance Estimation via Procrustes Reformulation
• Near-Optimal Stochastic Approximation for Online Principal Component Estimation
• Statistical analysis of latent generalized correlation matrix estimation in transelliptical distribution
• Sum-of-Squares Lower Bounds for Sparse PCA
• Binary Optimization via Mathematical Programming with Equilibrium Constraints
• Sparse PCA through Low-rank Approximations
• Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time
• High Dimensional Expectation-Maximization Algorithm: Statistical Optimization and Asymptotic Normality
• Sparsistency and agnostic inference in sparse PCA
• Sparse and Functional Principal Components Analysis
• Eigenvectors from Eigenvalues Sparse Principal Component Analysis (EESPCA)
• Rate Optimal Denoising of Simultaneously Sparse and Low Rank Matrices
• Optimal linear estimation under unknown nonlinear transform
• Tight convex relaxations for sparse matrix factorization
• Sparse PCA with Oracle Property
• Addressing the Item Cold-start Problem by Attribute-driven Active Learning
• Efficient active learning of sparse halfspaces with arbitrary bounded noise
• Sparse PCA via Bipartite Matchings
• Identifiability Conditions for Compressive Multichannel Blind Deconvolution
• Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality
• Non-negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
• Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Hypothesis testing for eigenspaces of covariance matrix
• Instability, Computational Efficiency and Statistical Accuracy
• Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
• An Alternating Manifold Proximal Gradient Method for Sparse PCA and Sparse CCA
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors
• Partially Observed Dynamic Tensor Response Regression
• Scalable Interpretable Multi-Response Regression via SEED
• Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates
• A Hybrid Method of Combinatorial Search and Coordinate Descent for Discrete Optimization
• Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension
• Approximation Algorithms for Sparse Principal Component Analysis
• Provable Sparse Tensor Decomposition
• High Dimensional Semiparametric Latent Graphical Model for Mixed Data
• Sparse Generalized Eigenvalue Problem: Optimal Statistical Rates via Truncated Rayleigh Flow
• Learning Feature Sparse Principal Components
• Sparse Principal Component Analysis for High Dimensional Vector Autoregressive Models
• Greedy Algorithms for Cone Constrained Optimization with Convergence Guarantees
• Optimal Sparse Linear Auto-Encoders and Sparse PCA
• Sparse GCA and Thresholded Gradient Descent
• A Coordinate-wise Optimization Algorithm for Sparse Inverse Covariance Selection
• Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descent
• Alternating direction method of multipliers for penalized zero-variance discriminant analysis
• On the Worst-Case Approximability of Sparse PCA
• An Inverse-free Truncated Rayleigh-Ritz Method for Sparse Generalized Eigenvalue Problem
• Kurdyka-Lojasiewicz Property of Zero-Norm Composite Functions
• Learning the effect of latent variables in Gaussian Graphical models with unobserved variables
• Multichannel Sparse Blind Deconvolution on the Sphere
• On Learning Sparsely Used Dictionaries from Incomplete Samples
• On the Impact of Dimension Reduction on Graphical Structures
• An Exponential Inequality for U-Statistics under Mixing Conditions
• Fast Large-Scale Discrete Optimization Based on Principal Coordinate Descent
• Using L1-relaxation and integer programming to obtain dual bounds for sparse PCA
• Non-Sparse PCA in High Dimensions via Cone Projected Power Iteration
• Mixed-Effect Time-Varying Network Model and Application in Brain Connectivity Analysis
• Optimal Projected Variance Group-Sparse Block PCA
• Boosted Sparse Non-linear Distance Metric Learning
• One-Bit Compressed Sensing via One-Shot Hard Thresholding
• A Framework for Private Matrix Analysis
• Projection Algorithms for Non-Convex Minimization with Application to Sparse Principal Component Analysis
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems
• Low-Rank Principal Eigenmatrix Analysis
• Exploring the Subgraph Density-Size Trade-off via the Lovász Extension
• An active-set algorithm for norm constrained quadratic problems
• High Dimensional Semiparametric Scale-Invariant Principal Component Analysis
• Pursuits in Structured Non-Convex Matrix Factorizations
• Efficient Approximate Solutions to Mutual Information Based Global Feature Selection
• The Sparse Principal Component of a Constant-rank Matrix
• Practical and Fast Momentum-Based Power Methods
• Sublinear Column-wise Actions of the Matrix Exponential on Social Networks
• Sparse Logistic Tensor Decomposition for Binary Data
• A New Basis for Sparse Principal Component Analysis
• A Decomposition Algorithm for the Sparse Generalized Eigenvalue Problem
• KL property of exponent $1/2$ of quadratic functions under nonnegative zero-norm constraints and applications
• Sparse Graph-based Transduction for Image Classification
• Stay on path: PCA along graph paths
• A Fast deflation Method for Sparse Principal Component Analysis via Subspace Projections