# Does dimensionality reduction by SVD preserves the ranking order of the dot products between data vectors?

I'm learning stanford cs224n. In its assignment 1, the notebook states:

We obtain a full matrix decomposition, with the singular values ordered in the diagonal $$S$$ matrix, and our new, shorter length-$$k$$ word vectors in $$U_k$$. This reduced-dimensionality co-occurrence representation preserves semantic relationships between words, e.g. doctor and hospital will be closer than doctor and dog.

So apparently the conclusion is not correct -- the reduced-dimensionality representation should be $$U_k S_k$$ rather than $$U_k$$ itself. But even after the correction, it's still not always correct. One may easily construct the following Python3 code to verify it:

import numpy as np
# used to extract non-duplicate elements from a symmetric matrix
from scipy.spatial.distance import squareform
# used to get the ranking order of elements
from scipy.stats import rankdata

# set parameters here
n = 10
d = 10
symmetriy = True
k = 7

# represents n d-dimensional vectors
A = np.random.randn(n, d)
if symmetry:
A = A.T @ A

U, S, _ = np.linalg.svd(A, full_matrices=False)
Uk, Sk = U[:, :k], S[:k]

# (i, j) element of these three matrices is the dot product between the
# i-th vector in A or Uk or Uk*Sk and j-th vector in A or Uk or Uk*Sk
Adot = squareform(A @ A.T, checks=False)
Udot = squareform(Uk @ Uk.T, checks=False)
USdot = squareform((Uk * Sk) @ (Uk * Sk).T, checks=False)

# the ranking order
rUdot = rankdata(Udot)
rUSdot = rankdata(USdot)

assert np.allclose(rAdot, rUdot)    # note (*)
assert np.allclose(rAdot, rUSdot)   # note (**)


where (*) is always false, and the value of (**) depends:

• When n equals d, n is small and symmetry is true, (**) is mostly true;
• Otherwise, (**) is almost always false.

Here is my attempt to dervie the general form of conclusion (i.e. when n is not equal to d): Let the data matrix be $$\mathbf A \in \mathbb R^{n \times d}$$. Let $$\mathbf A = \mathbf U\mathbf S\mathbf V^\top$$ be the SVD. Then the dot-product matrix of $$\mathbf A$$ is:

$$\mathbf A\mathbf A^\top = \sum_{i=1}^n \sigma_i^2 \boldsymbol u_i \boldsymbol u_i^\top$$

where $$\sigma_i^2$$'s are the descendingly sorted squared singular values, and $$\boldsymbol u_i$$'s are the left singular vectors. The dot-product matrix of the reduced-dimensionality data matrix $$U_k S_k$$ is:

$$(\mathbf U_k \mathbf S_k)(\mathbf U_k \mathbf S_k)^\top = \sum_{i=1}^k \sigma_i^2 \boldsymbol u_i \boldsymbol u_i^\top$$

Let $$\boldsymbol e_i$$ be the $$i$$-th column of an identity matrix of appropriate dimension. To preserve the ranking order of elements of $$\mathbf A \mathbf A^\top$$, the following statement must hold:

$$\forall p_1,q_1,p_2,q_2,\ \boldsymbol e_{p_1}^\top \mathbf A \mathbf A^\top \boldsymbol e_{q_1} \ge \boldsymbol e_{p_2}^\top \mathbf A \mathbf A^\top \boldsymbol e_{q_2} \Rightarrow \boldsymbol e_{p_1}^\top (\mathbf U_k \mathbf S_k)(\mathbf U_k \mathbf S_k)^\top \boldsymbol e_{q_1} \ge \boldsymbol e_{p_2}^\top (\mathbf U_k \mathbf S_k)(\mathbf U_k \mathbf S_k)^\top \boldsymbol e_{q_2} \tag{1}$$

But from the above experiment, it does not necessarily hold.

Hence my question relaxes to:

1. Either: given that $$\boldsymbol e_{p_1}^\top \mathbf A \mathbf A^\top \boldsymbol e_{q_1} \ge \boldsymbol e_{p_2}^\top \mathbf A \mathbf A^\top \boldsymbol e_{q_2}$$, what's the lower bound of $$\boldsymbol e_{p_1}^\top (\mathbf U_k \mathbf S_k)(\mathbf U_k \mathbf S_k)^\top \boldsymbol e_{q_1} \ge \boldsymbol e_{p_2}^\top (\mathbf U_k \mathbf S_k)(\mathbf U_k \mathbf S_k)^\top \boldsymbol e_{q_2}$$?
2. Or: what additional condition the singular values should hold in order for (1) to hold?

Any suggestions are appreciated! Thanks!