Divide-and-Conquer Method for L1 Norm Matrix Factorization in the Presence of Outliers and Missing Data

Details Divide-and-Conquer Method for L1 Norm Matrix Factorization in the Presence of Outliers and Missing Data Divide-and-Conquer Method for L1 Norm Matrix Factorization in the Presence of Outliers and Missing Data

2012-02-27

arxiv.org/abs/1202.5844v3

Computer Science

Numerical Analysis

19 pages, 2 figures, 2 tables

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Divide-and-Conquer Method for L1 Norm Matrix Factorization in the Presence of Outliers and Missing Data does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Divide-and-Conquer Method for L1 Norm Matrix Factorization in the Presence of Outliers and Missing Data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Divide-and-Conquer Method for L1 Norm Matrix Factorization in the Presence of Outliers and Missing Data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-262592