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 ′ = CU R. (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 − δ where A k is the "best" rank-k approximation provided by truncating the singular value decomposition (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 of these matrix decompositions over the last ten years. However, our two algorithms are the first polynomial time algorithms for such low-rank matrix approximations that come with relative-error guarantees; previously, in some cases, it was not even known whether such matrix decompositions exist. Both of our algorithms are simple and they take time of the order needed to approximately compute the top k singular vectors of A. The technical crux of our analysis is a novel, intuitive sampling method we introduce in this paper called "subspace sampling." In subspace sampling, the sampling probabilities depend on the Euclidean norms of the rows of the top singular vectors. This allows us to obtain provable relative-error guarantees by deconvoluting "subspace" information and "sizeof-A" information in the input matrix. This technique is likely to be useful for other matrix approximation and data analysis problems. * A preliminary version of this paper appeared in manuscript and technical report format as "Polynomial Time Algorithm for Column-Row-Based Relative-Error Low-Rank Matrix Approximation" [27, 28] . Preliminary versions of parts of this paper have also appeared as conference proceedings [29, 30, 31] .  Large m × n matrices are common in applications since the data often consist of m objects, each of which is described by n features. Examples of object-feature pairs include: documents and words contained in those documents; genomes and environmental conditions under which gene responses are measured; stocks and their associated temporal resolution; hyperspectral images and frequency resolution; and web groups and individual users. In each of these application areas, practitioners spend vast amounts of time analyzing the data in order to understand, interpret, and ultimately use this data for some application-specific task. Say that A is the m × n data matrix. In many cases, an important step in data analysis is to construct a compressed representation of A that may be easier to analyze and interpret. The most common such representation is obtained by truncating the Singular Value Decomposition (SVD) at some number k ≪ min{m, n} terms, in large part because this provides the "best" rank-k approximation to A when measured with respect to any unitarily invariant matrix norm. Unfortunately, the basis vectors (the so-called eigencolumns and eigenrows) provided by this approximation (and with respect to which every column and row of the original data matrix is expressed) are notoriously difficult to interpret in terms of the underlying data and processes generating that data. For example, the vector [(1/2) age -(1/ √ 2) height + (1/2) income], being one of the significant uncorrelated "factors" from a dataset of people's features is not particularly informative. It would be highly preferable to have a low-rank approximation that is nearly as good as that provided by the SVD but that is expressed in terms of a small number of actual columns and/or actual rows of a matrix, rather than linear combinations of those columns and rows. The main contribution of this paper is to provide such decompositions. In particular, we provide what we call a relative-error CUR matrix decomposition: given an m × n matrix A, we decompose it as a product of three matrices, C, U , and R, where C consists of a small number of actual columns of A, R consists of a small number of actual rows of A, and U is a small carefully constructed matrix that guarantees that the product CU R is "close" to A. In fact, CU R will be nearly as good as the best low-rank approximation to A that is traditionally used and that is obtained by truncating the SVD. Hence, the columns of A that are included in C, as well as the rows of A that are included in R, can be used in place of the eigencolumns and eigenrows, with the added benefit of improved interpretability in terms of the original data. Before describing applications of our main results in the next subsection, we would like to emphasize that two research communities, the Numerical Linear Algebra (NLA) community and the Theoretical Computer Science (TCS) community, have provided significant practical and theoretical motivation for studying variants of these matrix decompositions over the last ten years. In Section 3, we provide a detailed treatment of relevant prior work in both the NLA and the TCS literature. The two algorithms presented in this paper are the first polynomial time algorithms for such low-rank matrix approximations that come with relative-error guarantees; previously, in some cases, it was not even known whether such matrix decompositions exist. As an example of this preference for having the data matrix expressed in terms of a small number of actual columns and rows of the original matrix, as opposed to a small number of eigencolumns and eigenrows, consider recent data analysis work in DNA microarray and DNA Single Nucleotide Polymorphism (SNP) analysis [44, 47, 52] . DNA SNP data are often modeled as an m × n matrix A, where m is the number of individuals in the study, n is the number of SNPs being analyzed, and A ij is an encoding of the j-th SNP value for the i-th individual. Similarly, for DNA microarray
One of the most fundamental results for a CUR decomposition of a given matrix A ∈ R m×n was obtained in REF .
Relative-Error CUR Matrix Decompositions
ArXiv
ArXiv
Computer Science Mathematics