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

preprint2014arXivOpen access

Abstract

In this paper, we establish the following perturbation result concerning the singular values of a matrix: Let A,B∈Rm×nA,B \in \mathbb{R}^{m\times n} be given matrices, and let f:R+→R+f:\mathbb{R}_+\rightarrow\mathbb{R}_+ be a concave function satisfying f(0)=0f(0)=0. Then, we have ∑i=1min⁡{m,n}∣f(σi(A))−f(σi(B))∣≤∑i=1min⁡{m,n}f(σi(A−B)), \sum_{i=1}^{\min\{m,n\}} \big| f(σ_i(A)) - f(σ_i(B)) \big| \le \sum_{i=1}^{\min\{m,n\}} f(σ_i(A-B)), where σi(⋅)σ_i(\cdot) denotes the ii--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(⋅)=(⋅)pf(\cdot)=(\cdot)^p for any p∈(0,1]p \in (0,1], we obtain a perturbation inequality for the so--called Schatten pp--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 pp--quasi--norm heuristic. We believe that our result will find further applications, especially in the study of low--rank matrix recovery.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.