Two-dimensional singular-value decomposition

Let matrix $X\; =\; [\backslash mathbf\; x\_1,\; \backslash ldots,\; \backslash mathbf\; x\_n]$ contains the set of 1D vectors which have been centered. In PCA/SVD, we construct covariance matrix $F$ and Gram matrix $G$

: $F\; =\; X\; X^\backslash mathsf\{T\}$ , $G\; =\; X^\backslash mathsf\{T\}\; X,$

and compute their eigenvectors $U\; =\; [\backslash mathbf\; u\_1,\; \backslash ldots,\; \backslash mathbf\; u\_n]$ and $V\; =\; [\backslash mathbf\; v\_1,\; \backslash ldots,\; \backslash mathbf\; v\_n]$. Since $VV^\backslash mathsf\{T\}\; =\; I$ and $UU^\backslash mathsf\{T\}\; =\; I$ we have

: $X\; =\; UU^\backslash mathsf\{T\}\; X\; VV^\backslash mathsf\{T\}\; =\; U\; \backslash left(U^\backslash mathsf\{T\}\; XV\backslash right)\; V^\backslash mathsf\{T\}\; =\; U\; \backslash Sigma\; V^\backslash mathsf\{T\}.$

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

Here we deal with a set of 2D matrices $(X\_1,\backslash ldots,X\_n)$. Suppose they are centered $\backslash sum\_i\; X\_i\; =0$. We construct row–row and column–column covariance matrices

: $F\; =\; \backslash sum\_i\; X\_i\; X\_i^\backslash mathsf\{T\}$ and $G\; =\; \backslash sum\_i\; X\_i^\backslash mathsf\{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^\backslash mathsf\{T\}\; X\_i\; V\; V^\backslash mathsf\{T\}\; =\; U\; \backslash left(U^\backslash mathsf\{T\}\; X\_i\; V\backslash right)\; V^\backslash mathsf\{T\}\; =\; U\; M\_i\; V^\backslash mathsf\{T\}$

in identical fashion as in SVD. This gives a near optimal low-rank approximation of $(X\_1,\backslash ldots,X\_n)$ with the objective function

: $J=\; \backslash sum\_\{i=1\}^n\; \backslash left|\; X\_i\; -\; L\; M\_i\; R^\backslash mathsf\{T\}\backslash right|\; ^2$

Error bounds similar to Eckard–Young theorem also exist.

2DSVD is mostly used in image compression and representation.

• 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. http://ranger.uta.edu/~chqding/papers/2dsvdSDM05.pdf
• Jieping Ye. "Generalized Low Rank Approximations of Matrices". Machine Learning Journal. Vol. 61, pp. 167–191, 2005.

Category:Singular value decomposition