2008/12/24 by Christos Boutsidis, Boutsidis, Christos, Petros Drineas +1 · 1 citation
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Face and Expression Recognition #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.DS
paper · pdf · doi:10.48550/arxiv.0812.4547
to appear in Linear Algebra and its Applications
openalex publication_date 2008/12/24 · arxiv created 2009/03/13 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Constrained least-squares regression problems, such as the Nonnegative Least Squares (NNLS) problem, where the variables are restricted to take only nonnegative values, often arise in applications. Motivated by the recent development of the fast Johnson-Lindestrauss transform, we present a fast random projection type approximation algorithm for the NNLS problem. Our algorithm employs a randomized Hadamard transform to construct a much smaller NNLS problem and solves this smaller problem using a standard NNLS solver. We prove that our approach finds a nonnegative solution vector that, with high probability, is close to the optimum nonnegative solution in a relative error approximation sense. We experimentally evaluate our approach on a large collection of term-document data and verify that it does offer considerable speedups without a significant loss in accuracy. Our analysis is based on a novel random projection type result that might be of independent interest. In particular, given a tall and thin matrix Φ∈ ℝn × d (n ≫ d) and a vector y ∈ ℝd, we prove that the Euclidean length of Φy can be estimated very accurately by the Euclidean length of Φy, where Φ consists of a small subset of (appropriately rescaled) rows of Φ.