63 / 2019-12-12 02:22:00

Greedy coordinate descent method on non-negative quadratic programming

greedy coordinate descent; quadratic programming; nonnegative matrix factorization

IEEE SAM 2020: Special Sessions > Structured Matrix/Tensor Decompositions: Models, Applications and Fast Algorithms

The coordinate descent (CD) method has recently become popular for solving very large-scale problems, partly due to its simple update, low memory requirement, and fast convergence. In this paper, we explore the greedy CD on solving non-negative quadratic programming (NQP). The greedy CD generally has much more expensive per-update complexity than its cyclic and randomized counterparts. However, on the NQP, these three CDs have almost the same per-update cost, while the greedy CD can have significantly faster overall convergence speed. We also apply the proposed greedy CD as a subroutine to solve linearly constrained NQP and the non-negative matrix factorization. Promising numerical results on both problems are observed on instances with synthetic data and also image data.