1 / 1

Frechet Distance Between Feature Sets

Diffusion ModelsEvaluation MetricsLinear Algebra

Medium

Fit a Gaussian to each of two feature sets and return the squared Frechet distance between the two Gaussians.

d^2 = \lVert \mu_a - \mu_b \rVert^2 + \operatorname{Tr}(\Sigma_a) + \operatorname{Tr}(\Sigma_b) - 2 \operatorname{Tr}\big( (\Sigma_a \Sigma_b)^{1/2} \big)

Each row of features_a and features_b is one feature vector of length D. The mean $\mu_a$ is the average row of features_a, and $\Sigma_a$ is its sample covariance with the unbiased divisor $N_a - 1$ , where $N_a$ is the number of rows. The same definitions give $\mu_b$ and $\Sigma_b$ from features_b. $\operatorname{Tr}$ is the matrix trace.

The product $\Sigma_a \Sigma_b$ is usually not symmetric, so compute the trace of its square root through the symmetric matrix below, which has the same eigenvalues $\lambda_i$ .

\operatorname{Tr}\big( (\Sigma_a \Sigma_b)^{1/2} \big) = \sum_i \sqrt{\lambda_i}, \qquad \lambda_i = \text{eigenvalues of } \Sigma_a^{1/2} \Sigma_b \Sigma_a^{1/2}

Here $\Sigma_a^{1/2}$ is the symmetric square root of $\Sigma_a$ . Return the value $d^2$ as a Python float (a NumPy floating scalar is also accepted). A tiny negative result from rounding, such as -1e-8 for identical sets, is accepted.

Examples

Input: features_a = [[0.0,0.0],[1.0,0.0],[0.0,1.0],[1.0,1.0]], features_b = [[1.0,1.0],[3.0,1.0],[1.0,2.0],[3.0,2.0]]

Output: 3.583333

Explanation: Set a has mean (0.5, 0.5) and covariance diag(1/3, 1/3), set b has mean (2, 1.5) and covariance diag(4/3, 1/3). The mean term is 3.25, the traces add 7/3, and the cross term subtracts 2 times 1, giving about 3.583333.

Input: features_a = [[0.5,-1.0,2.0],[1.5,0.0,1.0],[-0.5,1.0,0.0],[1.0,2.0,-1.0]], features_b = [[0.5,-1.0,2.0],[1.5,0.0,1.0],[-0.5,1.0,0.0],[1.0,2.0,-1.0]]

Output: 0.0

Input: features_a = [[1.0],[2.0],[3.0]], features_b = [[0.0],[4.0],[8.0],[12.0],[16.0]]

Output: 64.350889

Hint 1

The function np.linalg.eigh returns the eigenvalues and orthonormal eigenvectors of a symmetric matrix, which is enough to build its symmetric square root.

Hint 2

Similar matrices share eigenvalues, so a symmetric matrix built from the two covariances can stand in for the non-symmetric product.

Hint 3

Pass rowvar=False to np.cov when each row is one observation.

Hint 4

np.cov returns a 0-d array when there is one feature, so np.atleast_2d keeps a 1 by 1 matrix.

Requirements

Use NumPy and compute in float64.
Set tiny negative eigenvalues caused by rounding to 0 before taking their square roots.
Leave the input arrays unchanged.

Constraints

features_a is a float64 NumPy array of shape (N_a, D) and features_b is a float64 NumPy array of shape (N_b, D).
D is between 1 and 6, and N_a and N_b are each at least D + 1 and at most 20. N_a and N_b may differ.
All values are finite with absolute value below 1,000. A covariance may be singular, for example when a feature is constant, two features are equal, or all rows of a set are identical.

Try Similar Problems

DiT Patchify and adaLN-Zero BlockHard Toy Diffusion Training StepHard Toy DDPM SamplerHard Gaussian Mixture ScoreMedium Cosine Noise ScheduleMedium Rescale to Zero Terminal SNRMedium Time-Conditioned Residual BlockMedium Spatial Self-Attention BlockMedium Hessian Tensor of a Vector-Valued FunctionMedium PCA from ScratchMedium Convexity Certificate via the HessianMedium Low-Rank ApproximationMedium