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

详细信息    查看全文

• 作者：Praneeth Vepakomma^a ; ^b ; ^{praneeth@scarletmail.rutgers.edu" class="auth_mail" title="E-mail the corresponding author} ; Ahmed Elgammal^c ; ^{elgammal@cs.rutgers.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Fast manifold learning ; Symmetric diagonally dominant (SDD) system ; Fast sparse Cholesky decomposition ; Fast SDD solver ; Linearly constrained optimization
• 刊名：Applied and Computational Harmonic Analysis
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：40
• 期：3
• 页码：622-628
• 全文大小：774 K

文摘

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.