Robust Generalized Low Rank Approximations of Matrices
Authors:
Open Access
- 14 September 2015
- journal article
- research article
- Published by Public Library of Science (PLoS) in PLOS ONE
- Vol. 10 (9) , e0138028
Abstract
In recent years, the intrinsic low rank structure of some datasets has been extensively exploited to reduce dimensionality, remove noise and complete the missing entries. As a well-known technique for dimensionality reduction and data compression, Generalized Low Rank Approximations of Matrices (GLRAM) claims its superiority on computation time and compression ratio over the SVD. However, GLRAM is very sensitive to sparse large noise or outliers and its robust version does not have been explored or solved yet. To address this problem, this paper proposes a robust method for GLRAM, named Robust GLRAM (RGLRAM). We first formulate RGLRAM as an l1-norm optimization problem which minimizes the l1-norm of the approximation errors. Secondly, we apply the technique of Augmented Lagrange Multipliers (ALM) to solve this l1-norm minimization problem and derive a corresponding iterative scheme. Then the weak convergence of the proposed algorithm is discussed under mild conditions. Next, we investigate a special case of RGLRAM and extend RGLRAM to a general tensor case. Finally, the extensive experiments on synthetic data show that it is possible for RGLRAM to exactly recover both the low rank and the sparse components while it may be difficult for previous state-of-the-art algorithms. We also discuss three issues on RGLRAM: the sensitivity to initialization, the generalization ability and the relationship between the running time and the size/number of matrices. Moreover, the experimental results on images of faces with large corruptions illustrate that RGLRAM obtains the best denoising and compression performance than other methods.Keywords
This publication has 17 references indexed in Scilit:
- Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorizationOptimization Methods and Software, 2012
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of MultipliersFoundations and Trends in Machine Learning, 2011
- Robust principal component analysis?Journal of the ACM, 2011
- Tensor Decompositions and ApplicationsSIAM Review, 2009
- Exact Matrix Completion via Convex OptimizationFoundations of Computational Mathematics, 2009
- : Two-directional two-dimensional PCA for efficient face representation and recognitionNeurocomputing, 2005
- Generalized Low Rank Approximations of MatricesMachine Learning, 2005
- Two-dimensional pca: a new approach to appearance-based face representation and recognitionIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- The Geometry of Algorithms with Orthogonality ConstraintsSIAM Journal on Matrix Analysis and Applications, 1998
- Eigenfaces vs. Fisherfaces: recognition using class specific linear projectionIEEE Transactions on Pattern Analysis and Machine Intelligence, 1997