A scalable dual approach to semidefinite metric learning

Chunhua Shen*, Junae Kim, Lei Wang

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    26 Citations (Scopus)

    Abstract

    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.

    Original languageEnglish
    Title of host publication2011 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011
    PublisherIEEE Computer Society
    Pages2601-2608
    Number of pages8
    ISBN (Print)9781457703942
    DOIs
    Publication statusPublished - 2011

    Publication series

    NameProceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
    ISSN (Print)1063-6919

    Fingerprint

    Dive into the research topics of 'A scalable dual approach to semidefinite metric learning'. Together they form a unique fingerprint.

    Cite this