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

This article is issued from Wikipedia - version of the Thursday, August 16, 2012. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.