A perturbation inequality for concave functions of singular values and its applications in low-rank matrix recovery

Abstract

In this paper, we establish the following perturbation result concerning the singular values of a matrix: Let A,B,E Rm×n be given matrices, and let f:R+→R+ be a concave function satisfying f(0)=0. Then, we have min{m,n}Σi=1| (σi(A))-(σi(B)) ≤min{m,n}i=1(σi(A-B)) where ;bsubi;(.) denotes the i-th largest singular value of a matrix. This answers an open question that is of interest to both the compressive sensing and linear algebra communities. In particular, by taking f(.)=;(.)p; for any p∈(0,1], we obtain a perturbation inequality for the so-called Schatten p-quasi-norm, which allows us to confirm the validity of a number of previously conjectured conditions for the recovery of low-rank matrices via the popular Schatten p-quasi-norm heuristic. We believe that our result will find further applications, especially in the study of low-rank matrix recovery.