Optimization Online


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

Dongmin Kim (dmkim***at***cs.utexas.edu)
Suvrit Sra (suvrit.sra***at***tuebingen.mpg.de)
Inderjit S. Dhillon (inderjit***at***cs.utexas.edu)

Abstract: 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.

Keywords: Least squares, nonnegativity constraints, large-scale, non-monotonic descent, Barzilai-Borwein stepsize, gradient projection method, NNLS

Category 1: Nonlinear Optimization (Nonlinear Systems and Least-Squares )

Category 2: Applications -- Science and Engineering (Basic Sciences Applications )

Category 3: Nonlinear Optimization (Bound-constrained Optimization )

Citation: Dept. of Computer Science, University of Texas at Austin, May 2010

Download: [PDF]

Entry Submitted: 05/26/2010
Entry Accepted: 05/26/2010
Entry Last Modified: 05/26/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society