Paper Info
Title
Accelerated algorithms for Eigen-Value Decomposition with application to spectral clustering
Abstract
Fast and accurate numerical algorithms for Eigen-Value Decomposition (EVD) are of great importance in solving many engineering problems. In this paper, we aim to develop algorithms for finding the leading eigen pairs with improved convergence speed compared to existing methods. We introduce several accelerated methods based on the power iterations where the main modification is to introduce a memory term in the iteration, similar to Nesterov's acceleration. Results on convergence and the speed of convergence are presented on a proposed method termed Memory-based Accelerated Power with Scaling (MAPS). Nesterov's acceleration for the power iteration is also presented. We discuss possible application of the proposed algorithm to (distributed) clustering problems based on spectral clustering. Simulation results show that the proposed algorithms enjoy faster convergence rates than the power method for matrix eigen-decomposition problems.
Year
DOI
Venue
2015
10.1109/ACSSC.2015.7421146
2015 49th Asilomar Conference on Signals, Systems and Computers
Keywords
Field
DocType
Eigen-value decomposition,Nesterov acceleration,spectral clustering,distributed implementation
Convergence (routing),Spectral clustering,Mathematical optimization,Correlation clustering,Matrix (mathematics),Computer science,Algorithm,Acceleration,Eigendecomposition of a matrix,Cluster analysis,Power iteration
Conference
Citations 
PageRank 
References 
2
0.37
6
Authors
2
Name
Order
Citations
PageRank
Songtao Lu18419.52
Zhengdao Wang21969149.43