2.5 Learned metrics and random projections

Dimensionality reduction can change a geometry deliberately or preserve a geometry approximately. Metric learning uses information about similarity to decide which directions should matter. Random projection uses an independently sampled map to preserve the distances of a fixed finite collection of points. Both approaches apply linear maps, but their assumptions and success criteria are different. Writing each map as a matrix makes those differences precise.

Motivation

Euclidean distance adds squared coordinate differences with equal weights. That choice has consequences when measurements use different units, or when some features are informative for a classification task and others are not. A learned geometry can rescale directions, combine correlated features, and identify variations that should be ignored for the task.

Random projection addresses another question. Suppose the existing Euclidean geometry is useful, but each point has thousands of coordinates. We want a shorter representation whose distances remain close on the objects under consideration. The target is simultaneous accuracy on finitely many pairwise differences, rather than an invertible transformation of the entire original space. This distinction permits a substantial reduction in dimension.

Definitions

Definition

Mahalanobis geometry and squared distances

For a symmetric positive semidefinite matrix $M\in\mathbb R^{d\times d}$, define

$$d_M(x,y)=\sqrt{(x-y)^TM(x-y)},\qquad \Delta_{ij}(M)=d_M(x_i,x_j)^2.$$

If $M=L^TL$ with $L\in\mathbb R^{r\times d}$, then

$$d_M(x,y)=\|Lx-Ly\|_2.$$

The squared form $\Delta_{ij}$ is convenient for optimization. The distance $d_M$, including its square root, is the object whose triangle inequality we will establish.

A spectral decomposition supplies such a factor $L$: take square roots of the positive eigenvalues and retain their eigenvectors. The smallest number of rows needed is $r=\operatorname{rank}(M)$. A low-rank learned matrix thus describes both a geometry and a representation with fewer coordinates.

Proposition

Positive semidefinite gives a pseudometric; positive definite gives a metric

For $M\succeq0$, the function $d_M$ is a pseudometric: it is nonnegative, symmetric, zero on identical points, and satisfies the triangle inequality. It is a metric on all of $\mathbb R^d$ exactly when $M\succ0$.

If $M$ is singular, distinct points have zero distance precisely when their difference belongs to $\ker(M)=\ker(L)$.

The proof follows the linear representation. Euclidean norms give

$$\|L(x-z)\|_2 \le\|L(x-y)\|_2+\|L(y-z)\|_2.$$

Also $(x-y)^TM(x-y)=\|L(x-y)\|_2^2$ vanishes exactly when $L(x-y)=0$. A positive definite matrix has no nonzero null direction; a singular positive semidefinite matrix does. On a particular finite set, a singular matrix can still separate every distinct pair if none of their differences lies in that nullspace. Global invertibility and separation of the observed objects are therefore different requirements.

Learning from labeled neighbors

Choose a fixed set $T_i$ of same-class target neighbors, excluding the anchor itself, for each anchor $x_i$. Let $\mathcal I_i$ contain indices with a different class label, and take $\lambda\ge0$. One large-margin nearest-neighbor objective is

$$F(M)=\sum_i\sum_{j\in T_i}\Delta_{ij}(M) +\lambda\sum_i\sum_{j\in T_i}\sum_{\ell\in\mathcal I_i} [1+\Delta_{ij}(M)-\Delta_{i\ell}(M)]_+, \qquad M\succeq0,$$

where $[a]_+=\max(a,0)$. The first term pulls each target neighbor closer. The hinge term penalizes an impostor whose squared distance falls below the target's squared distance plus a margin of one. The margin is expressed in squared distances; it is not a difference of ordinary Euclidean lengths.

For $v_{ij}=x_i-x_j$, define $A_{ij}=v_{ij}v_{ij}^T$. Then

$$\Delta_{ij}(M)=\operatorname{tr}(MA_{ij}).$$

This expression is linear in $M$. With the target sets fixed, every hinge is the maximum of zero and an affine function of $M$, so it is convex. Adding these terms preserves convexity, and the positive semidefinite constraint defines a convex feasible set. Thus this version of the learning problem is convex in the matrix variable.

The same claim can be seen using one slack variable per triplet. Require $\xi_{ij\ell}\ge0$ and $\xi_{ij\ell}\ge1+\Delta_{ij}(M)-\Delta_{i\ell}(M)$, then minimize the pull term plus $\lambda\sum\xi_{ij\ell}$. All these inequalities are affine in $M$ and the slacks. Keeping the neighbor sets fixed is essential to this argument; changing them changes which terms enter the objective.

Rank and the choice of optimization variable

