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

Let matrix ${\displaystyle X=[{\mathbf{𝐱}}_1,\dots ,{\mathbf{𝐱}}_n]}$ contains the set of 1D vectors which have been centered. In PCA/SVD, we construct covariance matrix ${\displaystyle F}$ and Gram matrix ${\displaystyle G}$

${\displaystyle F=X{X}^{\mathsf{T}}}$ , ${\displaystyle G=X^{\mathsf{T}}X,}$

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

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

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

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

${\displaystyle F=\sum _i{X}_i{X}_i^{\mathsf{T}}}$ and ${\displaystyle G=\sum _i{X}_i^{\mathsf{T}}{X}_i}$

in exactly the same manner as in SVD, and compute their eigenvectors ${\displaystyle U}$ and ${\displaystyle V}$. We approximate ${\displaystyle X_i}$ as

${\displaystyle X_i=U{U}^{\mathsf{T}}{X}_{i}V{V}^{\mathsf{T}}=U\left(U^{\mathsf{T}}{X}_{i}V\right)V^{\mathsf{T}}=U{M}_i{V}^{\mathsf{T}}}$

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

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

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Two-dimensional singular-value decomposition. Read more