We present a new algorithm for nonnegative least-squares (NNLS). Our algorithm extends the unconstrained quadratic optimization algorithm of Barzilai and Borwein (BB) (J. Barzilai and J. M. Borwein; Two-Point Step Size Gradient Methods. IMA J. Numerical Analysis; 1988.) to handle nonnegativity constraints. Our extension diff ers in several basic aspects from other constrained BB variants. The most notable diff erence is our modifi ed computation of the BB stepsize that takes into account the nonnegativity constraints. We further refi ne the stepsize computation by introducing a stepsize scaling strategy that, in combination with orthogonal projections onto the nonnegative quadrant, yields an efficient NNLS algorithm. We compare our algorithm with both established convex solvers and a specialized NNLS method: on several synthetic and real-world datasets we observe highly competitive empirical performance.
Citation
Dept. of Computer Science, University of Texas at Austin, May 2010