1.1 Gelfand n-widths (ticket #3905)

Continuing from last time, we have a signal $x\in {\mathbb{R}}^N$ , an $n\times N$ measurement matrix $\Phi$ , and $y=\Phi x\in {\mathbb{R}}^n$ is the information we draw from $x$ .

We consider decoders $\Delta$ mapping ${\mathbb{R}}^n\to {\mathbb{R}}^N$ . We have been discussing whether there exists a decoder withcertain properties. So for this discussion (about information preservation), we can just think about optimal decoding.

While the previous result on sparse signal recovery is interesting, it is not very robust. What happens if our signal does not have support $k$ ? Can we still obtain meaningful results? The answer is yes. To do so we introduce more general input signal classes $K\subseteq X$ that allows fully supported signals. For example, we will consider the signal class defined by the unit ball

We will see that these questions are actually equivalent to a classical “ $n$ -width” problem. $n$ -widths have seen a great deal of work over the years by a variety of mathematicians: Kolmogorov, Tikhomirov, Kashin, Gluskin, etc. There are many different flavors of $n$ -widths, but we will study the Gelfand $n$ -width (the least intuitive of the widths).

Gelfand n-width

Let $K\subseteq X$ be compact. Given $n$ , the Gelfand width (also called the dual width) is given by

In other words, we are looking for the subspace $Y$ that slices through the set $K$ so that the norms of the projected signals are as small as possible. We can now state the following theorem about n-widths:

Provided that $K$ has the properties (1) $K=-K$ and (2) $K+K=CK$ , then

We start with the left-hand inequality. We want to take any encoder/decoder pair and use that to construct a $Y$ . So let $\Phi ,\Delta$ be an encoder/decoder. Then simply let $Y=\mathcal{N}\left(\Phi \right)$ . Now consider an $\eta \in K\cap Y$ and note that $\Phi \left(\eta \right)=0$ since $\eta \in Y$ . Let $z=\Delta \left(0\right)$ be the decoding of 0 (practically speaking, $z$ should be zero itself, but we avoid that assumption in this proof). Then

Now we prove the right-hand inequality. Assume we have a good $Y$ . Suppose $Y$ has codimension $N-n$ . Then $Y^{\perp }$ (the orthogonal complement of $Y$ in ${\mathbb{R}}^N$ ) has dimension $n$ . Let $v_1,v_2,\cdots ,v_n\in {\mathbb{R}}^N$ be a basis for $Y^{\perp }$ . Let $\Phi$ be the $n\times N$ matrix obtained by stacking the rows $v_1,v_2,\cdots ,v_n$ . Then $\mathcal{N}\left(\Phi \right)=Y$ . Define $\Delta \left(y\right)=$ any element of $K\cap \mathcal{F}\left(y\right)$ if there is one (otherwise let $\Delta \left(y\right)$ be anything in $\mathcal{F}\left(y\right)$ ). Now look at the performance $\parallel x-\Delta \Phi \left(x\right){\parallel }_X$ for some $x\in K$ . Both $x$ and $\Delta \Phi \left(x\right)=:x^{\text{'}}$ are elements of $K$ , so $x-x^{\text{'}}$ is in $\mathcal{N}\left(\Phi \right)$ and in $CK$ . Therefore $\frac{x-x^{\text{'}}}{C}\in K\cap \mathcal{N}\left(\Phi \right)$ . Thus,

From the proof of this theorem, we see that there is a matching between the matrices $\Phi$ and the spaces $Y$ (via the nullspace of $\Phi$ ).

An important result is that $d^n{\left(U\right({\ell }_q^N\left)\right)}_{{\ell }_p^N}$ is known for all $p,q$ except $p=1,q=\infty$ . A precise statement of these widths can be found in the book . A particularly important case is