Uniform recovery in infinite-dimensional compressed sensing and applications to structured binary sampling. (English) Zbl 1472.94020
Summary: Infinite-dimensional compressed sensing deals with the recovery of analog signals (functions) from linear measurements, often in the form of integral transforms such as the Fourier transform. This framework is well-suited to many real-world inverse problems, which are typically modeled in infinite-dimensional spaces, and where the application of finite-dimensional approaches can lead to noticeable artefacts. Another typical feature of such problems is that the signals are not only sparse in some dictionary, but possess a so-called local sparsity in levels structure. Consequently, the sampling scheme should be designed so as to exploit this additional structure. In this paper, we introduce a series of uniform recovery guarantees for infinite-dimensional compressed sensing based on sparsity in levels and so-called multilevel random subsampling. By using a weighted \(\ell^1\)-regularizer we derive measurement conditions that are sharp up to log factors, in the sense that they agree with the best known measurement conditions for oracle estimators in which the support is known a priori. These guarantees also apply in finite dimensions, and improve existing results for unweighted \(\ell^1\)-regularization. To illustrate our results, we consider the problem of binary sampling with the Walsh transform using orthogonal wavelets. Binary sampling is an important mechanism for certain imaging modalities. Through carefully estimating the local coherence between the Walsh and wavelet bases, we derive the first known recovery guarantees for this problem.
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 94A20 | Sampling theory in information and communication theory |
| 42C40 | Nontrigonometric harmonic analysis involving wavelets and other special systems |
| 42C10 | Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.) |
| 15B52 | Random matrices (algebraic aspects) |
| 42B10 | Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type |
Keywords:
infinite-dimensional compressed sensing; uniform recovery; Walsh sampling; wavelet recovery; sparsity in levels; local coherenceSoftware:
MRI Simulation and ReconstructionReferences:
| [1] | Candès, E. J.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 2, 489-509 (2006) · Zbl 1231.94017 |
| [2] | Donoho, D. L., Compressed sensing, IEEE Trans. Inf. Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016 |
| [3] | Eldar, Y. C.; Kutyniok, G., Compressed Sensing: Theory and Applications (2012), Cambridge University Press |
| [4] | Foucart, S.; Rauhut, H., A Mathematical Introduction to Compressive Sensing (2013), Springer - Birkhäuser · Zbl 1315.94002 |
| [5] | Larson, P. E.; Hu, S.; Lustig, M.; Kerr, A. B.; Nelson, S. J.; Kurhanewicz, J.; Pauly, J. M.; Vigneron, D. B., Fast dynamic 3D MR spectroscopic imaging with compressed sensing and multiband excitation pulses for hyperpolarized 13C studies, Magn. Reson. Med., 65, 3, 610-619 (2011) |
| [6] | Lustig, M.; Donoho, D.; Pauly, J. M., Sparse MRI: the application of compressed sensing for rapid MR imaging, Magn. Reson. Med., 58, 6, 1182-1195 (2007) |
| [7] | Lustig, M.; Donoho, D. L.; Santos, J. M.; Pauly, J. M., Compressed sensing MRI, IEEE Signal Process. Mag., 25, 2, 72-82 (2008) |
| [8] | Jones, A.; Tamtögl, A.; Calvo-Almazán, I.; Hansen, A., Continuous compressed sensing for surface dynamical processes with helium atom scattering, Sci. Rep., 6, Article 27776 pp. (2016) |
| [9] | Studer, V.; Bobin, J.; Chahid, M.; Mousavi, H. S.; Candés, E.; Dahan, M., Compressive fluorescence microscopy for biological and hyperspectral imaging, Proc. Natl. Acad. Sci., 109, 26, E1679-E1687 (2012) |
| [10] | Zomet, A.; Nayar, S. K., Lensless imaging with a controllable aperture, (Computer Society Conference on Computer Vision and Pattern Recognition, vol. 1 (2006), IEEE), 339-346 |
| [11] | Arce, G. R.; Brady, D. J.; Carin, L.; Arguello, H.; Kittle, D. S., Compressive coded aperture spectral imaging: an introduction, IEEE Signal Process. Mag., 31, 1, 105-115 (2014) |
| [12] | Gehm, M. E.; Brady, D. J., Compressive sensing in the EO/IR, Appl. Opt., 54, 8, C14-C22 (2015) |
| [13] | Willett, R. M.; Marcia, R. F.; Nichols, J. M., Compressed sensing for practical optical imaging systems: a tutorial, Opt. Eng., 50, 7 (2011) |
| [14] | Adcock, B.; Hansen, A. C.; Poon, C.; Roman, B., Breaking the coherence barrier: a new theory for compressed sensing, Forum Math. Sigma, 5 (2017) · Zbl 1410.94030 |
| [15] | Roman, B.; Hansen, A. C.; Adcock, B., On asymptotic structure in compressed sensing (2014) |
| [16] | Bastounis, A.; Hansen, A. C., On the absence of uniform recovery in many real-world applications of compressed sensing and the restricted isometry property and nullspace property in levels, SIAM J. Imaging Sci., 10, 1, 335-371 (2017) · Zbl 1375.94017 |
| [17] | Li, C.; Adcock, B., Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class, Appl. Comput. Harmon. Anal., 46, 3, 453-477 (2019) · Zbl 1415.94162 |
| [18] | Chi, Y.; Scharf, L. L.; Pezeshki, A.; Calderbank, A. R., Sensitivity to basis mismatch in compressed sensing, IEEE Trans. Signal Process., 59, 5, 2182-2195 (2011) · Zbl 1392.94144 |
| [19] | Strang, G.; Nguyen, T., Wavelets and Filter Banks (1996), Wellesley-Cambridge Press · Zbl 1254.94002 |
| [20] | Guerquin-Kern, M.; Lejeune, L.; Pruessmann, K. P.; Unser, M., Realistic analytical phantoms for parallel magnetic resonance imaging, IEEE Trans. Med. Imaging, 31, 3, 626-636 (2012) |
| [21] | Adcock, B.; Boyer, C.; Brugiapaglia, S., On oracle-type local recovery guarantees in compressed sensing, Inf. Inference, 1-49 (2020) · Zbl 1470.94031 |
| [22] | Traonmilin, Y.; Gribonval, R., Stable recovery of low-dimensional cones in Hilbert spaces: one RIP to rule them all, Appl. Comput. Harmon. Anal., 45, 1, 170-205 (2018) · Zbl 1391.94421 |
| [23] | Candès, E. J.; Tao, T., Near-optimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inf. Theory, 52, 12, 5406-5425 (2006) · Zbl 1309.94033 |
| [24] | Candès, E. J.; Tao, T., Decoding by linear programming, IEEE Trans. Inf. Theory, 51, 12, 4203-4215 (2005) · Zbl 1264.94121 |
| [25] | Cai, T. T.; Wang, L.; Xu, G., Shifting inequality and recovery of sparse signals, IEEE Trans. Signal Process., 58, 3, 1300-1308 (2010) · Zbl 1392.94117 |
| [26] | Cai, T. T.; Wang, L.; Xu, G., New bounds for restricted isometry constants, IEEE Trans. Inf. Theory, 56, 9, 4388-4394 (2010) · Zbl 1366.94181 |
| [27] | Andersson, J.; Strömberg, J., On the theorem of uniform recovery of random sampling matrices, IEEE Trans. Inf. Theory, 60, 3, 1700-1710 (2014) · Zbl 1360.94181 |
| [28] | Rudelson, M.; Vershynin, R., On sparse reconstruction from Fourier and Gaussian measurements, Commun. Pure Appl. Math., 61, 8, 1025-1045 (2008) · Zbl 1149.94010 |
| [29] | Adcock, B.; Hansen, A. C.; Roman, B., A note on compressed sensing of structured sparse wavelet coefficients from subsampled Fourier measurements, IEEE Signal Process. Lett., 23, 5, 732-736 (2016) |
| [30] | Adcock, B.; Hansen, A. C., Generalized sampling and infinite-dimensional compressed sensing, Found. Comput. Math., 16, 5, 1263-1323 (2016) · Zbl 1379.94026 |
| [31] | Brugiapaglia, S.; Adcock, B., Robustness to unknown error in sparse regularization, IEEE Trans. Inf. Theory, 64, 10, 6638-6661 (2018) · Zbl 1401.94027 |
| [32] | Beauchamp, K. G., Walsh Functions and Their Applications, vol. 3 (1975), Academic Press · Zbl 0326.42007 |
| [33] | Golubov, B.; Efimov, A.; Skvortsov, V., Walsh Series and Transforms: Theory and Applications, vol. 64 (1991), Springer Science & Business Media · Zbl 0785.42010 |
| [34] | Daubechies, I., Ten Lectures on Wavelets, Vol. 61 (1992), SIAM · Zbl 0776.42018 |
| [35] | Mallat, S., A Wavelet Tour of Signal Processing: The Sparse Way (2008), Academic Press |
| [36] | Cohen, A.; Daubechies, I.; Vial, P., Wavelets on the interval and fast wavelet transforms, Appl. Comput. Harmon. Anal., 1, 1, 54-81 (1993) · Zbl 0795.42018 |
| [37] | Hansen, A.; Thesing, L., On the stable sampling rate for binary measurements and wavelet reconstruction, Appl. Comput. Harmon. Anal., 48, 2, 630-654 (2020) · Zbl 1454.94032 |
| [38] | Antun, V., Coherence estimates between Hadamard matrices and Daubechies wavelets (2016), University of Oslo, Master’s thesis |
| [39] | Thesing, L.; Hansen, A. C., Linear reconstructions and the analysis of the stable sampling rate, Sampl. Theory Signal Image Process., 17, 1, 103-126 (2018) · Zbl 1411.94036 |
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.
