Divide-and-Conquer Method for L1 Norm Matrix Factorization in the Presence of Outliers and Missing Data
This work addresses the challenge of efficient and accurate L1 norm matrix factorization for robust data analysis in fields like computer vision, though it appears incremental as it builds on existing L1 norm minimization approaches.
The authors tackled the problem of robust low-rank matrix factorization with outliers and missing data by proposing a divide-and-conquer method that breaks the problem into convex sub-problems with closed-form solutions, resulting in an algorithm with approximately linear computational complexity that outperforms state-of-the-art methods in both time and accuracy on large-scale applications like face recognition and structure from motion.
The low-rank matrix factorization as a L1 norm minimization problem has recently attracted much attention due to its intrinsic robustness to the presence of outliers and missing data. In this paper, we propose a new method, called the divide-and-conquer method, for solving this problem. The main idea is to break the original problem into a series of smallest possible sub-problems, each involving only unique scalar parameter. Each of these subproblems is proved to be convex and has closed-form solution. By recursively optimizing these small problems in an analytical way, efficient algorithm, entirely avoiding the time-consuming numerical optimization as an inner loop, for solving the original problem can naturally be constructed. The computational complexity of the proposed algorithm is approximately linear in both data size and dimensionality, making it possible to handle large-scale L1 norm matrix factorization problems. The algorithm is also theoretically proved to be convergent. Based on a series of experiment results, it is substantiated that our method always achieves better results than the current state-of-the-art methods on $L1$ matrix factorization calculation in both computational time and accuracy, especially on large-scale applications such as face recognition and structure from motion.