The quest for optimal sampling: computationally efficient, structure-exploiting measurements for compressed sensing. (English) Zbl 1333.94014
Boche, Holger (ed.) et al., Compressed sensing and its applications. MATHEON workshop, Berlin, Germany, December 2013. Cham: Birkhäuser/Springer (ISBN 978-3-319-16041-2/hbk; 978-3-319-16042-9/ebook). Applied and Numerical Harmonic Analysis, 143-167 (2015).
Summary: An intriguing phenomenon in many instances of compressed sensing is that the reconstruction quality is governed not just by the overall sparsity of the object to recover, but also on its structure. This chapter is about understanding this phenomenon, and demonstrating how it can be fruitfully exploited by the design of suitable sampling strategies in order to outperform more standard compressed sensing techniques based on random matrices.
For the entire collection see [Zbl 1320.94007].
For the entire collection see [Zbl 1320.94007].
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 94A20 | Sampling theory in information and communication theory |
Software:
SPGL1References:
| [1] | Adcock, B., Hansen, A.C.: Generalized sampling and infinite-dimensional compressed sensing. Technical report NA2011/02, DAMTP, University of Cambridge (2011) · Zbl 1379.94026 |
| [2] | Adcock, B., Hansen, A.C., Poon, C., Roman, B.: Breaking the coherence barrier: a new theory for compressed sensing. arXiv:1302.0561 (2014) · Zbl 1410.94030 |
| [3] | Adcock, B., Hansen, A.C., Roman, B.: A note on compressed sensing of structured sparse wavelet coefficients from subsampled Fourier measurements. arXiv:1403.6541 (2014) |
| [4] | Adcock, B.; Hansen, A. C.; Roman, B.; Teschke, G., Generalized sampling: stable reconstructions, inverse problems and compressed sensing over the continuum, Adv. Imaging Electron Phys., 182, 187-279 (2014) · doi:10.1016/B978-0-12-800146-2.00004-7 |
| [5] | Ailon,N., Liberty, E.: An almost optimal unrestricted fast Johnson-Lindenstrauss transform. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2011) · Zbl 1377.68259 |
| [6] | Baraniuk, R. G.; Cevher, V.; Duarte, M. F.; Hedge, C., Model-based compressive sensing, IEEE Trans. Inf. Theory, 56, 4, 1982-2001 (2010) · Zbl 1366.94215 · doi:10.1109/TIT.2010.2040894 |
| [7] | Bastounis, A., Hansen, A.C.: On the absence of the RIP in real-world applications of compressed sensing and the RIP in levels. arXiv:1411.4449 (2014) |
| [8] | Bigot, J., Boyer, C., Weiss, P.: An analysis of block sampling strategies in compressed sensing. arXiv:1305.4446 (2013) · Zbl 1359.94063 |
| [9] | Binev, P.; Dahmen, W.; DeVore, R. A.; Lamby, P.; Savu, D.; Sharpley, R.; Vogt, T.; Dahmen, W.; Binev, P., Compressed sensing and electron microscopy, Modeling Nanoscale Imaging in Electron Microscopy, Nanostructure Science and Technology, 73-126 (2012), New York: Springer, New York · doi:10.1007/978-1-4614-2191-7_4 |
| [10] | Bourrier, A., Davies, M.E., Peleg, T., Pérez, P., Gribonval, R.: Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems. arXiv:1311.6239 (2013) · Zbl 1359.94838 |
| [11] | Boyer, C.; Weiss, P.; Bigot, J., An algorithm for variable density sampling with block-constrained acquisition, SIAM J. Imag. Sci., 7, 2, 1080-1107 (2014) · Zbl 1343.94021 · doi:10.1137/130941560 |
| [12] | Candès, E.; Donoho, D. L., Recovering edges in ill-posed inverse problems: optimality of curvelet frames, Ann. Stat., 30, 3, 784-842 (2002) · Zbl 1101.62335 · doi:10.1214/aos/1028674842 |
| [13] | Candès, E. J.; Donoho, D. L., New tight frames of curvelets and optimal representations of objects with piecewise C^2 singularities, Commun. Pure Appl. Math., 57, 2, 219-266 (2004) · Zbl 1038.94502 · doi:10.1002/cpa.10116 |
| [14] | Candès, E. J.; Plan, Y., A probabilistic and RIPless theory of compressed sensing, IEEE Trans. Inf. Theory, 57, 11, 7235-7254 (2011) · Zbl 1365.94174 · doi:10.1109/TIT.2011.2161794 |
| [15] | Candès, E. J.; Romberg, J., Sparsity and incoherence in compressive sampling, Inverse Prob., 23, 3, 969-985 (2007) · Zbl 1120.94005 · doi:10.1088/0266-5611/23/3/008 |
| [16] | Carson, W. R.; Chen, M.; Rodrigues, M. R.D.; Calderbank, R.; Carin, L., Communications-inspired projection design with application to compressive sensing, SIAM J. Imag. Sci., 5, 4, 1185-1212 (2012) · Zbl 1260.94010 · doi:10.1137/120878380 |
| [17] | Chartrand, R.; Sidky, Y.; Pan, X., Nonconvex compressive sensing for X-ray CT: an algorithm comparison (2013), Asilomar Conference on Signals, Systems, and Computers: In, Asilomar Conference on Signals, Systems, and Computers |
| [18] | Crouse, M. S.; Nowak, R. D.; Baraniuk, R. G., Wavelet-based statistical signal processing using hidden Markov models, IEEE Trans. Signal Process., 46, 886-902 (1998) · doi:10.1109/78.668544 |
| [19] | 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 · doi:10.1016/j.acha.2009.02.004 |
| [20] | 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 Multiresolution Inf. Process., 6, 2, 157-181 (2008) · Zbl 1257.42047 · doi:10.1142/S021969130800229X |
| [21] | DeVore, R. A., Nonlinear approximation, Acta Numer., 7, 51-150 (1998) · Zbl 0931.65007 · doi:10.1017/S0962492900002816 |
| [22] | Do, M. N.; Vetterli, M., The contourlet transform: An efficient directional multiresolution image representation, IEEE Trans. Image Process., 14, 12, 2091-2106 (2005) · doi:10.1109/TIP.2005.859376 |
| [23] | Donoho, D. L., Compressed sensing, IEEE Trans. Inf. Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582 |
| [24] | Duarte, M. F.; Davenport, M. A.; Takhar, D.; Laska, J.; Kelly, K.; Baraniuk, R. G., Single-pixel imaging via compressive sampling, IEEE Signal Process. Mag., 25, 2, 83-91 (2008) · doi:10.1109/MSP.2007.914730 |
| [25] | Duarte, M. F.; Eldar, Y. C., Structured compressed sensing: from theory to applications, IEEE Trans. Signal Process., 59, 9, 4053-4085 (2011) · Zbl 1392.94188 · doi:10.1109/TSP.2011.2161982 |
| [26] | Eldar, Y. C., Robust recovery of signals from a structured union of subspaces, IEEE Trans. Inf. Theory, 55, 11, 5302-5316 (2009) · Zbl 1367.94087 · doi:10.1109/TIT.2009.2030471 |
| [27] | Foucart, S.; Rauhut, H., A Mathematical Introduction to Compressive Sensing (2013), New York: Birkhauser, New York · Zbl 1315.94002 · doi:10.1007/978-0-8176-4948-7 |
| [28] | Gan, L.; Do, T. T.; Tran, T. D., Fast compressive imaging using scrambled Hadamard ensemble (2008), EUSIPCO: Proc, EUSIPCO |
| [29] | Guerquin-Kern, M.; Häberlin, M.; Pruessmann, K. P.; Unser, M., A fast wavelet-based reconstruction method for magnetic resonance imaging, IEEE Trans. Med. Imaging, 30, 9, 1649-1660 (2011) · doi:10.1109/TMI.2011.2140121 |
| [30] | 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) · doi:10.1109/TMI.2011.2174158 |
| [31] | Haldar, J.; Hernando, D.; Liang, Z., Compressed-sensing MRI with random encoding, IEEE Trans. Med. Imaging, 30, 4, 893-903 (2011) · doi:10.1109/TMI.2010.2085084 |
| [32] | He, L.; Carin, L., Exploiting structure in wavelet-based Bayesian compressive sensing, IEEE Trans. Signal Process., 57, 9, 3488-3497 (2009) · Zbl 1391.94234 · doi:10.1109/TSP.2009.2022003 |
| [33] | He, L.; Chen, H.; Carin, L., Tree-structured compressive sensing with variational Bayesian analysis, IEEE Signal Process Lett., 17, 3, 233-236 (2010) · doi:10.1109/LSP.2009.2037532 |
| [34] | Herman, M.A.: Compressive sensing with partial-complete, multiscale Hadamard waveforms. In: Imaging and Applied Optics, p. CM4C.3. Optical Society of America (2013) https://www.osapublishing.org/viewmedia.cfm?uri=COSI-2013-CM4C.3&seq=0 |
| [35] | Herman, M. A.; Strohmer, T., High-resolution radar via compressed sensing, IEEE Trans. Signal Process., 57, 6, 2275-2284 (2009) · Zbl 1391.94236 · doi:10.1109/TSP.2009.2014277 |
| [36] | Hinrichs, A.; Vybiral, J., Johnson-Lindenstrauss lemma for circulant matrices, Random Struct. Algorithm, 39, 3, 391-398 (2011) · Zbl 1230.46019 |
| [37] | Huang, G., Jiang, H., Matthews, K., Wilford, P.: Lensless imaging by compressive sensing. arXiv:1305.7181 (2013) |
| [38] | Krahmer, F.; Ward, R., New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property, SIAM J. Math. Anal., 43, 3, 1269-1281 (2011) · Zbl 1247.15019 · doi:10.1137/100810447 |
| [39] | Krahmer, F.; Ward, R., Stable and robust recovery from variable density frequency samples, IEEE Trans. Image Proc., 23, 2, 612-622 (2014) · Zbl 1374.94181 · doi:10.1109/TIP.2013.2288004 |
| [40] | Kutyniok, G.; Lemvig, J.; Lim, W.-Q.; Neamtu, M.; Schumaker, L., Compactly supported shearlets, Approximation Theory XIII: San Antonio 2010. Springer Proceedings in Mathematics, 163-186 (2012), New York: Springer, New York · Zbl 1252.42042 · doi:10.1007/978-1-4614-0772-0_10 |
| [41] | Leary, R.; Saghi, Z.; Midgley, P. A.; Holland, D. J., Compressed sensing electron tomography, Ultramicroscopy, 131, 70-91 (2013) · doi:10.1016/j.ultramic.2013.03.019 |
| [42] | Liang, D., Xu, G., Wang, H., King, K.F., Xu, D., Ying, L.: Toeplitz random encoding MR imaging using compressed sensing. In: Proceedings/IEEE International Symposium on Biomedical Imaging., pp. 270-273, June 2009 |
| [43] | Lin, T.; Herrman, F. J., Compressed wavefield extrapolation, Geophysics, 72, 5, SM77-SM93 (2007) · doi:10.1190/1.2750716 |
| [44] | Lustig, M.; Donoho, D. L.; Pauly, J. M., Sparse MRI: the application of compressed sensing for rapid MRI imaging, Magn. Reson. Imaging, 58, 6, 1182-1195 (2007) |
| [45] | Lustig, M.; Donoho, D. L.; Santos, J. M.; Pauly, J. M., Compressed sensing MRI, IEEE Signal Process. Mag., 25, 2, 72-82 (2008) · doi:10.1109/MSP.2007.914728 |
| [46] | Mallat, S. G., A Wavelet Tour of Signal Processing: The Sparse Way (2009), London: Academic, London · Zbl 1170.94003 |
| [47] | Mishali, M.; Eldar, Y. C.; Elron, A. J., Xampling: Signal acquisition and processing in union of subspaces, IEEE Trans. Signal Process., 59, 10, 4719-4734 (2011) · Zbl 1392.94342 · doi:10.1109/TSP.2011.2161472 |
| [48] | Po, D. D.-Y.; Do, M. N., Directional multiscale modeling of images using the contourlet transform, IEEE Trans. Image Process., 15, 6, 1610-1620 (2006) · doi:10.1109/TIP.2006.873450 |
| [49] | Puy, G.; Marques, J. P.; Gruetter, R.; Thiran, J.; Van De Ville, D.; Vandergheynst, P.; Wiaux, Y., Spread spectrum magnetic resonance imaging, IEEE Trans. Med. Imaging, 31, 3, 586-598 (2012) · doi:10.1109/TMI.2011.2173698 |
| [50] | Roman, B., Adcock, B., Hansen, A.C.: On asymptotic structure in compressed sensing. arXiv:1406.4178 (2014) |
| [51] | Romberg, J., Imaging via compressive sampling, IEEE Signal Process. Mag., 25, 2, 14-20 (2008) · doi:10.1109/MSP.2007.914729 |
| [52] | Sebert, F.; Xou, Y. M.; Ying, L., Compressed sensing MRI with random B1 field, Proc. Int. Soc. Magn. Reson. Med., 16, 3151 (2008) |
| [53] | Som, S.; Schniter, P., Compressive imaging using approximate message passing and a markov-tree prior, IEEE Trans. Signal Process., 60, 7, 3439-3448 (2012) · Zbl 1393.94714 · doi:10.1109/TSP.2012.2191780 |
| [54] | Studer, V.; Bobin, J.; Chahid, M.; Moussavi, H.; Candès, E.; Dahan, M., Compressive fluorescence microscopy for biological and hyperspectral imaging, Natl. Acad. Sci. USA, 109, 26, 1679-1687 (2011) · doi:10.1073/pnas.1119511109 |
| [55] | Tsaig, Y.; Donoho, D. L., Extensions of compressed sensing, Signal Process., 86, 3, 549-571 (2006) · Zbl 1163.94399 · doi:10.1016/j.sigpro.2005.05.029 |
| [56] | van den Berg, E., Friedlander, M.P.: SPGL1: a solver for large-scale sparse reconstruction. http://www.cs.ubc.ca/labs/scl/spgl1 (2007) |
| [57] | van den Berg, E.; Friedlander, M. P., Probing the pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., 31, 2, 890-912 (2008) · Zbl 0077.23405 · doi:10.1137/080714488 |
| [58] | Wang, L., Carlson, D., Rodrigues, M.R.D., Wilcox, D., Calderbank, R., Carin, L.: Designed measurements for vector count data. Adv. Neural Inf. Process. Syst., pp. 1142-1150 (2013) |
| [59] | Wang, Z.; Arce, G. R., Variable density compressed image sampling, IEEE Trans. Image Process., 19, 1, 264-270 (2010) · Zbl 1371.94404 · doi:10.1109/TIP.2009.2032889 |
| [60] | Wiaux, Y.; Jacques, L.; Puy, G.; Scaife, A. M.M.; Vandergheynst, P., Compressed sensing imaging techniques for radio interferometry, Mon. Not. R. Astron. Soc., 395, 3, 1733-1742 (2009) · doi:10.1111/j.1365-2966.2009.14665.x |
| [61] | Wong, E.C.: Efficient randomly encoded data acquisition for compressed sensing. In: Proceedings on International Society for Magnetic Resonance in Medicine, p. 4893 (2010) |
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.
