Breaking the coherence barrier: a new theory for compressed sensing. (English) Zbl 1410.94030

Adcock, Ben; Hansen, Anders C.; Poon, Clarice; Roman, Bogdan

Forum Math. Sigma 5, Paper No. e4, 84 p. (2017).

Summary: This paper presents a framework for compressed sensing that bridges a gap between existing theory and the current use of compressed sensing in many real-world applications. In doing so, it also introduces a new sampling method that yields substantially improved recovery over existing techniques. In many applications of compressed sensing, including medical imaging, the standard principles of incoherence and sparsity are lacking. Whilst compressed sensing is often used successfully in such applications, it is done largely without mathematical explanation. The framework introduced in this paper provides such a justification. It does so by replacing these standard principles with three more general concepts: asymptotic sparsity, asymptotic incoherence and multilevel random subsampling. Moreover, not only does this work provide such a theoretical justification, it explains several key phenomena witnessed in practice. In particular, and unlike the standard theory, this work demonstrates the dependence of optimal sampling strategies on both the incoherence structure of the sampling operator and on the structure of the signal to be recovered. Another key consequence of this framework is the introduction of a new structured sampling method that exploits these phenomena to achieve significant improvements over current state-of-the-art techniques.

MSC:

94A20	Sampling theory in information and communication theory
94A08	Image processing (compression, reconstruction, etc.) in information and communication theory
42C40	Nontrigonometric harmonic analysis involving wavelets and other special systems
65R32	Numerical methods for inverse problems for integral equations
92C55	Biomedical imaging and signal processing

Software:

MRI Simulation and Reconstruction

References:

