Timezone: »

 
Spotlight
Fast Graph Laplacian Regularized Kernel Learning via Semidefinite–Quadratic–Linear Programming
Xiao-Ming Wu · Anthony Man-Cho So · Zhenguo Li · Shuo-Yen Robert Li

Wed Dec 09 03:34 PM -- 03:35 PM (PST) @
in Spotlights »
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 $m^{2.5}$, where m is the matrix dimension. Experimental results are also presented to show the superb computational efficiency of our approach.

Author Information

Xiao-Ming Wu (Columbia University)
Anthony Man-Cho So (CUHK)
Zhenguo Li (Huawei Noah's Ark Lab, Hong Kong)
Shuo-Yen Robert Li

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors