  In this paper, we present a novel approach to the low rank matrix recovery
(LRMR) problem by casting it as a group sparsity problem. Specifically, we
propose a flexible group sparse regularizer (FLGSR) that can group any number
of matrix columns as a unit, whereas existing methods group each column as a
unit. We prove the equivalence between the matrix rank and the FLGSR under some
mild conditions, and show that the LRMR problem with either of them has the
same global minimizers. We also establish the equivalence between the relaxed
and the penalty formulations of the LRMR problem with FLGSR. We then propose an
inexact restarted augmented Lagrangian method, which solves each subproblem by
an extrapolated linearized alternating minimization method. We analyze the
convergence of our method. Remarkably, our method linearizes each group of the
variable separately and uses the information of the previous groups to solve
the current group within the same iteration step. This strategy enables our
algorithm to achieve fast convergence and high performance, which are further
improved by the restart technique. Finally, we conduct numerical experiments on
both grayscale images and high altitude aerial images to confirm the
superiority of the proposed FLGSR and algorithm.
