Two-dimensional singular value decomposition

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=X\; X^T$ , $G=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\; X\; VV^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\; X\_i^T$ , $G=sum\_i\; X\_i^T\; X\_i$

in exactly the same manner as in SVD, and compute their eigenvectors $U$ and $V$.We approximate $X\_i$ as

: $X\_i\; =\; U\; U^T\; X\_i\; V\; V^T\; =\; U\; (U^T\; X\_i\; V)\; V^T\; =\; U\; M\_i\; V^T$

in identical fashion 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\; -\; L\; M\_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.