Abstract
The theory of sampling and the reconstruction of data has a wide range of applications and a rich collection of techniques. For many methods a core problem is the estimation of the number of samples needed in order to secure a stable and accurate reconstruction. This can often be controlled by the Stable Sampling Rate (SSR). In this paper we discuss the SSR and how it is crucial for two key linear methods in sampling theory: generalized sampling and the recently developed Parametrized Background Data Weak (PBDW) method. Both of these approaches rely on estimates of the SSR in order to be accurate. In many areas of signal and image processing binary samples are crucial and such samples, which can be modelled by Walsh functions, are the core of our analysis. As we show, the SSR is linear when considering binary sampling with Walsh functions and wavelet reconstruction. Moreover, for certain wavelets it is possible to determine the SSR exactly, allowing sharp estimates for the performance of the methods.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
B. Adcock, A. Hansen, G. Kutyniok, and J. Ma. Linear stable sampling rate: Optimality of 2d wavelet reconstructions from fourier measurements. SIAM J. Math. Anal., 47(2):1196–1233, 2015.
B. Adcock, A. Hansen, and C. Poon. Beyond consistent reconstructions: optimality and sharp bounds for generalized sampling, and application to the uniform resampling problem. SIAM J. Math. Anal., 45(5):3132–3167, 2013.
B. Adcock, A. Hansen, and C. Poon. On optimal wavelet reconstructions from fourier samples: linearity and universality. Appl. Comput. Harmon. Anal., 36(3):387–415, 2014.
B. Adcock and A. C. Hansen. A generalized sampling theorem for stable reconstructions in arbitrary bases. J. Fourier Anal. Appl., 18(4):685–716, 2010.
B. Adcock and A. C. Hansen. Generalized sampling and infinite-dimensional compressed sensing. Foundations of Computational Mathematics, 16(5):1263–1323, Oct 2016.
V. Antun. Coherence estimates between hadamard matrices and daubechies wavelets. Master’s thesis, University of Oslo, 2016.
M. Bachmayr, A. Cohen, R. DeVore, and G. Migliorati. Sparse polynomial approximation of parametric elliptic pdes. part ii: lognormal coefficients. ESAIM: Mathematical Modelling and Numerical Analysis, 51(1):341–363, 2017.
K. Beauchamp. Walsh Functions and their Applications. Academic Press, London, 1975.
P. Binev, A. Cohen, W. Dahmen, R. DeVore, G. Petrova, and P. Wojtaszczyk. Convergence rates for greedy algorithms in reduced basis methods. SIAM journal on mathematical analysis, 43(3):1457–1472, 2011.
P. Binev, A. Cohen, W. Dahmen, R. DeVore, G. Petrova, and P. Wojtaszczyk. Data assimilation in reduced modeling. SIAM/ASA Journal on Uncertainty Quantification, 5(1):1–29, 2017.
A. Böttcher. Infinite matrices and projection methods: in lectures on operator theory and its applications, fields inst. monogr. Amer. Math. Soc., (3):1–72, 1996.
A. Buffa, Y. Maday, A. T. Patera, C. Prud’homme, and G. Turinici. A priori convergence of the greedy algorithm for the parametrized reduced basis method. ESAIM: Mathematical Modelling and Numerical Analysis, 46(3):595–603, 2012.
P. Butzer and H. Wagner. On the dyadic analysis based on pointwise dyadic derivative. Anal. Math., (1):171–196, 1975.
K. Choi, S. Boyd, J. Wang, L. Xing, L. Zhu, and T.-S. Suh. Compressed Sensing Based Cone-Beam Computed Tomography Reconstruction with a First-Order Method. Medical Physics, 37(9), 2010.
A. Cohen, I. Daubechies, and P. Vial. Wavelets on the interval and fast wavelet transforms. Comput. Harmon. Anal., 1(1):54–81, 1993.
R. DeVore, G. Petrova, and P. Wojtaszczyk. Greedy algorithms for reduced bases in banach spaces. Constructive Approximation, 37(3):455–466, 2013.
R. DeVore, G. Petrova, and P. Wojtaszczyk. Data assimilation and sampling in banach spaces. Calcolo, 54(3):963–1007, 2017.
M. Gataric and C. Poon. A practical guide to the recovery of wavelet coefficients from fourier measurements. SIAM J. Sci. Comput., 38(2):A1075–A1099.
E. Gauss. Walsh Funktionen für Ingenieure und Naturwissenschaftler. Springer Fachmedien, Wiesbaden, 1994.
K. Gröchenig, Z. Rzeszotnik, and T. Strohmer. Quantitative estimates for the finite section method and banach algebras of matrices. Integral Equations and Operator Theory, 2(67):183–202, 2011.
M. Guerquin-Kern, M. Häberlin, K. Pruessmann, and M. Unser. A fast wavelet-based reconstruction method for magnetic resonance imaging. IEEE Transactions on Medical Imaging, 30(9):1649–1660, 2011.
A. C. Hansen. On the approximation of spectra of linear operators on hilbert spaces. J. Funct. Anal., 8(254):2092–2126, 2008.
A. C. Hansen and L. Terhaar. On the stable sampling rate for binary measurements and wavelet reconstruction. preprint, 2017.
T. Hrycak and K. Gröchenig. Pseudospectral fourier reconstruction with the modified inverse polynomial reconstruction method. J. Comput. Phys., 229(3):933–946, 2010.
A. J. Jerri. The shannon sampling theorem – its various extensions and applications: A tutorial review. Proc. IEEE, (65):1565–1596, 1977.
A. Jones, A. Tamtögl, I. Calvo-Almazán, and A. C. Hansen. Continuous compressed sensing for surface dynamical processes with helium atom scattering. Nature Sci. Rep., 6:27776 EP –, 06 2016.
A. F. Lawrence, S. Phan, and M. Ellisman. Electron tomography and multiscale biology. In M. Agrawal, S. Cooper, and A. Li, editors, Theory and Applications of Models of Computation, volume 7287 of Lecture Notes in Computer Science, pages 109–130. Springer Berlin Heidelberg, 2012.
R. Leary, Z. Saghi, P. A. Midgley, and D. J. Holland. Compressed sensing electron tomography. Ultramicroscopy, 131(0):70–91, 2013.
M. Lindner. Infinite matrices and their finite sections: An introduction to the limit operator method. Birkhäuser Verlag, Basel, 2006.
M. Lustig, D. Donoho, and J. M. Pauly. Sparse mri: the application of compressed sensing for rapid mr imaging. Magnetic Resonance in Medicine, 2007.
Y. Maday, A. T. Patera, J. D. Penn, and M. Yano. A parameterized-background data-weak approach to variational data assimilation: formulation, analysis, and application to acoustics. International Journal for Numerical Methods in Engineering, 102(5):933–965, 2015.
N. Mahadevan and K. A. Hoo. Wavelet-based model reduction of distributed parameter systems. 55:4271–4290, 10 2000.
S. Mallat. A wavelet tour of signal processing. Academic Press, San Diego, 1998.
C. Poon. A consistent and stable approach to generalized sampling. J. Fourier Anal. Appl., (20):985–1019, 2014.
E. T. Quinto. An introduction to X-ray tomography and Radon transforms. In The Radon Transform, Inverse Problems, and Tomography, volume 63, pages 1–23. American Mathematical Society, 2006.
B. Roman, B. Adcock, and A. C. Hansen. On asymptotic structure in compressed sensing. arXiv:1406.4178, 2014.
F. Schipp, P. Simon, and W. Wade. Walsh Series an Introduction to dyadic haromonic Analysis. Adam Hilger, Bristol and New York, 1990.
C. Shannon. A mathematical theory of communication. Bell Syst. Tech. J., (27):379–423, 623–656, 1948.
V. Studer, J. Bobin, M. Chahid, H. S. Mousavi, E. Candes, and M. Dahan. Compressive fluorescence microscopy for biological and hyperspectral imaging. Proceedings of the National Academy of Sciences, 109(26):E1679–E1687, 2012.
M. Unser. Sampling - 50 years after shannon. Proc. IEEE, 4(88):569–587, 2000.
P. Wojtaszczyk. On greedy algorithm approximating kolmogorov widths in banach spaces. Journal of Mathematical Analysis and Applications, 424(1):685–695, 2015.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Thesing, L., Hansen, A. Linear Reconstructions and the Analysis of the Stable Sampling Rate. STSIP 17, 103–126 (2018). https://doi.org/10.1007/BF03549616
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF03549616