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

Songtao Lu; Zhengdao Wang

doi:10.1109/ACSSC.2015.7421146

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

Songtao Lu, Zhengdao Wang

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 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 language	English (US)
Title of host publication	Conference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015
Editors	Michael B. Matthews
Publisher	IEEE Computer Society
Pages	355-359
Number of pages	5
ISBN (Electronic)	9781467385763
DOIs	https://doi.org/10.1109/ACSSC.2015.7421146
State	Published - Feb 26 2016
Event	49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015 - Pacific Grove, United States Duration: Nov 8 2015 → Nov 11 2015

Publication series

Name	Conference Record - Asilomar Conference on Signals, Systems and Computers
Volume	2016-February
ISSN (Print)	1058-6393

Other

Other	49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015
Country/Territory	United States
City	Pacific Grove
Period	11/8/15 → 11/11/15

Keywords

Eigen-value decomposition
Nesterov acceleration
distributed implementation
spectral clustering

Publisher link

10.1109/ACSSC.2015.7421146

Find It

Find It at U of M Libraries

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

Accelerated algorithms for Eigen-Value Decomposition with application to spectral clustering. / Lu, Songtao; Wang, Zhengdao.
Conference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015. ed. / Michael B. Matthews. IEEE Computer Society, 2016. p. 355-359 7421146 (Conference Record - Asilomar Conference on Signals, Systems and Computers; Vol. 2016-February).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Lu, S & Wang, Z 2016, Accelerated algorithms for Eigen-Value Decomposition with application to spectral clustering. in MB Matthews (ed.), Conference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015., 7421146, Conference Record - Asilomar Conference on Signals, Systems and Computers, vol. 2016-February, IEEE Computer Society, pp. 355-359, 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015, Pacific Grove, United States, 11/8/15. https://doi.org/10.1109/ACSSC.2015.7421146

Lu S, Wang Z. Accelerated algorithms for Eigen-Value Decomposition with application to spectral clustering. In Matthews MB, editor, Conference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015. IEEE Computer Society. 2016. p. 355-359. 7421146. (Conference Record - Asilomar Conference on Signals, Systems and Computers). doi: 10.1109/ACSSC.2015.7421146

Lu, Songtao ; Wang, Zhengdao. / Accelerated algorithms for Eigen-Value Decomposition with application to spectral clustering. Conference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015. editor / Michael B. Matthews. IEEE Computer Society, 2016. pp. 355-359 (Conference Record - Asilomar Conference on Signals, Systems and Computers).

@inproceedings{d6e3e2620e214e5e8ca67df5e0d7d952,

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.",

keywords = "Eigen-value decomposition, Nesterov acceleration, distributed implementation, spectral clustering",

author = "Songtao Lu and Zhengdao Wang",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE. Copyright: Copyright 2017 Elsevier B.V., All rights reserved.; 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015 ; Conference date: 08-11-2015 Through 11-11-2015",

year = "2016",

month = feb,

day = "26",

doi = "10.1109/ACSSC.2015.7421146",

language = "English (US)",

series = "Conference Record - Asilomar Conference on Signals, Systems and Computers",

publisher = "IEEE Computer Society",

pages = "355--359",

editor = "Matthews, {Michael B.}",

booktitle = "Conference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015",

}

TY - GEN

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

AU - Lu, Songtao

AU - Wang, Zhengdao

PY - 2016/2/26

Y1 - 2016/2/26

N2 - 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.

AB - 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.

KW - Eigen-value decomposition

KW - Nesterov acceleration

KW - distributed implementation

KW - spectral clustering

UR - http://www.scopus.com/inward/record.url?scp=84969776486&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84969776486&partnerID=8YFLogxK

U2 - 10.1109/ACSSC.2015.7421146

DO - 10.1109/ACSSC.2015.7421146

M3 - Conference contribution

AN - SCOPUS:84969776486

T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers

SP - 355

EP - 359

BT - Conference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015

A2 - Matthews, Michael B.

PB - IEEE Computer Society

T2 - 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015

Y2 - 8 November 2015 through 11 November 2015

ER -

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

Abstract

Publication series

Other

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this