Truncated power method for sparse eigenvalue problems

Xiao Tong Yuan, Tong Zhang

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)899-925
Number of pages27
JournalJournal of Machine Learning Research
Issue number1
StatePublished - Apr 2013
Externally publishedYes


  • Densest k-subgraph
  • Power method
  • Sparse eigenvalue
  • Sparse principal component analysis

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Software
  • Statistics and Probability
  • Artificial Intelligence


Dive into the research topics of 'Truncated power method for sparse eigenvalue problems'. Together they form a unique fingerprint.

Cite this