Empirical Inference

Solving large-scale nonnegative least-squares

2010

Poster

ei


We study the fundamental problem of nonnegative least squares. This problem was apparently introduced by Lawson and Hanson [1] under the name NNLS. As is evident from its name, NNLS seeks least-squares solutions that are also nonnegative. Owing to its wide-applicability numerous algorithms have been derived for NNLS, beginning from the active-set approach of Lawson and Hanson [1] leading up to the sophisticated interior-point method of Bellavia et al. [2]. We present a new algorithm for NNLS that combines projected subgradients with the non-monotonic gradient descent idea of Barzilai and Borwein [3]. Our resulting algorithm is called BBSG, and we guarantee its convergence by exploiting properties of NNLS in conjunction with projected subgradients. BBSG is surprisingly simple and scales well to large problems. We substantiate our claims by empirically evaluating BBSG and comparing it with established convex solvers and specialized NNLS algorithms. The numerical results suggest that BBSG is a practical method for solving large-scale NNLS problems.

Author(s): Sra, S.
Journal: 16th Conference of the International Linear Algebra Society (ILAS 2010)
Volume: 16
Pages: 19
Year: 2010
Month: June
Day: 0

Department(s): Empirical Inference
Bibtex Type: Poster (poster)

Digital: 0
Language: en
Note: based on Joint work with Dongmin Kim and Inderjit Dhillon
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF
Web

BibTex

@poster{6256,
  title = {Solving large-scale nonnegative least-squares},
  author = {Sra, S.},
  journal = {16th Conference of the International Linear Algebra Society (ILAS 2010)},
  volume = {16},
  pages = {19},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  month = jun,
  year = {2010},
  note = {based on Joint work with Dongmin Kim and Inderjit Dhillon},
  doi = {},
  month_numeric = {6}
}