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

Man Chung Yue, Anthony Man Cho So

Research output: Journal article publicationLetterAcademic researchpeer-review

13 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)396-416
Number of pages21
JournalApplied and Computational Harmonic Analysis
Volume40
Issue number2
DOIs
Publication statusPublished - 1 Mar 2016
Externally publishedYes

Keywords

  • Exact and robust recovery
  • Low-rank matrix recovery
  • Schatten quasi-norm
  • Singular value perturbation inequality

ASJC Scopus subject areas

  • Applied Mathematics

Cite this