Optimization Online


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

Yangyang Xu (yangyang.xu***at***rice.edu)
Wotao Yin (wotao.yin***at***rice.edu)

Abstract: This paper considers regularized block multi-convex optimization, where the feasible set and objective function are generally non-convex but convex in each block of variables. We review some of its interesting examples and propose a generalized block coordinate descent method. (Using proximal updates, we further allow non-convexity over some blocks.) Under certain conditions, we show that any limit point satisfies the Nash equilibrium conditions. Furthermore, we establish its global convergence and estimate its asymptotic convergence rate by assuming a property based on the Kurdyka-Lojasiewicz inequality. The proposed algorithms are adapted for factorizing nonnegative matrices and tensors, as well as completing them from their incomplete observations. The algorithms were tested on synthetic data, 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 is available for download from the authors' homepages.

Keywords: block multi-convex, block coordinate descent method, Kurdyka-Lojasiewicz inequality, Nash equilibrium, nonnegative matrix and tensor factorization, matrix completion, tensor completion, proximal gradient method

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Applications -- Science and Engineering (Data-Mining )

Category 3: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: Rice CAAM Report TR12-15

Download: [PDF]

Entry Submitted: 08/10/2012
Entry Accepted: 08/10/2012
Entry Last Modified: 09/07/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society