A non-monotonic method for large-scale non-negative least squares
A non-monotonic method for large-scale non-negative least squares
复制标题
DOI：
10.1080/10556788.2012.656368
复制
发表时间：
2013-10-01
影响因子：
2.2
通讯作者：
Dhillon, Inderjit S.
中科院分区：
文献类型：
--
作者：
Kim, Dongmin;Sra, Suvrit;Dhillon, Inderjit S.
提出了一种求解非负最小二乘（NNLS）问题的新算法。我们的算法推广了Barzilai和Borwein（BB）[J. Barzilai和J.M. Borwein;两点步长梯度法。IMA J.编号Anal. 1988年。]来处理非负性约束。我们的扩展不同于其他约束BB变种在简单但关键的方面，最显着的是我们的修改BB步长本身。我们的步长计算考虑到非负约束，并进一步细化步长缩放策略。这些变化，结合正交投影到非负正交，产生一个有效的NNLS算法。我们比较我们的算法与几个竞争的方法，包括建立边界约束求解器，流行的BB为基础的方法，也是一个专门的NNLS算法。在几个合成和真实世界的数据集上，我们的方法显示出极具竞争力的经验性能。
We present a new algorithm for solving the non-negative least-squares (NNLS) problem. 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. Numer. Anal. 1988.] to handle nonnegativity constraints. Our extension differs from other constrained BB variants in simple but crucial aspects, the most notable being our modification to the BB stepsize itself. Our stepsize computation takes into account the nonnegativity constraints, and is further refined by a stepsize scaling strategy. These changes, in combination with orthogonal projections onto the nonnegative orthant, yield an effective NNLS algorithm. We compare our algorithm with several competing approaches, including established bound-constrained solvers, popular BB-based methods, and also a specialised NNLS algorithm. On several synthetic and real-world datasets our method displays highly competitive empirical performance.