Back
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.
@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} }