1
$\begingroup$

I have a large word-frequency matrix (~6m unique words X ~4k documents) and I'm trying to use truncated singular value decomposition (SVD) to project it onto a matrix with fewer dimensions. I know how to get to $[U_{k}, S_{k}, V_{k}']$, but I don't know what to do then.

Each tutorial I find gives me a different answer. Here, for instance, I'm told to retain only the first $k$ rows of $S_{k}$ and $V_{k}'$ and then multiply $S_{k}V_{k}'$. In the scikit-learn implementation, however, they do it by multiplying $U_{k}S_{k}'$ (formula and code). (The book chapter they mention as source doesn't say anything about that.) In this previous answer they suggest $X'U_{k}$ instead (though they are talking about PCA, so maybe that doesn't apply here). Other answers haven't helped (here, for instance, they say we need to apply truncated SVD to the reduced matrix - which doesn't sound right, we use truncated SVD precisely to get to the reduced matrix, no?).

So, bottom line: how do I go from $[U_{k}, S_{k}, V_{k}']$ to a reduced data matrix? Which of the above formulas is the correct one (and why)?

Just to be clear: I'm not looking to reduce rank only (that I can do by multiplying $U_{k}S_{k}V_{k}'$ but it gives me the exact same dimensions I had before, which doesn't help me); I want to reduce the actual dimensions of the data matrix.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
5
$\begingroup$

Let's say you have 4x2 X matrix, run SVD and get U,S,V:

  • U is 4x4
  • S is 4x2, where only the top 2x2 is not empty
  • V is 2x2

If you want to truncate to a single largest singular value:

  • remove all columns from U leaving only the first one, now U1 is 4x1
  • remove all columns from S leaving only the first one, now S1 is 1x1
  • remove all columns from V leaving only the first one, now V1 is 2x1

You can restore the X matrix by U1*S1*V1'

The dimensionality is greatly reduced because now you can use 4x1 U matrix instead of original 4x2 X matrix.

UPDATE: you also have neat equality: X*V=U*S, so you could use both X*V1 or U1*S1 as your reduced dimension matrices, or simply U1, which is similar to the score in PCA

Improve this answer
$\endgroup$
2
  • $\begingroup$ That's it then? I simply get U1 and use it instead of X? But then why do some tutorials suggest more complicated formulas, like $S_{k}V_{k}'$, $U_{k}S_{k}'$, and $X'U_{k}$? Or are all of these valid answers but somehow different in their properties? Could you point me in the direction of a book/tutorial/paper that explains why U1 works? $\endgroup$
    – Parzival
    Feb 28, 2014 at 16:13
  • 1
    $\begingroup$ look at this PCA vs SVD tutorial, it explains how to estimate PCA through SVD. PCA may seem more intuitive for some people. It also discusses the dimensionality reduction $\endgroup$
    – Aksakal
    Feb 28, 2014 at 16:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.