Abstract: We present a new algorithm for nonnegative least-squares (NNLS). Our algorithm extends the uncon- strained 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 diers in several basic aspects from other constrained BB variants. The most notable dierence is our modied computation of the BB stepsize that takes into account the nonnegativ- ity constraints. We further rene the stepsize computation by introducing a stepsize scaling strategy that, in combination with orthogonal projections onto the nonnegative quadrant, yields an ecient NNLS algo- rithm. 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.
- A Non-monotonic Method for Large-scale Nonnegative Least Squares (pdf, software)
D. Kim, S. Sra, I. Dhillon.
Optimization Methods and Software, 2012.