TY - GEN
T1 - A scalable dual approach to semidefinite metric learning
AU - Shen, Chunhua
AU - Kim, Junae
AU - Wang, Lei
PY - 2011
Y1 - 2011
N2 - Distance metric learning plays an important role in many vision problems. Previous work of quadratic Maha-lanobis metric learning usually needs to solve a semidefinite programming (SDP) problem. A standard interior-point SDP solver has a complexity of O(D 6.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 ̇ 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-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.
AB - Distance metric learning plays an important role in many vision problems. Previous work of quadratic Maha-lanobis metric learning usually needs to solve a semidefinite programming (SDP) problem. A standard interior-point SDP solver has a complexity of O(D 6.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 ̇ 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-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.
UR - http://www.scopus.com/inward/record.url?scp=80052905593&partnerID=8YFLogxK
U2 - 10.1109/CVPR.2011.5995447
DO - 10.1109/CVPR.2011.5995447
M3 - Conference contribution
SN - 9781457703942
T3 - Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
SP - 2601
EP - 2608
BT - 2011 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011
PB - IEEE Computer Society
ER -