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 x 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 in-terpretability of data analysis methods. Our main result is a randomized, polynomial algorithm which, given as input an m x n matrix A, returns as output matrices C, U, R such thatrn‖A-CUR‖_F≤(1 + ε)‖A-A_k‖_Frnwith 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_2 regression from overcon-strained problems to general l_2 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.