Truncated power method for sparse eigenvalue problems

By Xiao-Tong Yuan, Tong Zhang. Journal of machine learning research, 2011

351 citations recorded by the source corpus.

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 data sets demonstrate the competitive empirical performance of our method.

Subfields: Computational Theory and Mathematics, Geometry and Topology, Organic Chemistry

View Paper: https://www.semanticscholar.org/paper/0992a9b9011672f77b88a94ae9728a455daa1d91

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Geometry and Topology

In Organic Chemistry

Citations in the corpus

Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, neutral): “s),maximumlikelihoodestimationcanbecastasfollows maximizex x >Lx subjectto x= [xi]1in; xi2fe1; ;emg; 8i: MoreexamplesofconstrainedPCAincludeanalternativeformulationofphaseretrieval[95],sparsePCA [96],andmulti-channelblinddeconvolutionwithsparsitypriors[97]. Tosolve(96),twoalgorithmsnaturallycomei”
ECA: High-Dimensional Elliptical Component Analysis in Non-Gaussian Distributions (2013, methodology): “Ma (2013) and Yuan and Zhang (2013) proposed using modified versions of the power method to estimate eigenvectors and principal subspaces.”
Guaranteed Matrix Completion via Non-Convex Factorization (2014, result): “and our work. Finally, we note that there is a growing list of works on the theoretical guarantee of non-convex formulations for various problems, such as sparse regression (e.g. [38{40]), sparse PCA [41,42], robust PCA [43] and EM (Expected-Maximization) algorithm [44,45]. The techniques used in th”
DSD: Regularizing Deep Neural Networks with Dense-Sparse-Dense Training Flow (2016, background): “Sparsity-Constrained Optimization: Truncation-based sparse network has been theoretically analyzed for learning a broad range of statistical models in high dimensions, such as sparse linear regression [5, 7], sparse principal component analysis [6, 22, 23], and sparse latent variable model [24].”
Majorization-Minimization Algorithms in Signal Processing, Communications, and Machine Learning (2017, methodology): “It has been applied to a large number of problems since then [13], including sparse regression with non-convex or discontinuous objective functions [14]–[18], sparse principal component analysis (PCA) with cardinality constraint [19], canonical component analysis (CCA) [20], [21], covariance estimat”
An Exact Penalty Method for Binary Optimization Based on MPEC Formulation (2017, methodology): “(ii) LP relaxation gives better performance than the state-off-the-art technique TPM in some cases.”
New Algorithms for Learning Incoherent and Overcomplete Dictionaries (2013, methodology): “One alternative is to construct the connection graph G and then ﬁnd the overlapping clustering by running a truncated power method [53] on e i + e j (a vector that is one on indices i , j and zero elsewhere and ( i, j ) is an edge).”
Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension (2019, methodology): “to the largest eigenvalue is k′-sparse (or approximately sparse, i.e., there exists a k′-sparse vector close to the eigenvector in the l2 sense), then it is possible to use the Truncated Power Method [YZ13] to obtain an approximation to λ1 using O(k ·k′) space. 8.2 Approximating the Spectrum of PSD ”
Sparse PCA: Optimal rates and adaptive estimation (2012, background): “In particular, Cai, Zhang and Zhou [14] established the optimal rate of convergence for estimating a class of bandable covariance matrices under the spectral norm.”
DSD: Dense-Sparse-Dense Training for Deep Neural Networks (2016, background): “Sparsity Regularization and Hard Thresholding: the truncation-based sparse network has been theoretically analyzed for learning a broad range of statistical models in high dimensions (Langford et al. (2009); Yuan & Zhang (2013); Wang et al. (2014)).”