Positive semidefiniteness alone does not force a low-rank answer. Imposing $\operatorname{rank}(M)\le r$ selects a generally nonconvex set. Alternatively, optimizing $L\in\mathbb R^{r\times d}$ and setting $M=L^TL$ enforces that rank limit automatically, but the objective as a function of $L$ is generally nonconvex. An equivalent representation of distances need not give an equivalent convex optimization problem. The example below makes this failure visible even with a single scalar factor.

Interpreting a learned geometry

For a diagonal matrix, the squared distance weights each coordinate separately. A full matrix also contains cross terms:

$$v^TMv=\sum_a M_{aa}v_a^2+2\sum_{a<b}M_{ab}v_av_b.$$

Those terms allow the learned map to identify combinations of coordinates. For example, the form $(v_1-v_2)^2$ measures change in a difference and ignores equal changes in both coordinates. Its negative off-diagonal entries are compatible with a positive semidefinite matrix. The eigenvectors specify directions being measured; eigenvalues specify their squared-distance weights. Looking at both makes a fitted matrix easier to interpret than looking only at individual diagonal entries.

Units can be handled explicitly through a change of coordinates. If $z=Sx$ for an invertible matrix $S$, the same geometry has matrix

$$M_z=S^{-T}M_xS^{-1}.$$

Substitution shows that the quadratic difference is unchanged. This congruence also preserves positive semidefiniteness and rank. Rescaling the input table while keeping the matrix fixed, in contrast, changes the geometry being fitted. The feature representation and the learned matrix should therefore be interpreted together.

The pull and push terms also determine scale. At $M=0$ all points collapse, the pull term is zero, and every included hinge equals one. With $\lambda=0$ that collapsed solution is optimal. A positive push weight introduces the margin cost and trades it against the target distances. The constant one in the margin fixes a squared-distance scale; multiplying $M$ by a scalar does not generally preserve the objective. This differs from simply rotating the rows of a factor, which preserves $L^TL$ and all learned distances.

Gaussian random projection

Now fix the points independently of the random map. Sample all entries of $R\in\mathbb R^{k\times d}$ independently with

$$R_{ab}\sim\mathcal N(0,1/k),\qquad f(x)=Rx.$$

The variance is $1/k$, so the standard deviation used to generate entries is $1/\sqrt{k}$. The rows need not be orthogonal. For any fixed nonzero difference $v$, independent rows give

$$(Rv)_a\sim\mathcal N(0,\|v\|_2^2/k),\qquad \frac{k\|Rv\|_2^2}{\|v\|_2^2}\sim\chi_k^2.$$

Consequently $\mathbb E\|Rv\|_2^2=\|v\|_2^2$. Equality in expectation is a statement about repeated draws of the map for that fixed difference. It does not say that a particular draw preserves even one distance exactly.

The normalized squared-length ratio has variance $2/k$, since a chi-square variable with $k$ degrees of freedom has variance $2k$. This gives a first indication of concentration as the projected dimension grows. The exponential bound below is stronger: it makes simultaneous control over a growing collection of differences possible with only logarithmic dependence on the number of points.

Theorem

A simultaneous finite-set projection bound

Let $0<\varepsilon<1$, $0<\delta<1$, and let $n\ge2$ fixed points be independent of $R$. Define

$$c_\varepsilon=\frac{\varepsilon^2}{4}-\frac{\varepsilon^3}{6}, \qquad N=\frac{n(n-1)}2.$$

The probability that any pair violates

$$(1-\varepsilon)\|x_i-x_j\|_2^2 \le\|R(x_i-x_j)\|_2^2 \le(1+\varepsilon)\|x_i-x_j\|_2^2$$

is at most $2N\exp(-kc_\varepsilon)$. In particular, the sufficient choice

$$k\ge\left\lceil\frac{\log(2N/\delta)}{c_\varepsilon}\right\rceil$$

makes all pairwise bounds hold with probability at least $1-\delta$. Here $\log$ denotes the natural logarithm.

The guarantee uses squared lengths. The corresponding ordinary lengths lie between $\sqrt{1-\varepsilon}$ and $\sqrt{1+\varepsilon}$ times their original values. Zero differences remain zero under every linear map and require no probabilistic estimate.

From one difference to all pairs

Proof

Chi-square concentration and the union bound

For $Z\sim\chi_k^2$, its moment generating function is $\mathbb E e^{tZ}=(1-2t)^{-k/2}$ for $t<1/2$. Applying the exponential Markov inequality and optimizing $t$ gives

