On optimal wavelet reconstructions from Fourier samples: linearity and universality of the stable sampling rate. (English) Zbl 1293.42037
Summary: In this paper we study the problem of computing wavelet coefficients of compactly supported functions from their Fourier samples. For this, we use the recently introduced framework of generalized sampling. Our first result demonstrates that using generalized sampling one obtains a stable and accurate reconstruction, provided the number of Fourier samples grows linearly in the number of wavelet coefficients recovered. For the class of Daubechies wavelets we derive the exact constant of proportionality.
Our second result concerns the optimality of generalized sampling for this problem. Under some mild assumptions we show that generalized sampling cannot be outperformed in terms of approximation quality by more than a constant factor. Moreover, for the class of so-called perfect methods, any attempt to lower the sampling ratio below a certain critical threshold necessarily results in exponential ill-conditioning. Thus generalized sampling provides a nearly-optimal solution to this problem.
Our second result concerns the optimality of generalized sampling for this problem. Under some mild assumptions we show that generalized sampling cannot be outperformed in terms of approximation quality by more than a constant factor. Moreover, for the class of so-called perfect methods, any attempt to lower the sampling ratio below a certain critical threshold necessarily results in exponential ill-conditioning. Thus generalized sampling provides a nearly-optimal solution to this problem.
MSC:
| 42C40 | Nontrigonometric harmonic analysis involving wavelets and other special systems |
Keywords:
sampling theory; generalized sampling; wavelets; wavelet-encoding; Fourier series; Hilbert spaceReferences:
| [1] | Adcock, B.; Hansen, A. C., Generalized sampling and infinite-dimensional compressed sensing (2011), University of Cambridge, Technical report NA2011/02, DAMTP |
| [2] | Adcock, B.; Hansen, A. C., Reduced consistency sampling in Hilbert spaces, (Proceedings of the 9th International Conference on Sampling Theory and Applications (2011)) |
| [3] | Adcock, B.; Hansen, A. C., A generalized sampling theorem for stable reconstructions in arbitrary bases, J. Fourier Anal. Appl., 18, 4, 685-716 (2012) · Zbl 1259.94035 |
| [4] | Adcock, B.; Hansen, A. C., Stable reconstructions in Hilbert spaces and the resolution of the Gibbs phenomenon, Appl. Comput. Harmon. Anal., 32, 3, 357-388 (2012) · Zbl 1245.94058 |
| [5] | Adcock, B.; Hansen, A. C.; Herrholz, E.; Teschke, G., Generalized sampling: extension to frames and ill-posed problems, Inverse Problems, 29, 015008 (2013) · Zbl 1321.42048 |
| [6] | Adcock, B.; Hansen, A. C.; Poon, C., Beyond consistent reconstructions: optimality and sharp bounds for generalized sampling, and application to the uniform resampling problem, SIAM J. Math. Anal. (2013), in press · Zbl 1320.94035 |
| [7] | Blumensath, T., Sampling theorems for signals from the union of finite-dimensional linear subspaces, IEEE Trans. Inform. Theory, 55, 4, 1872-1882 (2009) · Zbl 1367.94144 |
| [8] | Candès, E. J., An introduction to compressive sensing, IEEE Signal Process. Mag., 25, 2, 21-30 (2008) |
| [9] | Candès, E. J.; Donoho, D. L., Recovering edges in ill-posed inverse problems: optimality of curvelet frames, Ann. Statist., 30, 3, 784-842 (2002) · Zbl 1101.62335 |
| [10] | Candès, E. J.; Donoho, D. L., New tight frames of curvelets and optimal representations of objects with piecewise \(C^2\) singularities, Comm. Pure Appl. Math., 57, 2, 219-266 (2004) · Zbl 1038.94502 |
| [11] | Chui, C.; Wang, J., On compactly supported spline wavelets and a duality principle, Trans. Amer. Math. Soc., 330, 2, 903-915 (1992) · Zbl 0759.41008 |
| [12] | Cohen, A.; Daubechies, I.; Feauveau, J., Biorthogonal bases of compactly supported wavelets, Comm. Pure Appl. Math., 45, 5, 485-560 (2006) · Zbl 0776.42020 |
| [13] | Dahlke, S.; Kutyniok, G.; Maass, P.; Sagiv, C.; Stark, H.-G.; Teschke, G., The uncertainty principle associated with the continuous shearlet transform, Int. J. Wavelets Multiresolut. Inf. Process., 6, 2, 157-181 (2008) · Zbl 1257.42047 |
| [14] | Dahlke, S.; Kutyniok, G.; Steidl, G.; Teschke, G., Shearlet coorbit spaces and associated Banach frames, Appl. Comput. Harmon. Anal., 27, 2, 195-214 (2009) · Zbl 1171.42019 |
| [15] | Daubechies, I., Ten Lectures on Wavelets, CBMS-NSF Regional Conf. Ser. in Appl. Math. (1992), Society for Industrial and Applied Mathematics · Zbl 0776.42018 |
| [16] | Daubechies, I.; Defrise, M.; De Mol, C., An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math., 57, 11, 1413-1457 (2004) · Zbl 1077.65055 |
| [17] | Do, M. N.; Vetterli, M., The Contourlet transform: An efficient directional multiresolution image representation, IEEE Trans. Image Process., 14, 12, 2091-2106 (2005) |
| [18] | Dvorkind, T.; Eldar, Y. C., Robust and consistent sampling, IEEE Signal Process. Lett., 16, 9, 739-742 (2009) |
| [19] | Eldar, Y. C., Sampling with arbitrary sampling and reconstruction spaces and oblique dual frame vectors, J. Fourier Anal. Appl., 9, 1, 77-96 (2003) · Zbl 1028.94020 |
| [20] | Eldar, Y. C., Sampling without input constraints: Consistent reconstruction in arbitrary spaces, (Zayed, A. I.; Benedetto, J. J., Sampling, Wavelets and Tomography (2004), Birkhäuser: Birkhäuser Boston, MA), 33-60 · Zbl 1062.94536 |
| [21] | Eldar, Y. C., Robust recovery of signals from a structured union of subspaces, IEEE Trans. Inform. Theory, 55, 11, 5302-5316 (2009) · Zbl 1367.94087 |
| [22] | Eldar, Y. C.; Dvorkind, T., A minimum squared-error framework for generalized sampling, IEEE Trans. Signal Process., 54, 6, 2155-2167 (2006) · Zbl 1374.94720 |
| [23] | (Eldar, Y. C.; Kutyniok, G., Compressed Sensing: Theory and Applications (2012), Cambridge University Press) |
| [24] | Eldar, Y. C.; Werther, T., General framework for consistent sampling in Hilbert spaces, Int. J. Wavelets Multiresolut. Inf. Process., 3, 3, 347 (2005) · Zbl 1075.42010 |
| [25] | Erdélyi, T., Remez-type inequalities on the size of generalized polynomials, J. Lond. Math. Soc., 45, 255-264 (1992) · Zbl 0757.41023 |
| [26] | Feichtinger, H. G.; Gröchenig, K.; Strohmer, T., Efficient numerical methods in non-uniform sampling theory, Numer. Math., 69, 423-440 (1995) · Zbl 0837.65148 |
| [27] | Fornasier, M.; Rauhut, H., Compressive sensing, (Handbook of Mathematical Methods in Imaging (2011), Springer), 187-228 · Zbl 1259.94017 |
| [28] | Gelman, N.; Wood, M. L., Wavelet encoding for 3-D gradient echo MR-imaging, Magn. Reson. Med., 36, 613-619 (1996) |
| [29] | Guerquin-Kern, M.; Haberlin, M.; Pruessmann, K.; Unser, M., A fast wavelet-based reconstruction method for magnetic resonance imaging, IEEE Trans. Med. Imag., 30, 9, 1649-1660 (2011) |
| [30] | Hansen, A. C., On the solvability complexity index, the \(n\)-pseudospectrum and approximations of spectra of operators, J. Amer. Math. Soc., 24, 1, 81-124 (2011) · Zbl 1210.47013 |
| [31] | Healy, D. M.; Weaver, J. B., Two applications of wavelet transforms in Magnetic Resonance Imaging, IEEE Trans. Inform. Theory, 38, 2, 840-862 (1992) |
| [32] | Hernández, E.; Weiss, G., A First Course on Wavelets, Stud. Adv. Math. (1996), CRC Press · Zbl 0885.42018 |
| [33] | Hirabayashi, A.; Unser, M., Consistent sampling and signal recovery, IEEE Trans. Signal Process., 55, 8, 4104-4115 (2007) · Zbl 1390.94652 |
| [34] | Hrycak, T.; Gröchenig, K., Pseudospectral Fourier reconstruction with the modified inverse polynomial reconstruction method, J. Comput. Phys., 229, 3, 933-946 (2010) · Zbl 1184.65123 |
| [35] | Kutyniok, G.; Lemvig, J.; Lim, W.-Q., Compactly supported shearlets, (Neamtu, M.; Schumaker, L., Approximation Theory XIII. Approximation Theory XIII, San Antonio 2010. Approximation Theory XIII. Approximation Theory XIII, San Antonio 2010, Springer Proc. Math., vol. 13 (2012), Springer: Springer New York), 163-186 · Zbl 1252.42042 |
| [36] | Kyriakos, W. E.; Hoge, W. S.; Mitsouras, D., Generalized encoding through the use of selective excitation in accelerated parallel MRI, NMR Biomed., 19, 379-392 (2006) |
| [37] | Laine, A. F., Wavelets in temporal and spatial processing of biomedical images, Annu. Rev. Biomed. Eng., 02, 511-550 (2000) |
| [38] | Lu, Y. M.; Do, M. N., A theory for sampling signals from a union of subspaces, IEEE Trans. Signal Process., 56, 6, 2334-2345 (2008) · Zbl 1390.94656 |
| [39] | Nowak, R., Wavelet-based Rician noise removal for Magnetic Resonance Imaging, IEEE Trans. Image Process., 8, 1408-1419 (1998) |
| [40] | Panych, L. P., Theoretical comparison of Fourier and wavelet encoding in Magnetic Resonance Imaging, IEEE Trans. Med. Imag., 15, 2, 141-153 (1996) |
| [41] | Panych, L. P.; Jakab, P. D.; Jolesz, F. A., Implementation of wavelet-encoded MR imaging, J. Magn. Reson. Imaging, 3, 649-655 (1993) |
| [42] | Po, D. D.-Y.; Do, M. N., Directional multiscale modeling of images using the contourlet transform, IEEE Trans. Image Process., 15, 6, 1610-1620 (June 2006) |
| [43] | Pruessmann, K. P.; Weiger, M.; Scheidegger, M. B.; Boesiger, P., Sense: sensitivity encoding for fast MRI, Magn. Reson. Med., 42, 5, 952-962 (1999) |
| [44] | Unser, M., Splines: A perfect fit for signal and image processing, IEEE Signal Process. Mag., 16, 6, 22-38 (1999) |
| [45] | Unser, M., Sampling - 50 years after Shannon, Proc. IEEE, 88, 4, 569-587 (2000) · Zbl 1404.94028 |
| [46] | Unser, M.; Aldroubi, A., A general sampling theory for nonideal acquisition devices, IEEE Trans. Signal Process., 42, 11, 2915-2925 (1994) |
| [47] | Unser, M.; Aldroubi, A., A review of wavelets in biomedical applications, Proc. IEEE, 84, 4, 626-638 (1996) |
| [48] | Unser, M.; Aldroubi, A.; Eden, M., On the asymptotic convergence of B-spline wavelets to Gabor functions, IEEE Trans. Inform. Theory, 38, 2, 864-872 (1992) · Zbl 0757.41022 |
| [49] | Unser, M.; Aldroubi, A.; Laine, A. F., Guest editorial: wavelets in medical imaging, IEEE Trans. Med. Imag., 22, 3, 285-288 (2003) |
| [50] | Unser, M.; Zerubia, J., A generalized sampling theory without band-limiting constraints, IEEE Trans. Circuits Syst. II, 45, 8, 959-969 (1998) · Zbl 0998.94519 |
| [51] | Weaver, J. B.; Xu, Y.; Healy, D. M.; Driscoll, J. R., Filtering MR images in the wavelet transform domain, Magn. Reson. Med., 21, 288-295 (1991) |
| [52] | Weaver, J. B.; Xu, Y.; Healy, D. M.; Driscoll, J. R., Wavelet-encoded MR imaging, Magn. Reson. Med., 24, 275-287 (1992) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
