A Non-monotonic Method for Large-scale Nonnegative Least Squares

Dongmin Kim, Suvrit Sra, Inderjit Dhillon

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 di ers in several basic aspects from other constrained BB variants. The most notable di erence is our modi ed computation of the BB stepsize that takes into account the nonnegativ- ity constraints. We further re ne 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.

Download: pdf

Citation

  • A Non-monotonic Method for Large-scale Nonnegative Least Squares (pdf)
    D. Kim, S. Sra, I. Dhillon.
    Optimization Methods and Software, 2012.

    Bibtex: