SIAM Journal on Matrix Analysis and Applications · 2008 · 479 citations · 37 references
ComputingComputer ScienceAlgorithmsData StructuresScientific ComputingApproximation AlgorithmsMatrix ComputationMatrix FactorizationNumerical AlgorithmsNumerical AnalysisNumerical Linear AlgebraApproximation GuaranteesComputational Matrix TheoryDecompositionsLow-rank ApproximationRandomized Matrix AlgorithmsSparse Matrix AlgorithmsSparse Matrix Computation
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 × 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 show that with probability at least 1 − δ, ‖A − A ′ ‖F ≤ (1 + ɛ) ‖A − Ak‖F, where Ak is the “best ” rank-k approximation provided by truncating the SVD of A, and where ‖X‖F is the Frobenius norm of the matrix X. The number of columns of C and rows of R is a low-degree polynomial in k, 1/ɛ, and log(1/δ). Both the Numerical Linear Algebra community and the Theoretical Computer Science community have studied variants
37
A haplotype map of the human genome
Selection of relevant features and examples in machine learning
Avrim Blum, Pat Langley · Artificial Intelligence · 1997 · 3.3K citations
RCV1: A New Benchmark Collection for Text Categorization Research
David Lewis, Yiming Yang, Tony Rose et al. · Goldsmiths (University of London) · 2004 · 2.6K citations · Full text
Mathematics and Computers in Simulation · 1991 · 2.5K citations
Eigentaste: A Constant Time Collaborative Filtering Algorithm
Ken Goldberg, Dhruv Gupta, C. Perkins · Information Retrieval · 2001 · 1.4K citations · Full text