A Scalable Dual Approach to Semidefinite Metric Learning
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.
Keywords: distance metric learning, dual approach, semidefinite programming
|Conference/location:||IEEE Computer Vision and Pattern Recognition (CVPR) 2011|