CUR matrix approximation

Uses your system voice; voice and rate in settings.

Snapshot

≈ 6 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.

A CUR matrix approximation is a set of three matrices C, U and R that, when multiplied together, closely approximate a given matrix. A CUR approximation can be used in the same way as the low-rank approximation of the singular value decomposition (SVD).

CUR approximations are less accurate than the SVD, but they offer two key advantages, both stemming from the fact that the rows and columns come from the original matrix (rather than left and right singular vectors): * There are methods to calculate it with lower asymptotic time complexity versus the SVD. * The matrices are more interpretable; The meanings of rows and columns in the decomposed matrix are essentially the same as their meanings in the original matrix.

Formally, a CUR matrix approximation of a matrix A is three matrices C, U, and R such that C is made from columns of A, R is made from rows of A, and that the product CUR closely approximates A. Usually the CUR is selected to be a rank-k approximation, which means that C contains k columns of A, R contains k rows of A, and U is a k-by-k matrix. There are many possible CUR matrix approximations, and many CUR matrix approximations for a given rank.

The CUR matrix approximation is often used in place of the low-rank approximation of the SVD in principal component analysis.…

A CUR matrix approximation is a set of three matrices C, U and R that, when multiplied together, closely approximate a given matrix. A CUR approximation can be used in the same way as the low-rank approximation of the singular value decomposition (SVD). CUR approximations are less accurate than the SVD, but they offer two key advantages, both stemming from the fact that the rows and columns come from the original matrix (rather than left and right singular vectors): There are methods to calculate it with lower asymptotic time complexity versus the SVD.

The matrices are more interpretable; The meanings of rows and columns in the decomposed matrix are essentially the same as their meanings in the original matrix. Formally, a CUR matrix approximation of a matrix A is three matrices C, U, and R such that C is made from columns of A, R is made from rows of A, and that the product CUR closely approximates A. Usually the CUR is selected to be a rank-k approximation, which means that C contains k columns of A, R contains k rows of A, and U is a k-by-k matrix.

There are many possible CUR matrix approximations, and many CUR matrix approximations for a given rank. The CUR matrix approximation is often used in place of the low-rank approximation of the SVD in principal component analysis. The CUR is less accurate, but the columns of the matrix C are taken from A and the rows of R are taken from A. In principal component analysis, each column of A contains a data sample; thus, the matrix C is made of a subset of data samples.

This is much easier to interpret than the SVD's left singular vectors, which represent the data in a rotated space. Similarly, the matrix R is made of a subset of variables measured for each data sample. This is easier to comprehend than the SVD's right singular vectors, which are another rotations of the data in space.

Matrix CUR

Keaton Hamm and Akram Aldroubi et al. describe the following theorem, which outlines a CUR decomposition of a matrix L with rank r : Theorem: Consider row and column indices I, J \subseteq [n] with |I|, |J| \ge r . Denote submatrices C = L_{:,J}, U = L_{I,J} and R = L_{I,:} . If rank( U ) = rank( L ), then L = CU^+R , where (\cdot)^+ denotes the Moore–Penrose pseudoinverse. In other words, if L has low rank, we can take a sub-matrix U = L_{I,J} of the same rank, together with some rows R and columns C of L and use them to reconstruct L .

Tensor CURT

Tensor-CURT decomposition is a generalization of matrix-CUR decomposition. Formally, a CURT tensor approximation of a tensor A is three matrices and a (core-)tensor C, R, T and U such that C is made from columns of A, R is made from rows of A, T is made from tubes of A and that the product U(C,R,T) (where the i,j,l -th entry of it is \sum_{i',j',l'}U_{i',j',l'}C_{i,i'}R_{j,j'}T_{l,l'} ) closely approximates A. Usually the CURT is selected to be a rank-k approximation, which means that C contains k columns of A, R contains k rows of A, T contains tubes of A and U is a k-by-k-by-k (core-)tensor.

Algorithms

The CUR matrix approximation is not unique and there are multiple algorithms for computing one. One is ALGORITHMCUR. The "Linear Time CUR" algorithm simply picks J by sampling columns randomly (with replacement) with probability proportional to the squared column norms, \|L_{:,j}\|_2^2 ; and similarly sampling I proportional to the squared row norms, \|L_{i}\|_2^2 . The authors show that taking |J| \approx k /\varepsilon^4 and |I| \approx k / \varepsilon^2 where 0 \le \varepsilon , the algorithm achieves Frobenius error bound \|A - CUR\|_F \le \|A - A_k\|_F + \varepsilon \|A\|_F , where A_k is the optimal rank k approximation.

See also

Dimensionality reduction

References

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

Provenance

snapshot enwiki-001369899599 · captured 1786996661.0 · version history

Cite this page as: encyclopegia.org, “CUR matrix approximation”, snapshot enwiki-001369899599. https://encyclopegia.org/a/cur-matrix-approximation

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.