Low-rank matrix decomposition in L1-norm by dynamic systems

摘要

Low-rank matrix approximation is used in many applications of computer vision, and is frequently implemented by singular value decomposition under L2-norm sense. To resist outliers and handle matrix with missing entries, a few methods have been proposed for low-rank matrix approximation in L1 norm. However, the methods suffer from computational efficiency or optimization capability. Thus, in this paper we propose a solution using dynamic system to perform low-rank approximation under L1-norm sense. From the state vector of the system, two low-rank matrices are distilled, and the product of the two low-rank matrices approximates to the given measurement matrix with missing entries, in L1 norm. With the evolution of the system, the approximation accuracy improves step by step. The system involves a parameter, whose influences on the computational time and the final optimized two low-rank matrices are theoretically studied and experimentally valuated. The efficiency and approximation accuracy of the proposed algorithm are demonstrated by a large number of numerical tests on synthetic data and by two real datasets. Compared with state-of-the-art algorithms, the newly proposed one is competitive.