A Perturbation Inequality for the Schatten-$p$ Quasi-Norm and Its Applications to Low-Rank Matrix Recovery

Abstract

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}}_{+}\to {\mathbb{R}}_{+}$ be a concave function satisfying $f(0)=0$. Then, we have $$\sum _{i=1}^{\min \{m,n\}}|f({\sigma }_i(A))-f({\sigma }_i(B))|\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.

References in corpus (1)

• Measure What Should be Measured: Progress and Challenges in Compressive Sensing

Cited by in corpus (1)

• Schatten-$p$ Quasi-Norm Regularized Matrix Optimization via Iterative Reweighted Singular Value Minimization