Most work on metric learning learns a Mahalanobis distance, which generalizes the standard squared Euclidean distance by modeling the similarity of elements in different dimensions using a positive semi-definite matrix A.
given two vectors x and y, their squared Mahalanobis distance is: the computational complexity of learning a general Mahalanobis matrix is at least O(n 2 ), where n is the dimensionality of the input vectors.