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

Question

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
rAdot = rankdata(Adot)
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!

Answer 1

I starts to feel that in "This reduced-dimensionality co-occurrence representation preserves semantic relationships between words", it probably does not mean to preserve all inner product, but to preserve inner products as much as possible. This is, indeed, the job of SVD.

To conclude this question, I wrote a post on how SVD performs dimensionality reduction.