Block-coordinate update
Introduction
Our paper
Matlab codes

The block-coordinate update method

Background

The block-coordinate update (BCU) method is a generalization to the following methods:

  • alternating minimization,

  • alternating projection,

  • (block) coordinate minimization,

  • (block) coordinate descent.

The method solves the problem in the form of

mathop{mathrm{minimize}}_{mathbf{x}_1,ldots,mathbf{x}_s} F(mathbf{x}_1,ldots,mathbf{x}_s)~mbox{subject to}~(mathbf{x}_1,ldots,mathbf{x}_s)inmathcal{X}

by updating one or several blocks of variables at a time rather than all the blocks together (the batch update). The order of update can be deterministic or stochastic. The deterministic orders can be eithr cyclic or greedy according to a certain rank.

The main advantage is that updating one or just several blocks of variables are computationally much cheaper than the batch update. On the other hand, convergence requires more stringent conditions and typically takes more iterations.

The update applied to each block can be exact minimization over the block or take different forms of inexact updates such as

  • one or a few gradient descent steps,

  • one or a few projected gradient descent steps,

  • one or a few (preconditioned) CG steps,

  • prox-linear update,

  • more…

The choice of update should give a good tradeoff between the per-update complexity and the progress of overall minimization.

Our paper on BCU