A Block Coordinate Descent Method for Regularized Multiconvex Optimization with Applications to Nonnegative Tensor Factorization and Completion

TLDR

Regularized block multiconvex optimization is studied, where the objective and feasible set are nonconvex overall but convex in each variable block. The authors propose a generalized block coordinate descent method for regularized block multiconvex optimization, reviewing its applications. The method updates nonconvex blocks via proximal minimization and is applied to nonnegative matrix/tensor factorization and completion on synthetic, hyperspectral, and image data, with MATLAB code available. The algorithm converges globally, with limit points satisfying Nash equilibrium conditions and an estimated asymptotic rate, and outperforms state‑of‑the‑art methods in speed and solution quality.

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.