Robust distance metric learning via simultaneous ℓ₁-norm minimization and maximization

Traditional distance metric learning with side information usually formulates the objectives using the covariance matrices of the data point pairs in the two constraint sets of must-links and cannot-links. Because the covariance matrix computes the sum of the squared ℓ₁-norm distances, it is prone to both outlier samples and outlier features. To develop a robust distance metric learning method, we propose a new objective for distance metric learning using the ℓ₁-norm distances. The resulted objective is challenging to solve, because it simultaneously minimizes and maximizes (minmax) a number of non-smooth ℓ₁-norm terms. As an important theoretical contribution of this paper, we systematically derive an efficient iterative algorithm to solve the general ℓ₁-norm minmax problem. We performed extensive empirical evaluations, where our new distance metric learning method outperforms related state-of-the-art methods in a variety of experimental settings.