A fast algorithm for manifold learning by posing it as a symmetric diagonally dominant linear system

Praneeth Vepakomma, Ahmed Elgammal

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

We present a fast manifold learning algorithm by formulating a new linear constraint that we use to replace the weighted orthonormality constraints within Laplacian Eigenmaps; a popular manifold learning algorithm. We thereby convert a quadratically constrained quadratic optimization problem into a simpler formulation that is a linearly constrained quadratic optimization problem. We show that solving this problem is equivalent to solving a symmetric diagonally dominant (SDD) linear system which can be solved very fast using a combinatorial multigrid (CMG) solver. In addition to this we also suggest another method that can exploit any sparsity within the graph Laplacian matrix via a fast sparse Cholesky decomposition to produce an alternative solution in addition to the SDD based method. We compare the improvements in run-times using both our SDD system based method and our fast sparse Cholesky decomposition based method against the well known Nystrom method based fast manifold learning and present competitive results.

Original languageEnglish (US)
Pages (from-to)622-628
Number of pages7
JournalApplied and Computational Harmonic Analysis
Volume40
Issue number3
DOIs
StatePublished - May 1 2016

All Science Journal Classification (ASJC) codes

  • Applied Mathematics

Keywords

  • Fast SDD solver
  • Fast manifold learning
  • Fast sparse Cholesky decomposition
  • Linearly constrained optimization
  • Symmetric diagonally dominant (SDD) system

Fingerprint

Dive into the research topics of 'A fast algorithm for manifold learning by posing it as a symmetric diagonally dominant linear system'. Together they form a unique fingerprint.

Cite this