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

In this paper, we establish the following perturbation result concerning the singular values of a matrix: Let A,B∈Rm×nA,B∈Rm×n be given matrices, and let f:R+→R+f:R+→R+ be a concave function satisfying f(0)=0f(0)=0. Then, we have∑i=1min⁡{m,n}|f(σi(A))−f(σi(B))|≤∑i=1min⁡{m,n}f(σi(A−B)), where σi(⋅)σi(⋅) 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(⋅)=(⋅)pf(⋅)=(⋅)p for any p∈(0,1]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.