Relative-Error $CUR$ Matrix Decompositions
Top Cited Papers
- 1 January 2008
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 30 (2), 844-881
- https://doi.org/10.1137/07070471x
Abstract
Many data analysis applications deal with large matrices and involve approximating the matrix using a small number of “components.” Typically, these components are linear combinations of the rows and columns of the matrix, and are thus difficult to interpret in terms of the original features of the input data. In this paper, we propose and study matrix approximations that are explicitly expressed in terms of a small number of columns and/or rows of the data matrix, and thereby more amenable to interpretation in terms of the original data. Our main algorithmic results are two randomized algorithms which take as input an $m\times n$ matrix A and a rank parameter k. In our first algorithm, C is chosen, and we let $A'=CC^+A$, where $C^+$ is the Moore–Penrose generalized inverse of C. In our second algorithm C, U, R are chosen, and we let $A'=CUR$. (C and R are matrices that consist of actual columns and rows, respectively, of A, and U is a generalized inverse of their intersection.) For each algorithm, we sho...
Keywords
This publication has 24 references indexed in Scilit:
- Intra- and interpopulation genotype reconstruction from tagging SNPsGenome Research, 2006
- A haplotype map of the human genomeNature, 2005
- Algorithm 844ACM Transactions on Mathematical Software, 2005
- Fast monte-carlo algorithms for finding low-rank approximationsJournal of the ACM, 2004
- Finding Haplotype Tagging SNPs by Use of Principal Components AnalysisAmerican Journal of Human Genetics, 2004
- Approximating extent measures of pointsJournal of the ACM, 2004
- Spectral grouping using the nystrom methodIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- The maximal-volume concept in approximation by low-rank matricesPublished by American Mathematical Society (AMS) ,2001
- Incomplete Cross Approximation in the Mosaic-Skeleton MethodComputing, 2000
- Selection of relevant features and examples in machine learningArtificial Intelligence, 1997