[1]	Adcock, B. and Hansen, A. C., ‘A generalized sampling theorem for stable reconstructions in arbitrary bases’, J. Fourier Anal. Appl.18(4) (2012), 685-716. doi:10.1007/s00041-012-9221-x · Zbl 1259.94035
[2]	Adcock, B. and Hansen, A. C., ‘Stable reconstructions in Hilbert spaces and the resolution of the Gibbs phenomenon’, Appl. Comput. Harmon. Anal.32(3) (2012), 357-388. doi:10.1016/j.acha.2011.07.004 · Zbl 1245.94058
[3]	Adcock, B. and Hansen, A. C., ‘Generalized sampling and infinite-dimensional compressed sensing’, Found. Comput. Math.16(5) (2016), 1263-1323. doi:10.1007/s10208-015-9276-6 · Zbl 1379.94026
[4]	Adcock, B., Hansen, A. C., Herrholz, E. and Teschke, G., ‘Generalized sampling: extension to frames and inverse and ill-posed problems’, Inverse Problems29(1) (2013), 015008. doi:10.1088/0266-5611/29/1/015008 · Zbl 1321.42048
[5]	Adcock, B., Hansen, A. C. and Poon, C., ‘Beyond consistent reconstructions: optimality and sharp bounds for generalized sampling, and application to the uniform resampling problem’, SIAM J. Math. Anal.45(5) (2013), 3114-3131. doi:10.1137/120895846 · Zbl 1320.94035
[6]	Adcock, B., Hansen, A. C. and Poon, C., ‘On optimal wavelet reconstructions from Fourier samples: linearity and universality of the stable sampling rate’, Appl. Comput. Harmon. Anal.36(3) (2014), 387-415. doi:10.1016/j.acha.2013.07.001 · Zbl 1293.42037
[7]	Adcock, B., Hansen, A. C., Roman, B. and Teschke, G., ‘Generalized sampling: stable reconstructions, inverse problems and compressed sensing over the continuum’, Adv. Imaging Electron Phys.182 (2014), 187-279. doi:10.1016/B978-0-12-800146-2.00004-7
[8]	Baraniuk, R. G., Cevher, V., Duarte, M. F. and Hedge, C., ‘Model-based compressive sensing’, IEEE Trans. Inform. Theory56(4) (2010), 1982-2001. doi:10.1109/TIT.2010.2040894 · Zbl 1366.94215
[9]	Bastounis, A. and Hansen, A. C., ‘On the absence of uniform recovery in many real-world applications of compressed sensing and the RIP & nullspace property in levels’, SIAM J. Imaging Sci. (to appear). · Zbl 1375.94017
[10]	Bigot, J., Boyer, C. and Weiss, P., ‘An analysis of block sampling strategies in compressed sensing’, IEEE Trans. Inform. Theory62(4) (2016), 2125-2139. doi:10.1109/TIT.2016.2524628 · Zbl 1359.94063
[11]	Bourrier, A., Davies, M. E., Peleg, T., Pérez, P. and Gribonval, R., ‘Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems’, IEEE Trans. Inform. Theory60(12) (2014), 7928-7946. doi:10.1109/TIT.2014.2364403 · Zbl 1359.94838
[12]	Boyer, C., Bigot, J. and Weiss, P., ‘Compressed sensing with structured sparsity and structured acquisition’, Preprint, 2015, arXiv:1505.01619. · Zbl 1454.94010
[13]	Candès, E. and Donoho, D. L., ‘Recovering edges in ill-posed inverse problems: optimality of curvelet frames’, Ann. Statist.30(3) (2002), 784-842. doi:10.1214/aos/1028674842 · Zbl 1101.62335
[14]	Candès, E. J., An introduction to compressive sensing, IEEE Signal Process. Mag., 25, 2, 21-30, (2008)
[15]	Candès, E. J. and Donoho, D., ‘New tight frames of curvelets and optimal representations of objects with piecewise C2 singularities’, Comm. Pure Appl. Math.57(2) (2004), 219-266. doi:10.1002/cpa.10116 · Zbl 1038.94502
[16]	Candès, E. J. and Plan, Y., ‘A probabilistic and RIPless theory of compressed sensing’, IEEE Trans. Inform. Theory57(11) (2011), 7235-7254. doi:10.1109/TIT.2011.2161794 · Zbl 1365.94174
[17]	Candès, E. J. and Romberg, J., ‘Sparsity and incoherence in compressive sampling’, Inverse Problems23(3) (2007), 969-985. doi:10.1088/0266-5611/23/3/008 · Zbl 1120.94005
[18]	Candès, E. J., Romberg, J. and Tao, T., ‘Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information’, IEEE Trans. Inform. Theory52(2) (2006), 489-509. doi:10.1109/TIT.2005.862083 · Zbl 1231.94017
[19]	Carson, W. R., Chen, M., Rodrigues, M. R. D., Calderbank, R. and Carin, L., ‘Communications-inspired projection design with application to compressive sensing’, SIAM J. Imaging Sci.5(4) (2012), 1185-1212. doi:10.1137/120878380 · Zbl 1260.94010
[20]	Chauffert, N., Ciuciu, P., Kahn, J. and Weiss, P., ‘Variable density sampling with continuous trajectories’, SIAM J. Imaging Sci.7(4) (2014), 1962-1992. doi:10.1137/130946642 · Zbl 1308.94047
[21]	Chauffert, N., Weiss, P., Kahn, J. and Ciuciu, P., ‘Gradient waveform design for variable density sampling in magnetic resonance imaging’, Preprint, 2014, arXiv:1412.4621. · Zbl 1308.94047
[22]	Chi, Y., Scharf, L. L., Pezeshki, A. and Calderbank, R., ‘Sensitivity to basis mismatch in compressed sensing’, IEEE Trans. Signal Process.59(5) (2011), 2182-2195. doi:10.1109/TSP.2011.2112650 · Zbl 1392.94144
[23]	Cohen, A., Dahmen, W. and Devore, R., ‘Compressed sensing and best k-term approximation’, J. Amer. Math. Soc.22(1) (2009), 211-231. doi:10.1090/S0894-0347-08-00610-3 · Zbl 1206.94008
[24]	Cormen, T. H., Stein, C., Rivest, R. L. and Leiserson, C. E., Introduction to Algorithms, 2nd edn (MIT Press, Cambridge, MA; McGraw-Hill Book Co., Boston, MA, 2001). · Zbl 1047.68161
[25]	Dahlke, S., Kutyniok, G., Maass, P., Sagiv, C., Stark, H.-G. and Teschke, G., ‘The uncertainty principle associated with the continuous shearlet transform’, Int. J. Wavelets Multiresolut. Inf. Process.6(2) (2008), 157-181. doi:10.1142/S021969130800229X · Zbl 1257.42047
[26]	Dahlke, S., Kutyniok, G., Steidl, G. and Teschke, G., ‘Shearlet coorbit spaces and associated Banach frames’, Appl. Comput. Harmon. Anal.27(2) (2009), 195-214. doi:10.1016/j.acha.2009.02.004 · Zbl 1171.42019
[27]	Daubechies, I., Orthonormal bases of compactly supported wavelets, Comm. Pure Appl. Math., 41, 7, 909-996, (1988) · Zbl 0644.42026
[28]	Daubechies, I., Ten Lectures on Wavelets, (1992), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 0776.42018
[29]	Davenport, M. A., Duarte, M. F., Eldar, Y. C. and Kutyniok, G., ‘Introduction to compressed sensing’, inCompressed Sensing: Theory and Applications (Cambridge University Press, Cambridge, 2011).
[30]	Devore, R. A., Nonlinear approximation, Acta Numer., 7, 51-150, (1998) · Zbl 0931.65007
[31]	Do, M. N. and Vetterli, M., ‘The contourlet transform: an efficient directional multiresolution image representation’, IEEE Trans. Image Process.14(12) (2005), 2091-2106. doi:10.1109/TIP.2005.859376
[32]	Donoho, D. L., Compressed sensing, IEEE Trans. Inform. Theory, 52, 4, 1289-1306, (2006) · Zbl 1288.94016
[33]	Donoho, D. L. and Huo, X., ‘Uncertainty principles and ideal atomic decomposition’, IEEE Trans. Inform. Theory47 (2001), 2845-2862. doi:10.1109/18.959265 · Zbl 1019.94503
[34]	Donoho, D. L. and Kutyniok, G., ‘Microlocal analysis of the geometric separation problem’, Comm. Pure Appl. Math.66(1) (2013), 1-47. doi:10.1002/cpa.21418 · Zbl 1261.94007
[35]	Donoho, D. L. and Tanner, J., ‘Neighborliness of randomly-projected simplices in high dimensions’, Proc. Natl Acad. Sci. USA102(27) (2005), 9452-9457. doi:10.1073/pnas.0502258102 · Zbl 1135.60300
[36]	Donoho, D. L. and Tanner, J., ‘Counting faces of randomly-projected polytopes when the projection radically lowers dimension’, J. Amer. Math. Soc.22(1) (2009), 1-53. doi:10.1090/S0894-0347-08-00600-0 · Zbl 1206.52010
[37]	Duarte, M. F., Davenport, M. A., Takhar, D., Laska, J., Kelly, K. and Baraniuk, R. G., ‘Single-pixel imaging via compressive sampling’, IEEE Signal Process. Mag.25(2) (2008), 83-91. doi:10.1109/MSP.2007.914730
[38]	Duarte, M. F. and Eldar, Y. C., ‘Structured compressed sensing: from theory to applications’, IEEE Trans. Signal Process.59(9) (2011), 4053-4085. doi:10.1109/TSP.2011.2161982 · Zbl 1392.94188
[39]	Eldar, Y. C. and Kutyniok, G. (Eds.), Compressed Sensing: Theory and Applications (Cambridge University Press, Cambridge, 2012). doi:10.1017/CBO9780511794308
[40]	Fornasier, M. and Rauhut, H., ‘Compressive sensing’, inHandbook of Mathematical Methods in Imaging (Springer, New York, NY, 2011), 187-228. doi:10.1007/978-0-387-92920-0_6 · Zbl 1259.94017
[41]	Foucart, S. and Rauhut, H., A Mathematical Introduction to Compressive Sensing (Birkhäuser/Springer, New York, NY, 2013). doi:10.1007/978-0-8176-4948-7 · Zbl 1315.94002
[42]	Gröchenig, K., Rzeszotnik, Z. and Strohmer, T., ‘Convergence analysis of the finite section method and banach algebras of matrices’, Integr. Equat. Oper. Th.67(2) (2010), 183-202. doi:10.1007/s00020-010-1775-x · Zbl 1197.65053
[43]	Gross, D., Recovering low-rank matrices from few coefficients in any basis, IEEE Trans. Inform. Theory, 57, 3, 1548-1566, (2011) · Zbl 1366.94103
[44]	Gross, D., Krahmer, F. and Kueng, R., ‘A partial derandomization of phaselift using spherical designs’, J. Fourier Anal. Appl.21(2) (2015), 229-266. doi:10.1007/s00041-014-9361-2 · Zbl 1332.90197
[45]	Guerquin-Kern, M., Häberlin, M., Pruessmann, K. and Unser, M., ‘A fast wavelet-based reconstruction method for magnetic resonance imaging’, IEEE Transactions on Medical Imaging30(9) (2011), 1649-1660. doi:10.1109/TMI.2011.2140121
[46]	Guerquin-Kern, M., Lejeune, L., Pruessmann, K. P. and Unser, M., ‘Realistic analytical phantoms for parallel Magnetic Resonance Imaging’, IEEE Trans. Med. Imaging31(3) (2012), 626-636. doi:10.1109/TMI.2011.2174158
[47]	Hansen, A. C., On the approximation of spectra of linear operators on hilbert spaces, J. Funct. Anal., 254, 8, 2092-2126, (2008) · Zbl 1138.47002
[48]	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
[49]	Herman, M. A., ‘Compressive sensing with partial-complete, multiscale Hadamard waveforms’, inImaging and Applied Optics (Optical Society of America, Arlington, VA, 2013), CM4C.3.
[50]	Herman, M. A., Weston, T., Mcmackin, L., Li, Y., Chen, J. and Kelly, K. F., ‘Recent results in single-pixel compressive imaging using selective measurement strategies’, inProc. SPIE 9484, Compressive Sensing IV94840A (SPIE, Baltimore, MD, 2015).
[51]	Hernández, E. and Weiss, G., A First Course on Wavelets, (CRC Press, Boca Raton, FL, 1996). doi:10.1201/9781420049985 · Zbl 0885.42018
[52]	Hrycak, T. and Gröchenig, K., ‘Pseudospectral Fourier reconstruction with the modified inverse polynomial reconstruction method’, J. Comput. Phys.229(3) (2010), 933-946. doi:10.1016/j.jcp.2009.10.026 · Zbl 1184.65123
[53]	Jones, A., Tamtögl, A., Calvo-Almazán, I. and Hansen, A., ‘Continuous compressed sensing for surface dynamical processes with helium atom scattering’, Sci. Rep.6 (2016), 27776 EP -, 06.
[54]	Jones, A. D., Adcock, B. and Hansen, A. C., ‘On asymptotic incoherence and its implications for compressed sensing of inverse problems’, IEEE Trans. Inform. Theory62(2) (2016), 1020-1037. doi:10.1109/TIT.2015.2508562 · Zbl 1359.94107
[55]	Krahmer, F. and Ward, R., ‘Stable and robust sampling strategies for compressive imaging’, IEEE Trans. Image Process.23(2) (2014), 612-622. doi:10.1109/TIP.2013.2288004 · Zbl 1374.94181
[56]	Kutyniok, G., Lemvig, J. and Lim, W.-Q., ‘Compactly supported shearlets’, inApproximation Theory XIII: San Antonio 2010, (eds. Neamtu, M. and Schumaker, L.) , 13 (Springer, New York, 2012), 163-186. doi:10.1007/978-1-4614-0772-0_10 · Zbl 1252.42042
[57]	Kutyniok, G. and Lim, W.-Q., ‘Optimal compressive imaging of Fourier data’, Preprint, 2015, arXiv:1510.05029. · Zbl 1437.94043
[58]	Larson, P. E. Z., Hu, S., Lustig, M., Kerr, A. B., Nelson, S. J., Kurhanewicz, J., Pauly, J. M. and 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) (2011), 610-619. doi:10.1002/mrm.22650
[59]	Ledoux, M., The Concentration of Measure Phenomenon, 89, (2001), American Mathematical Society: American Mathematical Society, Providence, RI · Zbl 0995.60002
[60]	Li, C. and Adcock, B., ‘Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class’, Preprint, 2016, arXiv:1601.01988. · Zbl 1415.94162
[61]	Lustig, M., ‘Sparse MRI’, PhD Thesis, Stanford University, 2008.
[62]	Lustig, M., Donoho, D. L. and Pauly, J. M., ‘Sparse MRI: the application of compressed sensing for rapid MRI imaging’, Magn. Reson. Imaging58(6) (2007), 1182-1195.
[63]	Lustig, M., Donoho, D. L., Santos, J. M. and Pauly, J. M., ‘Compressed Sensing MRI’, IEEE Signal Process. Mag.25(2) (2008), 72-82. doi:10.1109/MSP.2007.914728
[64]	Mallat, S. G., A Wavelet Tour of Signal Processing: The Sparse Way, (2009), Elsevier/Academic Press: Elsevier/Academic Press, Amsterdam · Zbl 1170.94003
[65]	Mcdiarmid, C., ‘Concentration’, inProbabilistic Methods for Algorithmic Discrete Mathematics, , 16 (Springer, Berlin, 1998), 195-248. doi:10.1007/978-3-662-12788-9_6 · Zbl 0927.60027
[66]	Po, D. D.-Y. and Do, M. N., ‘Directional multiscale modeling of images using the contourlet transform’, IEEE Trans. Image Process.15(6) (2006), 1610-1620. doi:10.1109/TIP.2006.873450
[67]	Poon, C., A consistent, and stable approach to generalized sampling, J. Fourier Anal. Appl., 20, 5, 985-1019, (2014) · Zbl 1320.94037
[68]	Poon, C., On the role of total variation in compressed sensing, SIAM J. Imaging Sci., 8, 1, 682-720, (2015) · Zbl 1381.94038
[69]	Poon, C., ‘Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames’, Appl. Comput. Harmon. Anal. (2015), (to appear). · Zbl 1422.94021
[70]	Puy, G., Marques, J. P., Gruetter, R., Thiran, J., Van De Ville, D., Vandergheynst, P. and Wiaux, Y., ‘Spread spectrum Magnetic Resonance Imaging’, IEEE Trans. Med. Imaging31(3) (2012), 586-598. doi:10.1109/TMI.2011.2173698
[71]	Puy, G., Vandergheynst, P. and Wiaux, Y., ‘On variable density compressive sampling’, IEEE Signal Process. Letters18 (2011), 595-598. doi:10.1109/LSP.2011.2163712
[72]	Rauhut, H. and Ward, R., ‘Interpolation via weighted ℓ1 minimization’, Appl. Comput. Harmon. Anal.40(2) (2016), 321-351. doi:10.1016/j.acha.2015.02.003 · Zbl 1333.41003
[73]	Roman, B., Adcock, B. and Hansen, A. C., ‘On asymptotic structure in compressed sensing’, Preprint, 2014, arXiv:1406.4178.
[74]	Romberg, J., Imaging via compressive sampling, IEEE Signal Process. Mag., 25, 2, 14-20, (2008)
[75]	Rudelson, M., Random vectors in the isotropic position, J. Funct. Anal., 164, 1, 60-72, (1999) · Zbl 0929.46021
[76]	Strohmer, T., Measure what should be measured: progress and challenges in compressive sensing, IEEE Signal Process. Letters, 19, 12, 887-893, (2012)
[77]	Studer, V., Bobin, J., Chahid, M., Mousavi, H. S., Candès, E. and Dahan, M., ‘Compressive fluorescence microscopy for biological and hyperspectral imaging’, Proc. Natl. Acad. Sci. USA109(26) (2012), E1679-E1687. doi:10.1073/pnas.1119511109
[78]	Takhar, D., Laska, J. N., Wakin, M. B., Duarte, M. F., Baron, D., Sarvotham, S., Kelly, K. F. and Baraniuk, R. G., ‘A new compressive imaging camera architecture using optical-domain compression’, inProc. of Computational Imaging IV at SPIE Electronic Imaging (2006), 43-52.
[79]	Talagrand, M., New concentration inequalities in product spaces, Invent. Math., 126, 3, 505-563, (1996) · Zbl 0893.60001
[80]	Traonmilin, Y. and Gribonval, R., ‘Stable recovery of low-dimensional cones in Hilbert spaces: one RIP to rule them all’, Appl. Comput. Harmon. Anal. (2016), (to appear). · Zbl 1391.94421
[81]	Tropp, J. A., On the conditioning of random subdictionaries, Appl. Comput. Harmon. Anal., 25, 1, 1-24, (2008) · Zbl 1143.15026
[82]	Tsaig, Y. and Donoho, D. L., ‘Extensions of compressed sensing’, Signal Process.86(3) (2006), 549-571. doi:10.1016/j.sigpro.2005.05.029 · Zbl 1163.94399
[83]	Wang, L., Carlson, D., Rodrigues, M. R. D., Wilcox, D., Calderbank, R. and Carin, L., ‘Designed measurements for vector count data’, inAdvances in Neural Information Processing Systems (2013), 1142-1150.
[84]	Wang, Q., Zenge, M., Cetingul, H. E., Mueller, E. and Nadar, M. S., ‘Novel sampling strategies for sparse mr image reconstruction’, Proc. Int. Soc. Mag. Res. in Med. (22) (2014).
[85]	Wang, Z. and Arce, G. R., ‘Variable density compressed image sampling’, IEEE Trans. Image Process.19(1) (2010), 264-270. doi:10.1109/TIP.2009.2032889 · Zbl 1371.94404
[86]	Zomet, A. and Nayar, S. K., ‘Lensless imaging with a controllable aperture’, in2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (IEEE, 2006), 339-346.