A Linearized Alternating Direction Method of Multipliers for a Special Three-Block Nonconvex Optimization Problem of Background/Foreground Extraction

Abstract

In this paper, we focus on the three-block nonconvex optimization problem of background/foreground extraction from a blurred and noisy surveillance video. The coefficient matrices of the equality constraints are nonidentity matrices. Regarding the separable structure of the objective function and linear constraints, a benchmark solver for the problem is the alternating direction method of multipliers (ADMM). The computational challenge is that there is no closed-form solution to the subproblem of ADMM since the objective function is not differentiable and the coefficient matrices of the equality constraints are not identity matrices. In this paper, we propose a linearized ADMM by choosing the proximal terms appropriately and add the dual step size to make the proposed algorithm more flexible. Under proper assumptions and the associated function satisfying the Kurdyka-Łojasiewicz property, we show that the proposed algorithm converges to a critical point of the given problem. We apply the proposed algorithm to the background/foreground extraction and the numerical results are used to demonstrate the effectiveness of the proposed algorithm.

Keywords

• Alternating direction method of multipliers
• global convergence
• image processing
• Kurdyka-Łojasiewicz property
• linear constraint
• nonconvex optimization