Fast graph laplacian regularized kernel learning via semidefinite- quadratic-linear programming

Xiaoming Wu, Anthony Man Cho So, Zhenguo Li, Shuo Yen Robert Li

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

17 Citations (Scopus)


Kernel learning is a powerful framework for nonlinear data modeling. Using the kernel trick, a number of problems have been formulated as semidefinite programs (SDPs). These include Maximum Variance Unfolding (MVU) (Weinberger et al., 2004) in nonlinear dimensionality reduction, and Pairwise Constraint Propagation (PCP) (Li et al., 2008) in constrained clustering. Although in theory SDPs can be efficiently solved, the high computational complexity incurred in numerically processing the huge linear matrix inequality constraints has rendered the SDP approach unscalable. In this paper, we show that a large class of kernel learning problems can be reformulated as semidefinite-quadratic- linear programs (SQLPs), which only contain a simple positive semidefinite constraint, a second-order cone constraint and a number of linear constraints. These constraints are much easier to process numerically, and the gain in speedup over previous approaches is at least of the order m2.5, where m is the matrix dimension. Experimental results are also presented to show the superb computational efficiency of our approach.
Original languageEnglish
Title of host publicationAdvances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference
Number of pages9
Publication statusPublished - 1 Dec 2009
Externally publishedYes
Event23rd Annual Conference on Neural Information Processing Systems, NIPS 2009 - Vancouver, BC, Canada
Duration: 7 Dec 200910 Dec 2009


Conference23rd Annual Conference on Neural Information Processing Systems, NIPS 2009
CityVancouver, BC

ASJC Scopus subject areas

  • Information Systems

Cite this