Measuring distance preservation in dimensionality reduction

Question

I am looking to compare the distance preserved during dimension reductions for several techniques. I have read some papers on similar topics here and here.

For example, I would like to use the Euclidean Distance to measure the distance preserved during PCA's dimension reduction. However, my point of confusion what are $X$ and $Y$ in $$d(X, Y) = \sqrt{\sum^n_{i=1}\left(x_i - y_i\right)^2}$$ I understand how to calculate $d\left(X, Y\right)$ given two vectors/matrices, but I don't understand with context to PCA. Let me try to explain.

Let $W_{d \times k}$ be the matrix of $k$ leading eigenvectors, $X_{d\times n}$ be the original data, and $Z_{k\times n}$ be the projection of $X$ onto the reduced subspace.

$Z = W^{T}X$

Back to calculating $d\left(X, Y\right)$. My guess is that the PCA's $X$ correspond to $X$ and $Y$ can correspond to $Z$. But how does this work since $X$ and $Y$ have different dimensions? I have to be oblivious to something here.

Also, I am not concerned if a Euclidean Distance measure is not a good choice for measuring PCA's distance preservation (unless they are incompatible). This is simply exploration.

Edit: For example, if I have $$X_{d\times n} = \begin{bmatrix} x_{11} & \dots & x_{1n} \\ x_{21} & \dots & x_{2n} \\ x_{31} & \dots & x_{3n} \\ \end{bmatrix} $$ and say I choose to retain $k = 2$ principal components which are then projected onto $$Z_{k \times n} = \begin{bmatrix} z_{11} & \dots & z_{1n} \\ z_{21} & \dots & z_{2n} \\ \end{bmatrix} $$

Answer 1

The confusion

The point of confusion is probably the use of variable $n$ to denote the dimension in Euclidean distance, which is later re-used for the number of points. Euclidean distance is better to be written as $$d_X(\boldsymbol{x}_1, \boldsymbol{x}_2)=\sqrt{\sum_{i=1}^{\color{red}{d}}(x_1^i - x_2^i)^2}$$ in the original space, and $$d_Z(\boldsymbol{z}_1, \boldsymbol{z}_2)=\sqrt{\sum_{i=1}^{\color{red}{k}}(z_1^i - z_2^i)^2}$$ in the reduced space. Where $\boldsymbol{z}_a=(z_a^1,\cdots,z_a^k)$ is the transformation of point $\boldsymbol{x}_a=(x_a^1,\cdots,x_a^d)$ by $W$. EDIT: in your notation, $Z[:, a]$ is the transformation of $X[:, a]$.

Distance preservation measure

A measure of distance preservation for transformation $W$ should be defined in such a way that compares the distance of two points in the original space with the distance of the same two points in the reduced space.

Accordingly, a measure that compares all $\binom{n}{2}$ pairwise distances could be defined as: $$DP(W) = \frac{2}{n(n-1)}\sum_{a=1}^{n} \sum_{b=a+1}^{n} |d_X(\boldsymbol{x}_a, \boldsymbol{x}_b) - d_Z(\boldsymbol{z}_a, \boldsymbol{z}_b)|$$

where for a constant $k$, smaller $DP(W)$ implies better distance preservation by $W$.

Note that various measures of distance preservation can be defined based on this foundation. For example,

1. Restricting the comparison to only $K$ nearest neighbors of a point in the original space, leading to $nK$ comparisons instead of $\binom{n}{2}$, or
2. Using the Pearson correlation of distances rather than their difference, since we generally want close (distant) points in the original space to be also close (distant) in the reduced space, or
3. Measuring the distance to point's tangent space instead of the point itself, etc.

Answer 2

I think there is an easier way to compare distance preservations:

1) In case your original dataframe is big, sample let's say random N=10,000 points from there.

2) Fit all your dimensionality reduction algorithms and transform this newly sampled dataframe.

3) Obtain euclidean distances between points in originally sampled dataframe, then other newly produced transformed dataframes in step 2. For example:

dist_orig = np.square(euclidean_distances(X_sampled, X_sampled)).flatten()
dist_pca = np.square(euclidean_distances(pca, pca)).flatten()
dist_tsne = np.square(euclidean_distances(tsne, tsne)).flatten()
dist_umap = np.square(euclidean_distances(umap, umap)).flatten()

4) Run spearman or other correlation metric by comparing original sampled euclidean space vs each of the reduced spaces. For instance:

coef_pca, p_pca = spearmanr(dist_orig, dist_pca)
coef_tsne, p_tsne = spearmanr(dist_orig, dist_tsne)
coef_umap, p_umap = spearmanr(dist_orig, dist_umap)

5) See which method has the highest correlation coefficient and, hence, preserves the best distances between points in original space.