Alternating Direction Method of Multipliers for Nonconvex Background/Foreground Extraction

Lei Yang, Ting Kei Pong, Xiaojun Chen

Published 2015-06-23Version 1

In this paper, we propose a new optimization model for extracting background and foreground from a surveillance video. Our model can be nuclear-norm-free, and can incorporate different possibly nonconvex sparsity inducing regularization functions for extracting the foreground, such as the $\ell_p$ quasi-norm for $0<p<1$. To solve the resulting possibly nonconvex optimization problem, we adapt the alternating direction method of multipliers (ADMM) with a general dual step-size to solving a reformulation that contains three blocks of variables, and analyze its convergence. We show that for any dual step-size less than the golden ratio, there exists a (computable) threshold for the penalty parameter above which the cluster point of the sequence generated by our ADMM gives a stationary point of the nonconvex optimization problem, if the sequence is bounded. We achieve this via a potential function specifically constructed for our ADMM. Moreover, we establish the global convergence of the whole sequence generated if, in addition, this special potential function is a Kurdyka-{\L}ojasiewicz function. Furthermore, we present a simple strategy for initializing the algorithm to guarantee boundedness of the sequence generated. Finally, we perform numerical experiments comparing our model solved by our ADMM against the $\ell_1$-based model on real data. The numerical results show that our model outperforms the $\ell_1$-based model in terms of the quality of the extracted foreground.