Block-coordinate update
Introduction
Our paper
Matlab codes

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

Rice University CAAM Technical Report TR12-15

Method

It is difficult to establish the global convergence of BCU for optimization problems that are nonconvex and/or nonsmooth. This paper considers block multi-convex optimization, where the feasible set and objective function are convex in each block of variables (but not jointly convex in general). It describes several interesting applications and proposes a BCU algorithm with three different block-update schemes.

Under certain conditions, it shows that any limit point satisfies the Nash equilibrium conditions. Furthermore, global convergence and asymptotic convergence rate are established for problems obeying the Kurdyka-Lojasiewicz inequality.

Applications

  • Nonnegative matrix/tensor factorization

  • Nonnegative matrix/tensor completion (reconstruction from incomplete observations)

  • Hyperspectral data analysis

  • Sparse dictioanry learning

  • Blind source separation

  • Any multi-convex problems, where the feasible set and objective function are generally non-convex but convex in each block of variables.

Tested problem sets

  • Synthetic nonnegative matrices (factorization / completion)

  • Synthetic nonnegative tensor (factorization / completion)

  • CBCL and ORL image databases

  • Hyperspectral data

Citation

Y. Xu and W. Yin, A Block Coordinate Descent Method for Multi-Convex Optimization with Applications to Nonnegative Tensor Factorization and Completion, Rice CAAM technical report 12-15, 2012.