Applied and Computational Harmonic Analysis

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.