Name
Abstract | ||
|---|---|---|
Consistent reconstruction is a method for producing an estimate $$\\widetilde{x} \\in {\\mathbb {R}}^d$$x~¿Rd of a signal $$x\\in {\\mathbb {R}}^d$$x¿Rd if one is given a collection of $$N$$N noisy linear measurements $$q_n = \\langle x, \\varphi _n \\rangle + \\epsilon _n$$qn=¿x,¿n¿+∈n, $$1 \\le n \\le N$$1≤n≤N, that have been corrupted by i.i.d. uniform noise $$\\{\\epsilon _n\\}_{n=1}^N$${∈n}n=1N. We prove mean-squared error bounds for consistent reconstruction when the measurement vectors $$\\{\\varphi _n\\}_{n=1}^N\\subset {\\mathbb {R}}^d$${¿n}n=1N¿Rd are drawn independently at random from a suitable distribution on the unit-sphere $${\\mathbb {S}}^{d-1}$$Sd-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 K\\delta ^2/N^2$$E¿x-x~¿2≤K¿2/N2 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}$$Sd-1 and, in particular, show that in this case, the constant $$K$$K is dominated by $$d^3$$d3, the cube of the ambient dimension. The proofs involve an analysis of random polytopes using coverage processes on the sphere. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s10208-015-9251-2 | Foundations of Computational Mathematics |
Keywords | Field | DocType |
Consistent reconstruction,Coverage processes,Estimation with uniform noise,Random polytopes,Primary 62H12,Secondary 60D05,94A15 | Discrete mathematics,Mathematical optimization,Combinatorics,Mathematical analysis,Polytope,Mathematics,Cube | Journal |
Volume | Issue | ISSN |
abs/1405.7094 | 2 | 1615-3375 |
Citations | PageRank | References |
3 | 0.38 | 12 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexander M. Powell | 1 | 46 | 3.60 |
| J. Tyler Whitehouse | 2 | 13 | 1.09 |