Two-dimensional singular-value decomposition

2DSVD computes the low-rank approximation of a set of matrices such as 2D images or weather maps in a manner almost identical to SVD (singular value decomposition) which computes the low-rank approximation of a single matrix (or a set of 1D vectors).

SVD

Let matrix $X=(x_{1},...,x_{n})$ contains the set of 1D vectors. In SVD, we construct covariance and Gram matrices

$F=XX^{T}$ , $F=X^{T}X$,

and compute their eigenvectors $U=(u_{1},...,u_{n})$ and $V=(v_{1},...,v_{n})$. Since $VV^{T}=I,UU^{T}=I$, we have

$X=UU^{T}XVV^{T}=U(U^{T}XV)V^{T}=U\Sigma V^{T}$

If we retain only $K$ principal eigenvectors in $U,V$, this gives low-rank approximation of $X$.

In 2DSVD, we deal with a set of 2D matrices $(X_{1},...,X_{n})$ . We construct row-row and column-column covariance matrices

$F=\sum _{i}X_{i}^{T}X_{i}$ , $G=\sum _{i}X_{i}X_{i}^{T}$

in exactly the same manner as in SVD, and compute their eigenvectors $U$ and $V$. We approximate $X_{i}$ as

$X_{i}=UU^{T}X_{i}VV^{T}=U(U^{T}X_{i}V)V^{T}=UM_{i}V^{T}$

in identical fasion as in SVD. This gives a near optimal low-rank approximation of $(X_{1},...,X_{n})$ with the objective function

$J=\sum _{i}|X_{i}-LM_{i}R^{T}|^{2}$

Error bounds similar to Eckard-Young Theorem also exist.

2DSVD is mostly used in image compression and representation.

References

• Chris Ding and Jieping Ye. "Two-dimensional Singular Value Decomposition (2DSVD) for 2D Maps and Images". Proc. SIAM Int'l Conf. Data Mining (SDM'05), pp:32-43, April 2005.
• Jieping Ye. "Generalized Low Rank Approximations of Matrices". Machine Learning Journal. Vol. 61, pp. 167—191, 2005.