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…

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 = [\mathbf x_1, \ldots, \mathbf 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^\mathsf{T} , G = X^\mathsf{T} X, and compute their eigenvectors U = [\mathbf u_1, \ldots, \mathbf u_n] and V = [\mathbf v_1, \ldots, \mathbf v_n] . Since VV^\mathsf{T} = I and UU^\mathsf{T} = I we have X = UU^\mathsf{T} X VV^\mathsf{T} = U \left(U^\mathsf{T} XV\right) V^\mathsf{T} = U \Sigma V^\mathsf{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,\ldots,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^\mathsf{T} and G = \sum_i X_i^\mathsf{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^\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 (X_1,\ldots,X_n) with the objective function J= \sum_{i=1}^n \left| X_i - L M_i R^\mathsf{T}\right| ^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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1177659152 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001177659152 · captured 1695921015.0 · version history

Cite this page as: encyclopegia.org, “Two-dimensional singular-value decomposition”, snapshot enwiki-001177659152. https://encyclopegia.org/a/two-dimensional-singular-value-decomposition

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.