Upper bounds on the error of sparse vector and low-rank matrix recovery

作者：Malek Mohammadi Mohammadreza^*; Rojas Cristian R; Jansson Magnus; Babaie Zadeh Massoud

来源：Signal Processing, 2016, 120: 249-254.

DOI：10.1016/j.sigpro.2015.09.003

• Approximately sparse solutions
• Low-rank matrix recovery
• Restricted isometry property
• Sparse vector recovery

Suppose that a solution (x) over tilde to an underdetermined linear system b = Ax is given. (x) over tilde is approximately sparse meaning that it has a few large components compared to other small entries. However, the total number of nonzero components of (x) over tilde is large enough to violate any condition for the uniqueness of the sparsest solution. On the other hand, if only the dominant components are considered, then it will satisfy the uniqueness conditions. One intuitively expects that (x) over tilde should not be far from the true sparse solution x(0). It was already shown that this intuition is the case by providing upper bounds on parallel to(x) over tilde - x(0)parallel to which are functions of the magnitudes of small components of (x) over tilde but independent from x(0). In this paper, we tighten one of the available bounds on parallel to(x) over tilde - x(0)parallel to and extend this result to the case that b is perturbed by noise. Additionally, we generalize the upper bounds to the low-rank matrix recovery problem.

• 出版日期2016-3