A Scalable Dual Approach to Semidefinite Metric Learning

Author:

Shen, Chunhua; Kim, Junae; Wang, Lei

Date of Publication:

2011-06-20

Publication Type:

Conference Material

Conference Name:

IEEE Computer Vision and Pattern Recognition (CVPR) 2011

Conference Location:

Colorado Springs, USA

Pages:

2601 - 2608

Abstract:

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

URL:

http://cvpr2011.org/

Identifier:

nicta:4745

Attribution Statement:

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.