Sparse recovery and nullspace certificates — Examples and Counterexamples

Given: $A=[11]$, $s=1$, and the vectors $h=(1,-1)$, $x^{†}=(1,0)$, and $z=(0,1)$ in ${\mathbb{R}}^2$.

The strict nullspace property: strict NSP requires $\mathrm{\parallel }{h}_S{\mathrm{\parallel }}_1<\mathrm{\parallel }{h}_{S^c}{\mathrm{\parallel }}_1$ for every nonzero kernel vector and every $S$ of size at most $s$.

The $p$-norms $\parallel x{\parallel }_p$ for rational $p\ge 1$, and $\parallel x{\parallel }_{\mathrm{\infty }}$: on ${\mathbb{R}}^2$, $\mathrm{\parallel }u{\mathrm{\parallel }}_1=\mathrm{\mid }{u}_1\mathrm{\mid }+\mathrm{\mid }{u}_2\mathrm{\mid }$.

The triangle inequality: $\mathrm{\mid }a+b\mathrm{\mid }\le \mathrm{\mid }a\mathrm{\mid }+\mathrm{\mid }b\mathrm{\mid }$ for real $a,b$.

The strict nullspace property: the matrix-vector product is computed by the one-based row formula in the definition.

Given: The matrix $A=\left(\begin{array}{ccc}1& -1& 0\\ 1& 0& 1\end{array}\right)$ and sparsity order $s=1$.

The strict nullspace property: strict NSP requires $\mathrm{\parallel }{h}_S{\mathrm{\parallel }}_1<\mathrm{\parallel }{h}_{S^c}{\mathrm{\parallel }}_1$ for each nonzero kernel vector and every $S$ with $\mathrm{\mid }S\mathrm{\mid }\le s$.

The $p$-norms $\parallel x{\parallel }_p$ for rational $p\ge 1$, and $\parallel x{\parallel }_{\mathrm{\infty }}$: the ${\mathrm{\ell }}_1$ norm is the sum of coordinate absolute values.

Exact basis-pursuit recovery under the strict nullspace property: a matrix with strict NSP of order $s$ uniquely recovers every vector with at most $s$ nonzero coordinates by exact ${\mathrm{\ell }}_1$ minimization.

Each $\parallel \cdot {\parallel }_p$ is a norm on ${\mathbb{R}}^n$, and the induced metrics are exactly $d_1$, $d_2$ and $d_{\mathrm{\infty }}$ of the published metric-spaces page: the defined ${\mathrm{\ell }}_1$ function is a norm on ${\mathbb{R}}^3$.

The strict nullspace property: under its coordinate relabeling, $(Au{)}_i={\sum }_{j=1}^n{A}_{ij}{u}_j$ for each row $i$.

Given: The Axiom of Choice; integers $n\ge 1$, $d\ge 2$, and $1\le s\le d\mathrm{/}2$; $\sigma >0$; the class ${\mathrm{\Theta }}_{s,d}$ and independent Gaussian observation law in the Example; and a Borel estimator $T:{\mathbb{R}}^d\to {\mathbb{R}}^d$.

The Axiom of Choice: the Axiom of Choice states that every family of nonempty sets has a choice function; the minimax supplier used below explicitly assumes this axiom.

The strict nullspace property: the strict nullspace property tests every nonzero $h\in \ker A$; if $\ker A=\{0\}$, the condition is vacuous for every admissible order $1\le s\le d$.

Exact basis-pursuit recovery under the strict nullspace property: strict NSP of order $s$ implies unique noiseless ${\mathrm{\ell }}_1$ recovery for every vector with at most $s$ nonzero coordinates.

Gaussian sparse-sequence minimax lower bound: under AC, for $n,d\ge 1$, $\sigma >0$, and $1\le s\le d\mathrm{/}2$, independent $N({\theta }_j,{\sigma }^2\mathrm{/}n)$ coordinates over ${\mathrm{\Theta }}_{s,d}$ give every Borel estimator squared-${\mathrm{\ell }}_2$ risk at least ${\sigma }^{2}s\log (ed\mathrm{/}s)\mathrm{/}(200000n)$ in the worst case.

The $p$-norms $\parallel x{\parallel }_p$ for rational $p\ge 1$, and $\parallel x{\parallel }_{\mathrm{\infty }}$: $\mathrm{\parallel }u{\mathrm{\parallel }}_2^2={\sum }_{j=1}^d{u}_j^2$ for $u\in {\mathbb{R}}^d$.

Each $\parallel \cdot {\parallel }_p$ is a norm on ${\mathbb{R}}^n$, and the induced metrics are exactly $d_1$, $d_2$ and $d_{\mathrm{\infty }}$ of the published metric-spaces page: the defined ${\mathrm{\ell }}_2$ function is a norm on ${\mathbb{R}}^d$.

Rectangular matrix multiplication and the identity matrix $I_n$, including zero-sized shapes: $I_d$ has diagonal entries $1$ and off-diagonal entries $0$.

The strict nullspace property: $(Au{)}_i={\sum }_{j=1}^d{A}_{ij}{u}_j$ under the one-based coordinate relabeling.

Laws of finite sums and finite products: finite sums split at an index, and the sum of a list with exactly one nonzero term is that term.