2
$\begingroup$

Suppose an arbitrary $m \times n$ matrix $M$ and the factorizations:

Arbitrary: $M = U_a V_a^T$, where $U_a$ is $m \times k$, $V_a$ is $n \times k$ ($k < m,n$), and $rank(U_a)=rank(V_a)=k$.

SVD: $M = U_{svd} \Sigma_{svd} V_{svd}^T$

Truncated SVD (top-r singular vectors, where $r < k$): $M \approx U_{svdR} \Sigma_{svdR} V_{svdR}^T$

Given any three of rows $M^i$, $M^j$, and $M^k$, and supposing $f(M^i, M^j) - f(M^i, M^k) > 0$, where $f$ can be the dot product, cosine similarity, or Euclidean distance, what can we state about $f(U_a^i, U_a^j) - f(U_a^i, U_a^k)$?

For the SVD, we know that $M M^T = U_{svd} \Sigma_{svd} (U_{svd} \Sigma_{svd})^T$, so $f(M^i, M^j) - f(M^i, M^k) = f(U_{svd}^i \Sigma_{svd}, U_{svd}^j \Sigma_{svd}) - f(U_{svd}^i \Sigma_{svd}, U_{svd}^k \Sigma_{svd})$ when $f$ is the dot product. What if $f$ is the cosine similarity or Euclidean distance? And can we make any statements when the truncated SVD is used, lowering the rank of $M$?

The questions is motivated by trying to understand recommender systems that factorize $item \times user$ matrices and use row-wise similarity in the latent space to find similar items. The SVD provably preserves dot products, but I'm curious about the other similarities and if methods such as Alternating Least Squares (arbitrary factorization in my question) and Truncated SVD offer any such guarantees.

Experimental evidence that similarity is preserved in an arbitrary factorization: I randomly initialized $10000 \times 50$ $U_a, V_a^T$ to get $10000 \times 10000$ $M$. I then randomly sampled 100 pairs of rows and recorded $f(U_a^i, U_a^j)$ and $f(M^i, M^j)$ for each pair $(i, j)$, for $f$ as the dot product, cosine similarity, and Euclidean distance. The Spearman correlation is nearly perfect (> .99) for all $f$. The SVD factorization gives perfect correlation for all $f$.

(Note: I'm asking about rows to make the question more compact but by the transpose any statements that are true about rows will also be true about columns.)

$\endgroup$
5
  • $\begingroup$ What assumptions, if any, are you making about $U_a$ and $V_a$? Without some, it looks difficult to say anything at all about your questions. $\endgroup$ – whuber Jan 10 '20 at 14:17
  • $\begingroup$ I've added the assumption that both have the same rank. $\endgroup$ – Alexandre Jan 10 '20 at 14:24
  • $\begingroup$ I've also added the assumption that both are dense, to reflect the factorizations obtained by ALS and SGD in recommender systems. $\endgroup$ – Alexandre Jan 10 '20 at 14:30
  • $\begingroup$ That doesn't sound sufficiently restrictive: $U$ could be made arbitrarily close to $M$ or arbitrarily close to an identity matrix simply by starting with the factorizations $M=MI=IM$ and perturbing them a tiny bit. $\endgroup$ – whuber Jan 10 '20 at 14:40
  • $\begingroup$ I restricted the dimensions fof U and V that preclude them from nearing the identity matrix, and removed the dense assumption as it doesn't seem to help the analysis in any way. $\endgroup$ – Alexandre Jan 10 '20 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.