A Fast Scale-Invariant Algorithm for Non-negative Least Squares with Non-negative Data

Within machine learning, NNLS problems arise whenever having negative labels is not meaningful, for example, when labels represent quantities like prices, age, pixel intensities, chemical concentrations, or frequency counts. NNLS is also widely used as a subroutine in nonnegative matrix factorization to extract sparse features in applications like image processing, computational biology, clustering, collaborative filtering, and community detection [Gil14]. From a statistical perspective, NNLS problems can be shown to possess a regularization property that enforces sparsity similar to LASSO [Tib96], while being comparatively simpler, without the need to tune a regularization parameter or perform cross-validation [SH14, BEZ08, FK14]. From an algorithmic standpoint, the nonnegativity constraint in NNLS problems is typically viewed as an obstacle: most NNLS algorithms need to perform additional work to handle it, and the problem is considered harder than unconstrained least squares. However, in many applications that use NNLS, the data is also nonnegative. This is true, for example, in problems arising in image processing, computational genomics, functional MRI, and in applications traditionally addressed using nonnegative matrix factorization. We argue in this paper that when the data for NNLS is nonnegative, it is in fact possible to obtain stronger guarantees than for traditional least squares problems.