A scalable dual approach to semidefinite metric learning



Publication Details

Shen, C., kim, j. & Wang, L. (2011). A scalable dual approach to semidefinite metric learning. IEEE CVPR 2011: IEEE Conference on Computer Vision and Pattern Recognition (pp. 2601-2608). IEEE.


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 interior-point SDP solver has a complexity of O(D6.5) (with D the dimension of input data), and can only solve problems up to a few thousand variables. Since the number of variables is D(D + l)/2, this corresponds to a limit around D <; 100. This high complexity hampers the application of metric learning to high-dimensional 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 · D3) 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-of-the-art. We also demonstrate that this idea may also be able to be applied to other SDP problems such as maximum variance unfolding.

Please refer to publisher version or contact your library.



Link to publisher version (DOI)