Error bounds for consistent reconstruction: random polytopes and coverage processes

Understand

Consistent reconstruction is a method for producing an estimate $\widetilde{x} \in \mathbb{R}^d$ of a signal $x\in \mathbb{R}^d$ if one is given a collection of $N$ noisy linear measurements $q_n = \langle x, \varphi_n \rangle + \epsilon_n$, $1 \leq n \leq N$, that have been corrupted by i.i.d.

• uniform noise $\{\epsilon_n\}_{n=1}^N$.
• We prove mean squared error bounds for consistent reconstruction when the measurement vectors $\{\varphi_n\}_{n=1}^N\subset \mathbb{R}^d$ are drawn independently at random from a suitable distribution on the unit-sphere $\mathbb{S}^{d-1}$.
• Our main results prove that the mean squared error (MSE) for consistent reconstruction is of the optimal order $\mathbb{E}\|x - \widetilde{x}\|^2 \leq K\delta^2/N^2$ under general conditions on the measurement vectors.