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 which have been centered. In PCA/SVD, we construct covariance matrix $F$ and Gram matrix $G$

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

2DSVD

Here we deal with a set of 2D matrices $(X_1,...,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^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. 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.