Distance Metric Learning by Optimization on the Stiefel Manifold

Ankita Shukla and Saket Anand

Abstract

Distance metric learning has proven to be very successful in various problem domains. Most techniques learn a global metric in the form of a nxn symmetric positive semidefinite (PSD) Mahalanobis distance matrix, which has O(n^2) unknowns. The PSD constraint makes solving the metric learning problem even harder making it computationally intractable for high dimensions. In this work, we propose a flexible formulation that can employ different regularization functions, while implicitly maintaining the positive semidefiniteness constraint. We achieve this by eigendecomposition of the rank p Mahalanobis distance matrix followed by a joint optimization on the Stiefel manifold S_{n,p} and the positive orthant R^p_+. The resulting nonconvex optimization problem is solved by employing an alternating strategy. We use a recently proposed projection free approach for efficient optimization over the Stiefel manifold. Even though the problem is nonconvex, we empirically show competitive classification accuracy on UCI and USPS digits datasets.

Session

Workshop: 1st International Workshop on DIFFerential Geometry in Computer Vision for Analysis of Shapes, Images and Trajectories (DIFF-CV)

Files

Paper (PDF, 279K)

DOI

10.5244/C.29.DIFFCV.7
https://dx.doi.org/10.5244/C.29.DIFFCV.7

Citation

Bibtex

@inproceedings{DIFFCV2015_7,
	title={Distance Metric Learning by Optimization on the Stiefel Manifold},
	author={Ankita Shukla and Saket  Anand},
	year={2015},
	month={September},
	pages={7.1-7.10},
	articleno={7},
	numpages={10},
	booktitle={Proceedings of the 1st International Workshop on DIFFerential Geometry in Computer Vision for Analysis of Shapes, Images and Trajectories (DIFF-CV 2015)},
	publisher={BMVA Press},
	editor={H. Drira, S. Kurtek, and P. Turaga},
	doi={10.5244/C.29.DIFFCV.7},
	isbn={1-901725-56-1},
	url={https://dx.doi.org/10.5244/C.29.DIFFCV.7}
}