  In linear distance metric learning, we are given data in one Euclidean metric
space and the goal is to find an appropriate linear map to another Euclidean
metric space which respects certain distance conditions as much as possible. In
this paper, we formalize a simple and elegant method which reduces to a general
continuous convex loss optimization problem, and for different noise models we
derive the corresponding loss functions. We show that even if the data is
noisy, the ground truth linear metric can be learned with any precision
provided access to enough samples, and we provide a corresponding sample
complexity bound. Moreover, we present an effective way to truncate the learned
model to a low-rank model that can provably maintain the accuracy in loss
function and in parameters -- the first such results of this type. Several
experimental observations on synthetic and real data sets support and inform
our theoretical results.
