Seminar Details
2014-08-26 (14.00) : Robust Matrix Decomposition with Fixed-Rank Constraint
At Euler building
Organized by Mathematical Engineering
Speaker :
Julio Guerrero (Universidad de Murcia, Spain)
Abstract :
There are many applications in which one can find a structured matrix (signal) severely affected by noise and outliers. Due to the presence of noise, when a signal is observed its original structure (e.g., low-rank) is lost, giving rise to a matrix without any apparent property. In many real applications, it is of great interest to be able to decompose such a corrupted matrix into the sum of the original (uncorrupted) low-rank matrix and a residual matrix containing the noise.
A traditional method to recover the low-rank structure of a matrix is Principal Component Analysis (PCA). However, PCA is known to fail in the presence of high levels of noise, leading to wrong estimations. It has been recently discovered that, in those cases where the noise/outliers can be modeled as a sparse component an exact decomposition is possible via a combination of nuclear-norm and l1-norm minimization. Robust PCA is the main representative of this trend, having being successfully applied to a wide variety of problems such as: motion estimation, background subtraction, video surveillance, face recognition, photometric stereo, Robust Manifold Learning, biomedical images, etc. Furthermore, RPCA is intimately related to other relevant problems like robust matrix completion (the Netflix Prize) and matrix sensing.
In our research, we have focused on those cases where the low-rank matrix can be characterized by a fixed rank constraint, usually imposed by the physical constraints of the system under study (e.g., motion estimation, photometric stereo, etc.). In this talk we propose a new method where Robust PCA is adapted to efficiently deal with fixed-rank constraints. Our approach, named FixedRank via Alternating Direction Method (FR-ADM) poses the optimization problem on the manifold of fixed-rank matrices , parametrized as the factor manifold of two Stiefel manifolds and a SPD manifold taken quotient by rotations. We achieved a very efficient optimization through the use of Alternating Direction minimization on the three submanifolds, using closed-form expressions for the projectors onto each submanifold. In particular, for the SPD manifold, we introduce a novel and fast projector and we prove its validity during the minimization process. The resulting method outperforms existing methods in terms of accuracy and speed. Further acceleration can be obtained by using a Nystrom based scheme to achieve linear complexity.