Robust Low-Rank Matrix Recovery as Mixed Integer Programming via l0-Norm Optimization

This letter focuses on the robust low-rank matrix recovery (RLRMR) in the presence of gross sparse outliers. Instead of using l(1)-norm to reduce or suppress the influence of anomalies, we aim to eliminate their impact. To this end, we model the RLRMR as a mixed integer programming (MIP) problem based on the l(0)-norm. Then, a block coordinate descent (BCD) algorithm is developed to iteratively solve the resultant MIP. At each iteration, the proposed approach first utilizes the l(0)-norm optimization theory to assign binary weights to all entries of the residual between the known and estimated matrices. With these binary weights, the optimization over the bilinear term is reduced to a weighted extension of the Frobenius norm. As a result, the optimization problem is decomposed into a group of row-wise and column-wise subproblems with closed-form solutions. Additionally, the convergence of the proposed algorithm is studied. Simulation results demonstrate that the proposed method is superior to five state-of-the-art RLRMR algorithms.