Error Bounds for Consistent Reconstruction: Random Polytopes and Coverage Processes

Consistent reconstruction is a method for producing an estimate $$widetilde{x} in {mathbb {r}}^d$$ of a signal $$xin {mathbb {r}}^d$$ if one is given a collection of $$n$$ noisy linear measurements $$q_n = langle x, varphi _n rangle + epsilon _n$$ , $$1 le n le 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}^nsubset {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}}vert x - widetilde{x}vert ^2 le kdelta ^2/n^2$$ under general conditions on the measurement vectors. we also prove refined mse bounds when the measurement vectors are i.i.d. uniformly distributed on the unit-sphere $${mathbb {s}}^{d-1}$$ and, in particular, show that in this case, the constant $$k$$ is dominated by $$d^3$$ , the cube of the ambient dimension. the proofs involve an analysis of random polytopes using coverage processes on the sphere.