  We address the problem of efficient sparse fixed-rank (S-FR) matrix
decomposition, i.e., splitting a corrupted matrix $M$ into an uncorrupted
matrix $L$ of rank $r$ and a sparse matrix of outliers $S$. Fixed-rank
constraints are usually imposed by the physical restrictions of the system
under study. Here we propose a method to perform accurate and very efficient
S-FR decomposition that is more suitable for large-scale problems than existing
approaches. Our method is a grateful combination of geometrical and algebraical
techniques, which avoids the bottleneck caused by the Truncated SVD (TSVD).
Instead, a polar factorization is used to exploit the manifold structure of
fixed-rank problems as the product of two Stiefel and an SPD manifold, leading
to a better convergence and stability. Then, closed-form projectors help to
speed up each iteration of the method. We introduce a novel and fast projector
for the $\text{SPD}$ manifold and a proof of its validity. Further acceleration
is achieved using a Nystrom scheme. Extensive experiments with synthetic and
real data in the context of robust photometric stereo and spectral clustering
show that our proposals outperform the state of the art.
