Subspace sampling and relative-error matrix approximation: column-row-based methods

Much recent work in the theoretical computer science, linear algebra, and machine learning has considered matrix decompositions of the following form: given an m × n matrix A , decompose it as a product of three matrices, C, U , and R , where C consists of a small number of columns of A, R consists of a small number of rows of A, and U is a small carefully constructed matrix that guarantees that the product CUR is "close" to A . Applications of such decompositions include the computation of matrix "sketches", speeding up kernel-based statistical learning, preserving sparsity in low-rank matrix representation, and improved interpretability of data analysis methods. Our main result is a randomized, polynomial algorithm which, given as input an m × n matrix A , returns as output matrices C, U, R such that || A-CUR || _F ≤ (1+ε)|| A-A _k || _F with probability at least 1-δ. Here, A _k is the "best" rank- k approximation (provided by truncating the Singular Value Decomposition of A ), and || X || _F is the Frobenius norm of the matrix X. The number of columns in C and rows in R is a low-degree polynomial in k , 1/ε, and log(1/δ). Our main result is obtained by an extension of our recent relative error approximation algorithm for l ₂ regression from overconstrained problems to general l ₂ regression problems. Our algorithm is simple, and it takes time of the order of the time needed to compute the top k right singular vectors of A . In addition, it samples the columns and rows of A via the method of "subspace sampling," so-named since the sampling probabilities depend on the lengths of the rows of the top singular vectors, and since they ensure that we capture entirely a certain subspace of interest.