Inexact block coordinate descent methods with application to non-negative matrix factorization

摘要

This paper is concerned with the cyclic block coordinate descent method, also known as the nonlinear Gauss-Seidel (GS) method, where the solution of an optimization problem is achieved by partitioning the variables in blocks and successively minimizing with respect to each block. The properties of the objective function that guarantee the convergence of such alternating scheme have been widely investigated in the literature and it is well known that without suitable convexity hypotheses, the method may fail to locate the stationary points when more than two blocks of variables are employed. In this paper the general constrained nonconvex case is considered, presenting three contributions. First, a general method allowing an approximate solution of each block minimization subproblem is devised and the related convergence analysis is developed, showing that the proposed inexact method has the same convergence properties as the standard nonlinear GS method. Then a cyclic block gradient projection method is analysed, proving that it leads to stationary points for every number of blocks. Finally, the cyclic block gradient method is applied to large-scale problems arising from the non-negative matrix factorization approach. The results of a numerical experimentation on image recognition problems are also reported.