View source for Two-dimensional singular-value decomposition

{{short description|Method of decomposing a set of matrices via low-rank approximation}}

In [[Linear algebra|linear algebra]], '''two-dimensional singular-value decomposition''' ('''2DSVD''') computes the low-rank approximation of a set of [[Matrix (mathematics)|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 <math> X = [\mathbf x_1, \ldots, \mathbf x_n] </math> contains the set of 1D vectors which have been centered. In PCA/SVD, we construct covariance matrix <math> F </math> and Gram matrix <math> G </math>
: <math> F = X X^\mathsf{T} </math> , <math> G = X^\mathsf{T} X, </math>
and compute their eigenvectors <math> U = [\mathbf u_1, \ldots, \mathbf u_n] </math> and <math> V = [\mathbf v_1, \ldots, \mathbf v_n] </math>. Since <math> VV^\mathsf{T} = I </math> and <math> UU^\mathsf{T} = I </math> we have
: <math> X = UU^\mathsf{T} X VV^\mathsf{T} = U \left(U^\mathsf{T} XV\right) V^\mathsf{T} = U \Sigma V^\mathsf{T}. </math>
If we retain only <math> K </math> principal eigenvectors in <math> U , V</math>, this gives low-rank approximation of <math> X </math>.

==2DSVD==

Here we deal with a set of 2D matrices <math> (X_1,\ldots,X_n) </math>. Suppose they are centered <math display="inline"> \sum_i X_i =0 </math>. We construct row–row and column–column covariance matrices

: <math> F = \sum_i X_i X_i^\mathsf{T} </math> and <math> G = \sum_i X_i^\mathsf{T} X_i </math>

in exactly the same manner as in SVD, and compute their eigenvectors <math> U </math> and <math> V</math>. We approximate <math> X_i </math> as

: <math> 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} </math>

in identical fashion as in SVD. This gives a near optimal low-rank approximation of <math> (X_1,\ldots,X_n) </math> with the objective function

: <math> J=  \sum_{i=1}^n \left| X_i - L M_i R^\mathsf{T}\right| ^2 </math>

Error bounds similar to Eckard–Young theorem also exist.

2DSVD is mostly used in [[Image compression|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.&nbsp;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.&nbsp;167–191, 2005.

[[Category:Singular value decomposition]]

{{Sourceattribution|Two-dimensional singular-value decomposition}}