Efficient Low Rank Matrix Recovery With Flexible Group Sparse Regularization

Abstract

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.

References in corpus (9)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• An Alternating Direction Algorithm for Matrix Completion with Nonnegative Factors
• Multi-View Matrix Completion for Multi-Label Image Classification
• Low-rank matrix factorization with attributes
• The Dantzig selector: Recovery of Signal via ${\ell }_1-\alpha {\ell }_2$ Minimization
• Enhanced total variation minimization for stable image reconstruction
• A smoothing proximal gradient algorithm for matrix rank minimization problem
• Euclidean-Norm-Induced Schatten-p Quasi-Norm Regularization for Low-Rank Tensor Completion and Tensor Robust Principal Component Analysis
• An Inexact Augmented Lagrangian Algorithm for Training Leaky ReLU Neural Network with Group Sparsity