A Fast Algorithm for Manifold Learning by Posing it as a Symmetric Diagonally Dominant Linear System

April 15, 2016

Applied and Computational Harmonic Analysis


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. 

Related Content