In this paper, we establish the following perturbation result concerning the singular values of a matrix: Let $A,B \in \mathbb{ R}^{ m\times n}$ be given matrices, and let $f:\mathbb{ R}_+\rightarrow\mathbb{ R}_+$ be a concave function satisfying $f(0)=0$. Then, we have $$ \sum_{ i=1}^{ \min\{ m,n\}} \big| f(\sigma_i(A)) - f(\sigma_i(B)) \big| \le \sum_{ i=1}^{ \min\{ m,n\}} f(\sigma_i(A-B)), $$ where $\sigma_i(\cdot)$ 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(\cdot)=(\cdot)^p$ for any $p \in (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.
Categories: math.OC cs.IT math.IT