# What is UV decomposition?

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?

• Maybe QR decomposition? (en.wikipedia.org/wiki/Matrix_decomposition) Jan 7 '16 at 17:56
• I haven't heard about UV-decomposition, while low-rank (approximated) decompositions are frequently written as $A = U \Sigma V$ or $A = U V$ with U and V satisfying the properties you named Jan 7 '16 at 18:23
• Look at section 9.4.1 of infolab.stanford.edu/~ullman/mmds/ch9.pdf . Then glance through infolab.stanford.edu/~ullman/mmds/ch11.pdf . Also stats.stackexchange.com/questions/149262/… . Jan 7 '16 at 18:25
• +1 @MarkL.Stone. This is a relatively rare decomposition used in recommender systems. I would strongly suggest using some "cheap" SVD alternative. Jan 7 '16 at 18:42
• @Cliff AB I'm not recommending any of this recommender cr@p; merely providing links relevant to the posted question :) Jan 7 '16 at 19:19

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.