3.4 The nullspace property

We begin with a property of the null space $N$ which is at the heart of proving results on instance-optimality.

We say that $N$ has the Null Space Property if for all $\eta \in N$ and all $T$ with we have ${\parallel \eta \parallel }_X\le c_1{\parallel {\eta }_{T^C}\parallel }_X$

Intuitively, NSP implies that for any vector in the nullspace the energy will not be concentrated in a small number of entries.

The following are equivalent formulations for NSP $X$ for $k$ :

• ${\parallel \eta \parallel }_X\le c_1{\sigma }_k\left(\eta \right)$
• ${\parallel {\eta }_T\parallel }_X\le c_1^{\prime }{\parallel {\eta }_{T^C}\parallel }_X$ where $\eta ={\eta }_T+{\eta }_{T^C}$ .

Note also that the triangle inequality can be used as follows

$${\parallel \eta \parallel }_X={\parallel {\eta }_T+{\eta }_{T^C}\parallel }_X\le {\parallel {\eta }_T\parallel }_X+{\parallel {\eta }_{T^C}\parallel }_X$$

which shows that (b) is equivalent to NSP.

• If $(\Phi ,\Delta )$ is instance optimal on $X$ for the value $k$ , then $\Phi$ satisfies the NSP for $2k$ on $X$ with an equivalent constant.
• If $\Phi$ has the NSP for $X$ and $2k$ then $\exists \Delta$ s.t. $\Phi$ has the instance optimal property for $k$ .

Note that the instance optimal property automatically gives reproduction of $K$ -sparse signals.

At this stage the challenge is to create $\Phi$ with this instance optimal property. For this we shall use the restricted isometry property as introduced earlier and which we now recall.