Abstract
This paper considers regularized block multiconvex optimization, where the feasible set and objective function are generally nonconvex but convex in each block of variables. It also accepts nonconvex blocks and requires these blocks to be updated by proximal minimization. We review some interesting applications and propose a generalized block coordinate descent method. Under certain conditions, we show that any limit point satisfies the Nash equilibrium conditions. Furthermore, we establish global convergence and estimate the asymptotic convergence rate of the method by assuming a property based on the Kurdyka-Łojasiewicz inequality. The proposed algorithms are tested on nonnegative matrix and tensor factorization, as well as matrix and tensor recovery from incomplete observations. The tests include synthetic data and hyperspectral data, as well as image sets from the CBCL and ORL databases. Compared to the existing state-of-the-art algorithms, the proposed algorithms demonstrate superior performance in both speed and solution quality. The MATLAB code of nonnegative matrix/tensor decomposition and completion, along with a few demos, are accessible from the authors' homepages.
Original language | English (US) |
---|---|
Pages (from-to) | 1758-1789 |
Number of pages | 32 |
Journal | SIAM Journal on Imaging Sciences |
Volume | 6 |
Issue number | 3 |
DOIs | |
State | Published - 2013 |
Externally published | Yes |
Keywords
- Block coordinate descent
- Block multiconvex
- Kurdyka-Łojasiewicz inequality
- Matrix completion
- Nash equilibrium
- Nonnegative matrix and tensor factorization
- Proximal gradient method
- Tensor completion