Greedy coordinate descent method on non-negative quadratic programming
ID:163
Submission ID:63 View Protection:ATTENDEE
Updated Time:2020-08-05 10:17:28 Hits:430
Oral Presentation
Abstract
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.
Keywords
greedy coordinate descent; quadratic programming; nonnegative matrix factorization
Submission Author
Chenyu Wu
Rensselaer Polytechnic Institute, USA
Yangyang Xu
Rensselaer Polytechnic Institute, USA
Comment submit