A Scalable Dual Approach to Semidefinite Metric Learning
Shen, Chunhua; Kim, Junae; Wang, Lei
2011-06-20
Conference Material
IEEE Computer Vision and Pattern Recognition (CVPR) 2011
Colorado Springs, USA
2601 - 2608
Distance metric learning plays an important role in many vision problems. Previous work of quadratic Mahalanobis metric learning usually needs to solve a semidefinite programming (SDP) problem. A standard interiorpoint SDP solver has a complexity of O(n^6.5) (with n the number of variables), and can only solve problems up to a few thousand variables. Since the number of variables is D(D + 1)/2 (D is the dimension of input data), this corresponds to a limit around D < 100. This high complexity hampers the application of metric learning to highdimensional problems. In this work, we propose a very efficient approach to this metric learning problem. We formulate a Lagrange dual approach which is much simpler to optimize, and we can solve much larger Mahalanobis metric learning problems. Roughly, the proposed approach has a time complexity of O(t · D^3) with t ≈ 20 ∼ 30 for most problems in our experiments. The proposed algorithm is scalable and easy to implement. Experiments on various datasets show its similar accuracy compared with state-ofthe- art. We also demonstrate that this idea may also be able to be applied to other SDP problems such as maximum variance unfolding.
distance metric learning, dual approach, semidefinite programming
nicta:4745
Shen, Chunhua; Kim, Junae; Wang, Lei. A Scalable Dual Approach to Semidefinite Metric Learning. In: IEEE Computer Vision and Pattern Recognition (CVPR) 2011; Colorado Springs, USA. 2011-06-20. 2601 - 2608.
Loading citation data...
Citation counts
(Requires subscription to view)