Skip to main content
Expanded the answer to describe in detail how
Source Link
Brian Borchers
  • 5.3k
  • 1
  • 20
  • 27

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 (deal$\Sigma$ is a diagonal matrix with only the non-zero singular values byfirst $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 columnsdiagonal 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$ orand $V$ matrices would typically be fully dense.) There

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 that can$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.

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$.

If you have the SVD of $A$, then it's easy to compute this low rank factorization from the SVD (deal with the non-zero singular values by scaling the columns of $U$ or $V$.) There are specialized algorithms for heuristically finding low rank approximations of matrices that are faster than computing a full SVD and that can 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.

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.

Source Link
Brian Borchers
  • 5.3k
  • 1
  • 20
  • 27

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$.

If you have the SVD of $A$, then it's easy to compute this low rank factorization from the SVD (deal with the non-zero singular values by scaling the columns of $U$ or $V$.) There are specialized algorithms for heuristically finding low rank approximations of matrices that are faster than computing a full SVD and that can 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.