$$\Pr(Z\ge k(1+\varepsilon)) \le e^{-k(\varepsilon-\log(1+\varepsilon))/2}, \qquad \Pr(Z\le k(1-\varepsilon)) \le e^{-k(-\varepsilon-\log(1-\varepsilon))/2}.$$

For $0<\varepsilon<1$, integration of $t/(1+t)\ge t-t^2$ and $t/(1-t)\ge t$ on $[0,\varepsilon]$ yields

$$\varepsilon-\log(1+\varepsilon) \ge\varepsilon^2/2-\varepsilon^3/3, \qquad -\varepsilon-\log(1-\varepsilon)\ge\varepsilon^2/2.$$

Both tails are therefore bounded by $e^{-kc_\varepsilon}$, giving a two-sided bound of $2e^{-kc_\varepsilon}$ for one nonzero difference. Apply this result to the at most $N$ unordered pairs and add their failure probabilities. The pairwise events need not be independent for this union bound. Solving $2Ne^{-kc_\varepsilon}\le\delta$ gives the displayed dimension choice.

Since $c_\varepsilon\ge\varepsilon^2/12$ in this interval, a sufficient dimension has order $\varepsilon^{-2}(\log n+\log(1/\delta))$, with no original dimension $d$ in that expression. Fixing a failure probability below one gives a positive probability of success, which proves that a suitable map exists. This is the Johnson–Lindenstrauss existence conclusion. The explicit probability bound additionally specifies how likely a fresh Gaussian draw is to succeed.

If this sufficient dimension is larger than $d$, the estimate does not certify dimensional reduction for those parameters. It does not prove that every smaller-dimensional representation must fail. Its role is to certify a chosen construction uniformly over the specified finite set.

Worked examples

Worked example

Example 1: A learned null direction collapses distinct points

Take

$$L=\begin{bmatrix}1&-1\end{bmatrix},\qquad M=L^TL=\begin{bmatrix}1&-1\\-1&1\end{bmatrix}.$$

Its eigenvalues are $2$ and $0$, so the learned representation has one coordinate. Points $(0,0)$ and $(1,1)$ both map to zero and have learned distance zero. The point $(1,0)$ maps to one and is distance one from either of those points. These values satisfy the pseudometric properties while identifying variations along the direction $(1,1)$.

Adding the identity gives

$$M+I_2=\begin{bmatrix}2&-1\\-1&2\end{bmatrix},$$

whose eigenvalues are $3$ and $1$. It defines a metric on the whole plane; the formerly collapsed pair now has distance $\sqrt2$. The additional positive direction restores separation in that direction and makes the matrix full rank. This change alters the chosen geometry rather than merely changing a coordinate notation.

Worked example

Example 2: Convex matrix learning, nonconvex factor learning

Use one anchor at $0$, one same-class target at $1$, and an impostor at $2$. In one dimension let $M=[m]$, with $m\ge0$, and set $\lambda=1$. The anchored loss is

$$F(m)=m+[1+m-4m]_+ =\begin{cases}1-2m,&0\le m\le1/3,\\m,&m\ge1/3.\end{cases}$$

The slope changes from $-2$ to $1$, so the function is convex. Its minimum is $1/3$ at $m=1/3$. At that point the impostor's squared distance exceeds the target's by $4m-m=1$, exactly the required margin.

Factor $m=\ell^2$. The objective becomes $F(\ell^2)=\ell^2+[1-3\ell^2]_+$. At $\ell=\pm1/\sqrt3$ its value is $1/3$, but at their midpoint $\ell=0$ it is $1$. This violates the defining midpoint inequality for a convex function. Factoring enforces positivity, yet loses convexity in the factor variable. The distinction persists in higher-dimensional low-rank parameterizations.

Worked example

Example 3: Choose a dimension with a stated failure probability

Take $n=20$, original dimension $d=2000$, squared-distance tolerance $\varepsilon=1/2$, and desired failure probability $\delta=1/10$. Then

$$N=190,\qquad c_\varepsilon=\frac1{24},\qquad k=\lceil24\log(3800)\rceil=198.$$

The bound on failure is $380e^{-198/24}\approx0.099278$, which is below $0.1$. Thus a fresh Gaussian map into $198$ coordinates succeeds on every pair with probability at least $0.9$. This is a simultaneous guarantee for the given twenty points; it is not a claim that every direction in $\mathbb R^{2000}$ has its length preserved.

Indeed a $198\times2000$ matrix has a nontrivial kernel. Its induced matrix $R^TR$ is singular and defines only a pseudometric on the full space. The finite collection can nevertheless avoid all collapsed pairwise differences. There is no contradiction between a low-rank map and accurate distances on the prescribed finite set.

