Fast Low-Rank Matrix Approximations in l1-Norm Using an Alternating Projected Gradient Method

Abstract

A low-rank matrix approximation plays an important role in the area of computer vision and image processing. Most of the conventional low-rank matrix approximation methods are based on l2-norm, and the principal component analysis (PCA) is the most popular among them. However, this can give a poor approximation for the data contaminated by outliers (including missing data) because this exaggerates the negative effect of the outliers. Recently, in order to overcome this problem, various methods based on l1-norm have been proposed. Despite the robustness of the l1-norm-based methods, these require heavy computational effort. In this paper, we propose a robust and fast low-rank factorization method based on the l1-norm, which finds proper projection and coefficient matrices using an alternating projected gradient method. This gives a good approximation as the other l1-based methods, but its execution time is much faster. The proposed method is applied to several problems to demonstrate its fast computational time in matrix approximation.