Recovering low-rank and sparse matrix based on the truncated nuclear norm

Abstract

Recovering the low-rank, sparse components of a given matrix is a challenging problem that arises in many real applications. Existing traditional approaches aimed at solving this problem are usually recast as a general approximation problem of a low-rank matrix. These approaches are based on the nuclear norm of the matrix, and thus in practice the rank may not be well approximated. This paper presents a new approach to solve this problem that is based on a new norm of a matrix, called the truncated nuclear norm (TNN). An efficient iterative scheme developed under the linearized alternating direction method multiple framework is proposed, where two novel iterative algorithms are designed to recover the sparse and low-rank components of matrix. More importantly, the convergence of the linearized alternating direction method multiple on our matrix recovering model is discussed and proved mathematically. To validate the effectiveness of the proposed methods, a series of comparative trials are performed on a variety of synthetic data sets. More specifically, the new methods are used to deal with problems associated with background subtraction (foreground object detection), and removing shadows and peculiarities from images of faces. Our experimental results illustrate that our new frameworks are more effective and accurate when compared with other methods.

Keywords: Low-rank and sparse decomposition; Recovery of matrix; Removing shadows of image; Surveillance video; Truncated nuclear norm.