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 -