Small coherence implies the weak Null Space Property
This is an incremental theoretical result for the Compressed Sensing community, clarifying relationships between existing properties.
The paper tackles the problem of establishing a connection between coherence and the weak Null Space Property in Compressed Sensing, showing that small coherence implies the weak Null Space Property for most index subsets with a given cardinality.
In the Compressed Sensing community, it is well known that given a matrix $X \in \mathbb R^{n\times p}$ with $\ell_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 \subset \{1,\ldots,p\}$ with size governed by $μ$ and $δ$. In this short note, we show that a small Coherence implies a weak Null Space Property, i.e. $\Vert h_T\Vert_2 \le C \ \Vert h_{T^c}\Vert_1/\sqrt{s}$ for most $T \subset \{1,\ldots,p\}$ with cardinality $|T|\le s$. We moreover prove some singular value perturbation bounds that may also prove useful for other applications.