Small coherence implies the weak Null Space Property

Abstract

In the Compressed Sensing community, it is well known that given a matrix X R^n p with _2 normalized columns, the Restricted Isometry Property (RIP) implies the Null Space Property (NSP). It is also well known that a small Coherence implies a weak RIP, i.e. the singular values of X_T lie between 1- and 1+ for "most" index subsets T \1,,p\ with size governed by and . In this short note, we show that a small Coherence implies a weak Null Space Property, i.e. h_T_2 C \ h_T^c_1/s for most T \1,,p\ with cardinality |T| s. We moreover prove some singular value perturbation bounds that may also prove useful for other applications.

Tasks

Reproductions