Nearest neighbour classification requires a good distance metric. Previous approaches try to learn a quadratic distance metric learning so that observations of different classes are well separated. For high-dimensional problems, where many uninformative variables are present, it is attractive to select a sparse distance metric, both to increase predictive accuracy but also to aid interpretation of the result. We investigate the <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$\ell 1$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>ℓ</mi> <mn>1</mn> </mrow> </math> </EquationSource> </InlineEquation>-regularized metric learning problem, making a connection with the Lasso algorithm in the linear least squared settings. We show that the fitted transformation matrix is close to the desired transformation matrix in <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$\ell 1$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>ℓ</mi> <mn>1</mn> </mrow> </math> </EquationSource> </InlineEquation>-norm by assuming a version of the compatibility condition. Copyright Springer-Verlag Berlin Heidelberg 2014
