Accelerated algorithms for Eigen-Value Decomposition with application to spectral clustering

Songtao Lu, Zhengdao Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationConference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015
EditorsMichael B. Matthews
PublisherIEEE Computer Society
Pages355-359
Number of pages5
ISBN (Electronic)9781467385763
DOIs
StatePublished - Feb 26 2016
Event49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015 - Pacific Grove, United States
Duration: Nov 8 2015Nov 11 2015

Publication series

NameConference Record - Asilomar Conference on Signals, Systems and Computers
Volume2016-February
ISSN (Print)1058-6393

Other

Other49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015
CountryUnited States
CityPacific Grove
Period11/8/1511/11/15

    Fingerprint

Keywords

  • Eigen-value decomposition
  • Nesterov acceleration
  • distributed implementation
  • spectral clustering

Cite this

Lu, S., & Wang, Z. (2016). Accelerated algorithms for Eigen-Value Decomposition with application to spectral clustering. In M. B. Matthews (Ed.), Conference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015 (pp. 355-359). [7421146] (Conference Record - Asilomar Conference on Signals, Systems and Computers; Vol. 2016-February). IEEE Computer Society. https://doi.org/10.1109/ACSSC.2015.7421146