CUR matrix approximation: Difference between revisions

Revision as of 09:50, 23 November 2014

Revision as of 15:07, 13 March 2017

Line 1:

A '''CUR matrix approximation''' is a set of three [[Matrix (mathematics)|matrices]] that, when multiplied together, closely approximate a given matrix.<ref name=mahoney>{{cite web|title=CUR matrix decompositions for improved data analysis|url=http://www.pnas.org/content/106/3/697.full|accessdate=26 June 2012|author=Michael W. Mahoney|author2=Petros Drineas}}</ref> 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 sincethey 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), the CUR approximation is often easy for users to comprehend.:

* 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 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 (linear algebra)|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.