Empirical Inference Poster 2010

Solving large-scale nonnegative least squares using an adaptive non-monotonic method

We present an efficient algorithm for large-scale non-negative least-squares (NNLS). We solve NNLS by extending the unconstrained quadratic optimization method of Barzilai and Borwein (BB) to handle nonnegativity constraints. Our approach is simple yet efficient. It differs from other constrained BB variants as: (i) it uses a specific subset of variables for computing BB steps; and (ii) it scales these steps adaptively to ensure convergence. We compare our method with both established convex solvers and specialized NNLS methods, and observe highly competitive empirical performance.

Author(s): Sra, S. and Kim, D. and Dhillon, I.
Journal: 24th European Conference on Operational Research (EURO 2010)
Volume: 24
Pages: 223
Year: 2010
Month: April
Day: 0
Bibtex Type: Poster (poster)
Digital: 0
Electronic Archiving: grant_archive
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik
Links:

BibTex

@poster{6521,
  title = {Solving large-scale nonnegative least squares using an adaptive non-monotonic method},
  journal = {24th European Conference on Operational Research (EURO 2010)},
  abstract = {We present an efficient algorithm for large-scale non-negative least-squares
  (NNLS). We solve NNLS by extending the unconstrained quadratic optimization
  method of Barzilai and Borwein (BB) to handle nonnegativity constraints.
  Our approach is simple yet efficient. It differs from other constrained BB variants
  as: (i) it uses a specific subset of variables for computing BB steps; and
  (ii) it scales these steps adaptively to ensure convergence. We compare our
  method with both established convex solvers and specialized NNLS methods,
  and observe highly competitive empirical performance.},
  volume = {24},
  pages = {223},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  month = apr,
  year = {2010},
  slug = {6521},
  author = {Sra, S. and Kim, D. and Dhillon, I.},
  month_numeric = {4}
}