Error Bounds for Consistent Reconstruction: Random Polytopes and Coverage Processes

详细信息    查看全文

• 作者：Alexander M. Powell ; J. Tyler Whitehouse
• 关键词：Consistent reconstruction ; Coverage processes ; Estimation with uniform noise ; Random polytopes
• 刊名：Foundations of Computational Mathematics
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：16
• 期：2
• 页码：395-423
• 全文大小：748 KB
• 参考文献：1.P. Boufounos and R. Baraniuk, Quantization of sparse representations, Rice University ECE Department Technical Report 0701.
  2.A. Brieden, P. Gritzmann, R. Kannan, V. Klee, L. Lovász and M. Simonivits, Deterministic and randomized polynomial-time approximation of radii, Mathematika 48 (2001), 63–105.CrossRef MathSciNet MATH
  3.P. Bürgisser, F. Cucker and M. Lotz, Coverage processes on spheres and condition numbers for linear programming, The Annals of Probability 38 (2010), 570–604.CrossRef MathSciNet MATH
  4.Z. Cvetković and M. Vetterli, On simple oversampled A/D conversion in \(L^2(\mathbb{R})\) , IEEE Transactions on Information Theory 47 (2001), no. 1, 146–154.CrossRef MATH
  5.Z. Cvetković, Resilience properties of redundant expansions under additive noise and quantization, IEEE Transactions on Information Theory 49 (2003), no. 3, 644–656.CrossRef MATH
  6.T.S. Ferguson, A Course in Large Sample Theory, Chapman & Hall, London, 1996.CrossRef MATH
  7.L. Flatto and D.J. Newman, Random coverings, Acta Mathematica 138 (1977), 241–264.CrossRef MathSciNet MATH
  8.V.K. Goyal, J. Kovačević and J.A. Kelner, Quantized frame expansions with erasures, Applied and Computational Harmonic Analysis 10 (2001), no. 3, 203–233.CrossRef MathSciNet MATH
  9.V.K. Goyal, M. Vetterli and N.T. Thao, Quantized overcomplete expansions in \({\mathbb{R}}^n\) : analysis, synthesis, and algorithms, IEEE Transactions on Information Theory 44 (1998), no.1, 16–30.CrossRef MathSciNet MATH
  10.L. Jacques, D.K. Hammond and J.M. Fadili, Dequantizing compressed sensing: when oversampling and non-Gaussian constraints combine, IEEE Transactions on Information Theory 57 (2011), no. 1, 560–571.CrossRef MathSciNet
  11.L. Jacques, J.N. Laska, P.T. Boufounos and R.G. Baraniuk, Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors, IEEE Transactions on Information Theory 59 (2013), no. 4, 2082–2102.CrossRef MathSciNet
  12.S. Janson, Random coverings in several dimensions, Acta Mathematica 156 (1986), 83–118.CrossRef MathSciNet MATH
  13.D. Jimenez, L. Wang and Y. Wang, White noise hypothesis for uniform quantization errors, SIAM Journal on Mathematical Analysis 38 (2007), no. 6, 2042–2056.CrossRef MathSciNet MATH
  14.I. Jovanović and B. Beferull-Lozano, Oversampled A/D conversion and error-rate dependence of nonbandlimited signals with finite rate of innovation, IEEE Transactions on Signal Processing 54 (2006), no. 6, 2140–2154.CrossRef
  15. J. Masoušek, Lectures on Discrete Geometry, Springer-Verlag, New York, 2002.
  16.Y. Plan and R. Vershynin, One-bit compressed sensing by linear programming, Communications on Pure and Applied Mathematics 66 (2013), no. 8, 1275–1297.CrossRef MathSciNet MATH
  17.A.M. Powell, Mean squared error bounds for the Rangan-Goyal soft thresholding algorithm, Applied and Computational Harmonic Analysis 29 (2010), no. 3, 251–271.CrossRef MathSciNet MATH
  18.S. Rangan and V.K. Goyal, Recursive consistent estimation with bounded noise, IEEE Transactions on Information Theory 47 (2001), no. 1, 457–464.CrossRef MathSciNet MATH
  19.A.F. Siegel and L. Holst, Covering the circle with random arcs of random sizes, Journal of Applied Probability 19 (1982), no. 2, 373–381.CrossRef MathSciNet MATH
  20.H. Solomon, Geometric Probability, Society for Industrial and Applied Mathematics, Philadelphia, 1978.CrossRef MATH
  21.A.J. Stam, Limit theorems for uniform distributions on spheres in high-dimensional Euclidean spaces, Journal of Applied Probability 19 (1982), no. 1, 221–228.CrossRef MathSciNet MATH
  22.N.T. Thao and M. Vetterli, Deterministic analysis of oversampled A/D conversion and decoding improvement based on consistent estimates, IEEE Transactions on Signal Processing 42 (1994), no. 3, 519–531.CrossRef
  23.N.T. Thao and M. Vetterli, Reduction of the MSE in \(R\) -times oversampled A/D Conversion from \({{\cal O}}(R^{-1})\) to \({{\cal O}}(R^{-2})\) , IEEE Transactions on Signal Processing 42 (1994), 200–203.
  24.N.T. Thao and M. Vetterli, Lower bound on the MSE in over sampled quantization of periodic signals using vector quantization analysis, IEEE Transactions on Information Theory 42 (1996), 469–479.CrossRef MATH
  25.J.G. Wendel, Note on the gamma function, American Mathematical Monthly 55 (1946), no. 9, 563–564.CrossRef MathSciNet
  
• 作者单位：Alexander M. Powell (1)
  J. Tyler Whitehouse (2)
  
  1. Department of Mathematics, Vanderbilt University, Nashville, TN, 37240, USA
  2. Quantitative Scientific Solutions, LLC, Washington, DC, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Numerical Analysis
  Computer Science, general
  Math Applications in Computer Science
  Linear and Multilinear Algebras and Matrix Theory
  Applications of Mathematics
  
• 出版者：Springer New York
• ISSN：1615-3383

文摘

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 \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}^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}}\Vert x - \widetilde{x}\Vert ^2 \le K\delta ^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.