Sampling algorithms for ℓ ₂ regression and applications

We present and analyze a sampling algorithm for the basic linear-algebraic problem of ℓ ₂ regression. The ℓ ₂ regression (or least-squares fit) problem takes as input a matrix A ∈ ℝ ^n×d (where we assume n ≫ d) and a target vector b ∈ ℝ ⁿ, and it returns as output cross Z sign = min _x∈ℝd |b - Ax| ₂. Also of interest is x _opt = A ⁺b, where A ⁺ is the Moore-Penrose generalized inverse, which is the minimum-length vector achieving the minimum. Our algorithm randomly samples r rows from the matrix A and vector b to construct an induced ℓ ₂ regression problem with many fewer rows, but with the same number of columns. A crucial feature of the algorithm is the nonuniform sampling probabilities. These probabilities depend in a sophisticated manner on the lengths, i.e., the Euclidean norms, of the rows of the left singular vectors of A and the manner in which b lies in the complement of the column space of A. Under appropriate assumptions, we show relative error approximations for both cross Z sign and x _opt. Applications of this sampling methodology are briefly discussed.