A reproducible projection experiment

This example first creates a dataset, then fixes it before drawing the projection. Rows store points, so their transformed table is $XR^T$. For the stated seed, the smallest and largest squared-distance ratios are approximately $0.715409$ and $1.305531$, inside the required interval $[0.5,1.5]$.

import numpy as np

n, d, epsilon, delta = 20, 2000, 0.5, 0.1
pairs = n * (n - 1) // 2
c = epsilon**2 / 4 - epsilon**3 / 6
k = int(np.ceil(np.log(2 * pairs / delta) / c))
rng = np.random.default_rng(2026)
X = rng.normal(size=(n, d))
R = rng.normal(size=(k, d)) / np.sqrt(k)
Y = X @ R.T
i, j = np.triu_indices(n, k=1)
original = np.sum((X[i] - X[j])**2, axis=1)
projected = np.sum((Y[i] - Y[j])**2, axis=1)
ratios = projected / original
print(k)
print(np.round([ratios.min(), ratios.max()], 6))

The experiment checks all $190$ observed pairs for one sampled map. The probability theorem describes repeated random draws conditional on the fixed dataset, while this output records one realization. Both forms of evidence answer useful but different questions about the construction.

Common mistakes

Common mistake

Changing the mathematical object or the probability claim

A positive semidefinite matrix can collapse a nonzero difference; use positive definiteness when a metric on the entire space is required. Squared distances are linear in $M$ but generally do not satisfy a triangle inequality: on a line, the squared distance from $0$ to $2$ is $4$, larger than $1+1$ through the point $1$.

For random projection, a correct expected squared length does not establish a simultaneous high-probability bound. Concentration controls one fixed difference, and the union bound controls the finite collection. Choosing a new difference from the kernel after observing $R$ does not meet the fixed-set assumption.

Summary

Metric learning fits a positive semidefinite quadratic form to task constraints. Fixed-neighbor LMNN is convex in that matrix, while rank limits and factor optimization can change the problem's convexity. Gaussian random projection instead preserves fixed finite-set distances with a quantified probability, using the variance normalization $1/k$, chi-square concentration, and a union bound over pairs.

Exercises

Checkpoint

Exercise 1: For $M=\operatorname{diag}(9,0)$, give a one-row factor $L$, a distinct pair with zero learned distance, and the representation rank.

Identify the ignored coordinate direction.

Checkpoint

Exercise 2: An anchor-target difference is $(1,0)^T$ and an anchor-impostor difference is $(0,2)^T$. With one triplet and $\lambda=1$, compute the loss at $M=\operatorname{diag}(2,1)$ and at $M=\operatorname{diag}(2,0)$.

Calculate the two squared distances before applying the hinge.

Checkpoint

Exercise 3: A fixed difference has norm $3$, and the Gaussian map has $k=50$. What is the variance of one coordinate of $Rv$, its expected squared norm, and a chi-square normalization?

Keep variance and standard deviation distinct.

Checkpoint

Exercise 4: Keep $n=20$ and $\varepsilon=1/2$, but require $\delta=0.01$. What sufficient integer dimension follows from the finite-set bound?

Use the same $190$ pairs and $c_\varepsilon=1/24$.

Solutions

Solution · Exercise 1 solution

Take $L=\begin{bmatrix}3&0\end{bmatrix}$. The points $(0,0)$ and $(0,1)$ both map to zero. The rank is one, so $d_M$ is a pseudometric on the plane, with a one-dimensional representation.

Solution · Exercise 2 solution

The target squared distance is $2$ in both cases. The impostor squared distances are respectively $4$ and $0$. Thus the losses are $2+[1+2-4]_+=2$ and $2+[1+2-0]_+=5$. The second matrix collapses the impostor direction, increasing the margin penalty.

Solution · Exercise 3 solution

Each coordinate has variance $9/50$, and $\mathbb E\|Rv\|_2^2=9$. The normalized variable $50\|Rv\|_2^2/9$ has the $\chi_{50}^2$ distribution. The coordinate standard deviation is $3/\sqrt{50}$.

Solution · Exercise 4 solution

The required dimension from this bound is

$$k=\lceil24\log(38000)\rceil=254.$$

It guarantees success probability at least $0.99$. Requiring greater confidence adds a logarithmic dependence on $1/\delta$; the original dimension still does not enter this sufficient estimate.

Related notes

Fisher discriminants and class scatter uses labels to select projection directions. SVD and principal components explains spectral rank reduction, while classical and non-metric MDS builds coordinates from pairwise relations. The course reading list collects the course books.