3.2 Instance optimality

Now we consider another way (actually two related ways) to measure optimality of an encoder/decoder pair.

• Instance optimality. Suppose we are in ${ℝ}^N$ with an $n\times N$ measurement matrix $\Phi$ and a decoder $\Delta$ . Recall that
  ${\sigma }_k{(x)}_X:=\underset{z:\text{\#}z\le k}{\inf }\parallel x-z{\parallel }_X\text{.}$
  We say that the encoding/decoding strategy $\Phi ,\Delta$ is instance optimal of order $k$ with constant $C_0$ if
  ${\parallel x-\Delta \Phi (x)\parallel }_X\le C_0{\sigma }_k{(x)}_X$
  for all $x\in {ℝ}^N$ . (Note that we are no longer restricting $x$ to a class $K$ .) Better $\Phi$ ’s have larger $k$ for which this holds. The name “instance optimal” indicates that the encoding/decoding performance depends on each instance of $x$ .
• Mixed-norm instance optimality (MNIO). Let . The encoder/decoder pair $\Phi ,\Delta$ is MNIO for $p,q,k$ , and $C_0$ if
  $\begin{array}{c}{\parallel x-{\mathrm{\Delta }\mathrm{\Phi }(x)}_{}\parallel }_{{\ell }_p^N}\le C_0\frac{{{\sigma }_k{(x)}_{}}_{{\ell }_q^N}}{k^{1∕q-1∕p}}\text{.}\end{array}$
  Cases of interest include asking whether
  $\begin{array}{c}{\parallel x-{\mathrm{\Delta }\mathrm{\Phi }(x)}_{}\parallel }_{{\ell }_2^N}\le C_0{{\sigma }_k{(x)}_{}}_{{\ell }_1^N}\text{.}\end{array}$
  and whether
  $\begin{array}{c}{\parallel x-{\mathrm{\Delta }\mathrm{\Phi }(x)}_{}\parallel }_{{\ell }_2^N}\le C_0\frac{{{\sigma }_k{(x)}_{}}_{{\ell }_1^N}}{\sqrt{k}}\text{.}\end{array}$

Let’s focus on instance optimality. It would be interesting to know whether a given $\Phi$ satisfies this property. To answer this question, we state an equivalent condition to instance optimality.

Consider the statements

• $\Phi ,\Delta$ is instance optimal of order $k$ on $X$ .
• $\Phi$ has the following nullspace property (NSP): ${\parallel \eta \parallel }_X\le C_1\parallel {\eta }_{T^c}{\parallel }_X\forall \eta \in N(\Phi ),\text{\#}T\le k\text{.}$
• ${\parallel \eta \parallel }_X\le C_1{\sigma }_k{(\eta )}_X\forall \eta \in N(\Phi )\text{.}$
• ${\parallel {\eta }_T\parallel }_X\le C_1^{\prime }\parallel {\eta }_T^c{\parallel }_X\forall \eta \in N(\Phi ),\text{\#}T\le k\text{.}$

Then (b) and (c) are equivalent with the same constant; (d) is equvalent to (b) and (c) but with a different constant. Also (a) with a value $k$ implies (b) with the same $k$ , and (b) with a value $2k$ implies (a) with a value $k$ .