Journal
LINEAR ALGEBRA AND ITS APPLICATIONS
Volume 431, Issue 5-7, Pages 760-771Publisher
ELSEVIER SCIENCE INC
DOI: 10.1016/j.laa.2009.03.026
Keywords
Nonnegative least-squares; Sampling; Hadamard transform; Randomized algorithm; Random projections
Categories
Funding
- Institute of Pure and Applied Mathematics of the University of California at Los Angeles
Ask authors/readers for more resources
Constrained least-squares regression problems, such as the Non-negative 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 Phi is an element of R-nxd (n >> d) and a vector y is an element of R-d, we prove that the Euclidean length of Phi y can be estimated very accurately by the Euclidean length of (Phi) over tildey, where (Phi) over tilde consists of a small subset of (appropriately rescaled) rows of Phi. (c) 2009 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available