1
$\begingroup$

As I'm reading about different matrix decomposition methods, I see a reference to a decomposition method that is known as UV method where:

  • U: has small number of columns
  • V: has small number of rows

Surprisingly, I don't find any reference on what UV is, on algorithms to get UV, and on where to use UV. Could anyone please guide me on where I can learn more about this decomposition method?

$\endgroup$
6
$\begingroup$

If $A$ is a matrix of rank $k$ and size $m$ by $n$, $A$ can be written as

$A=UV^{T}$

where $U$ is of size $m$ by $k$ and $V$ is of size $n$ by $k$. The columns of $U$ and $V$ need not necessarily be orthogonal.

If you have the SVD of $A$, then it's easy to compute this low rank factorization from the SVD. Given the SVD

$A=U\Sigma V^{T}$

where $\Sigma$ is a diagonal matrix with only the first $k$ entries of $\Sigma$ nonzero, we can write $A$ as

$A=U_{:,1:k} \Sigma_{1:k,1:k} V_{:,1:k}^{T}$.

The scaling factors on the diagonal of $\Sigma_{1:k,1:k}$ can be incorporated into $V$ so that $A$ and can be written as $A=UV^{T}$.

However, computing the singular value decomposition of a large matrix can be extremely expensive, and the resulting $U$ and $V$ matrices would typically be fully dense.

There are specialized algorithms for heuristically finding low rank approximations of matrices that are faster than computing a full SVD. Some of these methods find sparse $U$ and $V$ matrices and
also deal with the case where $A$ is only approximately of rank $k$ (e.g. due to noise in the entries.) There is a lot of current interest in low rank matrix factorization algorithms of various sorts.

$\endgroup$

Your Answer

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

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