Two-dimensional singular-value decomposition

In linear algebra, 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=[{𝐱}_1,\dots ,{𝐱}_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}^{𝖳}$ , $G=X^{𝖳}X,$

and compute their eigenvectors $U=[{𝐮}_1,\dots ,{𝐮}_n]$ and $V=[{𝐯}_1,\dots ,{𝐯}_n]$. Since $V{V}^{𝖳}=I$ and $U{U}^{𝖳}=I$ we have

$X=U{U}^{𝖳}XV{V}^{𝖳}=U\left(U^{𝖳}XV\right)V^{𝖳}=U\mathrm{\Sigma }{V}^{𝖳}.$

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

2DSVD

Here we deal with a set of 2D matrices $(X_1,\dots ,X_n)$. Suppose they are centered $\sum _i{X}_i=0$. We construct row–row and column–column covariance matrices

$F=\sum _i{X}_i{X}_i^{𝖳}$ and $G=\sum _i{X}_i^{𝖳}{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}^{𝖳}{X}_{i}V{V}^{𝖳}=U\left(U^{𝖳}{X}_{i}V\right)V^{𝖳}=U{M}_i{V}^{𝖳}$

in identical fashion as in SVD. This gives a near optimal low-rank approximation of $(X_1,\dots ,X_n)$ with the objective function

$J=\sum _{i=1}^n{|X_i-L{M}_i{R}^{𝖳}|}^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. 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.