<< Chapter < Page | Chapter >> Page > |
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 $\text{\#}T\le k$ 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$ :
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.
We will prove a slightly weaker version of this to save time. We first prove that instance optimality for $k$ implies NSP $X$ for $k$ (hence this is slightly weaker than advertised) . Let $\eta \in N$ and set $z=\Delta (0)$ then
We now prove 2. Suppose $\Phi $ has the NSP for $2k$ . Given $y$ , $\mathcal{F}$ $(y)=\{x:\Phi (x)=y\}$ . Let us define the decoder $\Delta $ by $\Delta (y):=\mathrm{arg}\mathrm{min}\{{\sigma}_{K}{(x)}_{X}:x\in \text{}\mathcal{F}\text{}(y)\}$ , then
$\begin{array}{l}\begin{array}{l}\begin{array}{l}{\parallel x-\mathrm{\Delta}\left(\mathrm{\Phi}\right(x\left)\right)\parallel}_{X}={\parallel x-{x}^{\prime}\parallel}_{X}\phantom{\rule{0ex}{0ex}}\\ \le {c}_{1}{\sigma}_{2K}(x-{x}^{\prime})\end{array}\\ \le {c}_{1}\left({\sigma}_{K}\right(x)-{\sigma}_{K}({x}^{\prime}\left)\right)\text{}\phantom{\rule[-0.0ex]{3.0em}{0.0ex}}\text{specific 2K term approximation}\end{array}\\ \le 2{c}_{1}{\sigma}_{K}\left(x\right)\end{array}\phantom{\rule{0ex}{0ex}}$
QED.
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.
Notification Switch
Would you like to follow the 'Compressive sensing' conversation and receive update notifications?