TY - JOUR

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

AU - Yue, Man Chung

AU - So, Anthony Man Cho

N1 - Funding Information:
We thank the two anonymous referees for their insightful comments. We would also like to thank Liang Chen and Defeng Sun for pointing out an inaccuracy in an earlier version of Theorem 3 and for suggesting Example 1 . This research is supported in part by the Hong Kong Research Grants Council (RGC) General Research Fund (GRF) Project CUHK 416413 and in part by a gift grant from Microsoft Research Asia .
Publisher Copyright:
© 2015 Elsevier Inc. All rights reserved.

PY - 2016/3/1

Y1 - 2016/3/1

N2 - 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.

AB - 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.

KW - Exact and robust recovery

KW - Low-rank matrix recovery

KW - Schatten quasi-norm

KW - Singular value perturbation inequality

UR - http://www.scopus.com/inward/record.url?scp=84953635310&partnerID=8YFLogxK

U2 - 10.1016/j.acha.2015.06.006

DO - 10.1016/j.acha.2015.06.006

M3 - Letter

AN - SCOPUS:84953635310

SN - 1063-5203

VL - 40

SP - 396

EP - 416

JO - Applied and Computational Harmonic Analysis

JF - Applied and Computational Harmonic Analysis

IS - 2

ER -