  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.
