Compressed sensing with structured sparsity and structured acquisition. (English) Zbl 1454.94010

Boyer, Claire; Bigot, Jérémie; Weiss, Pierre

Appl. Comput. Harmon. Anal. 46, No. 2, 312-350 (2019).

Summary: Compressed Sensing (CS) is an appealing framework for applications such as Magnetic Resonance Imaging (MRI). However, up-to-date, the sensing schemes suggested by CS theories are made of random isolated measurements, which are usually incompatible with the physics of acquisition. To reflect the physical constraints of the imaging device, we introduce the notion of blocks of measurements: the sensing scheme is not a set of isolated measurements anymore, but a set of groups of measurements which may represent any arbitrary shape (parallel or radial lines for instance). Structured acquisition with blocks of measurements are easy to implement, and provide good reconstruction results in practice. However, very few results exist on the theoretical guarantees of CS reconstructions in this setting. In this paper, we derive new CS results for structured acquisitions and signals satisfying a prior structured sparsity. The obtained results provide a recovery probability of sparse vectors that explicitly depends on their support. Our results are thus support-dependent and offer the possibility for flexible assumptions on the sparsity structure. Moreover, the results are drawing-dependent, since we highlight an explicit dependency between the probability of reconstructing a sparse vector and the way of choosing the blocks of measurements. Numerical simulations show that the proposed theory is faithful to experimental observations.

MSC:

94A08	Image processing (compression, reconstruction, etc.) in information and communication theory
62H12	Estimation in multivariate analysis
90C90	Applications of mathematical programming

Keywords:

compressed sensing; blocks of measurements; structured sparsity; MRI; exact recovery; \(\ell_1\) minimization

References:

[1]	Adcock, Ben; Hansen, Anders C., Generalized sampling and infinite-dimensional compressed sensing, Found. Comput. Math., 1-61, (2015) · Zbl 1379.94026
[2]	Adcock, Ben; Hansen, Anders C.; Poon, Clarice; Roman, Bogdan, Breaking the coherence barrier: a new theory for compressed sensing, (2013), arXiv preprint · Zbl 1410.94030
[3]	Adcock, Ben; Hansen, Anders C.; Roman, Bogdan, A note on compressed sensing of structured sparse wavelet coefficients from subsampled Fourier measurements, (2014), arXiv preprint
[4]	Adcock, Ben; Hansen, Anders C.; Roman, Bogdan, The quest for optimal sampling: computationally efficient, structure-exploiting measurements for compressed sensing, (Compressed Sensing and Its Applications, (2015), Springer International Publishing: Springer International Publishing Cham), 143-167, Book Chapter · Zbl 1333.94014
[5]	Bigot, Jérémie; Boyer, Claire; Weiss, Pierre, An analysis of blocks sampling strategies in compressed sensing, (2014), arXiv preprint · Zbl 1343.94021
[6]	Baraniuk, Richard G.; Cevher, Volkan; Duarte, Marco F.; Hegde, Chinmay, Model-based compressive sensing, IEEE Trans. Inform. Theory, 56, 4, 1982-2001, (2010) · Zbl 1366.94215
[7]	Bastounis, Alexander; Hansen, Anders C., On the absence of the rip in real-world applications of compressed sensing and the rip in levels, (2014), arXiv preprint · Zbl 1375.94017
[8]	Bach, Francis; Jenatton, Rodolphe; Mairal, Julien; Obozinski, Guillaume, Optimization with sparsity-inducing penalties, Found. Trends Mach. Learn., 4, 1, 1-106, (2012) · Zbl 06064248
[9]	Chauffert, Nicolas; Ciuciu, Philippe; Kahn, Jonas; Weiss, Pierre, Variable density sampling with continuous sampling trajectories, SIAM J. Imaging Sci., 7, 4, 1962-1992, (2014) · Zbl 1308.94047
[10]	Chauffert, N.; Ciuciu, P.; Weiss, P., Variable density compressed sensing in MRI. Theoretical vs heuristic sampling strategies, (Proceedings of IEEE ISBI, (2013))
[11]	Candès, Emmanuel; Plan, Yaniv, A probabilistic and ripless theory of compressed sensing, IEEE Trans. Inform. Theory, 57, 11, 7235-7254, (2011) · Zbl 1365.94174
[12]	Candès, Emmanuel; Romberg, Justin; Tao, Terence, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52, 2, 489-509, (2006) · Zbl 1231.94017
[13]	Candès, Emmanuel; Romberg, Justin; Tao, Terence, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math., 59, 8, 1207-1223, (2006) · Zbl 1098.94009
[14]	Candès, Emmanuel; Tao, Terence, Near-optimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inform. Theory, 52, 12, 5406-5425, (2006) · Zbl 1309.94033
[15]	Chauffert, Nicolas; Weiss, Pierre; Kahn, Jonas; Ciuciu, Philippe, Gradient waveform design for variable density sampling in magnetic resonance imaging, IEEE Trans. Med. Imag., 35, 9, 2026-2039, (2016) · Zbl 1439.94003
[16]	Duarte, Marco F.; Eldar, Yonina C., Structured compressed sensing: from theory to applications, IEEE Trans. Signal Process., 59, 9, 4053-4085, (2011) · Zbl 1392.94188
[17]	Donoho, David, Compressed sensing, IEEE Trans. Inform. Theory, 52, 4, 1289-1306, (2006) · Zbl 1288.94016
[18]	Eldar, Yonina C.; Mishali, Moshe, Robust recovery of signals from a structured union of subspaces, IEEE Trans. Inform. Theory, 55, 11, 5302-5316, (2009) · Zbl 1367.94087
[19]	Feller, Willliam, An Introduction to Probability Theory and Its Applications, vol. 2, (2008), John Wiley & Sons
[20]	Foucart, Simon; Rauhut, Holger, A Mathematical Introduction to Compressive Sensing, (2013), Springer · Zbl 1315.94002
[21]	Gribonval, Rémi; Nielsen, Morten, Beyond sparsity: recovering structured representations by \(\{\ell \}^1\) minimization and greedy algorithms, Adv. Comput. Math., 28, 1, 23-41, (2008) · Zbl 1128.41004
[22]	Gross, David, Recovering low-rank matrices from few coefficients in any basis, IEEE Trans. Inform. Theory, 57, 3, 1548-1566, (2011) · Zbl 1366.94103
[23]	Gröchenig, Karlheinz; Luis Romero, José; Unnikrishnan, Jayakrishnan; Vetterli, Martin, On minimal trajectories for mobile sampling of bandlimited fields, Appl. Comput. Harmon. Anal., 39, 3, 487-510, (2015) · Zbl 1339.94028
[24]	Herzet, Cédric; Soussen, Charles; Idier, Jérôme; Gribonval, Rémi, Exact recovery conditions for sparse representations with partial support information, IEEE Trans. Inform. Theory, 59, 11, 7509-7524, (2013) · Zbl 1364.94128
[25]	Krahmer, Felix; Ward, Rachel, Stable and robust sampling strategies for compressive imaging, IEEE Trans. Image Process., 23, 2, 612-622, (2014) · Zbl 1374.94181
[26]	Lustig, Michael; Donoho, David; Pauly, John M., Sparse MRI: the application of compressed sensing for rapid MR imaging, Magn. Reson. Med., 58, 6, 1182-1195, (2007)
[27]	Leary, Rowan; Saghi, Zineb; Midgley, Paul A.; Holland, Daniel J., Compressed sensing electron tomography, Ultramicroscopy, 131, 70-91, (2013)
[28]	Polak, Adam C.; Duarte, Marco F.; Goeckel, Dennis L., Performance bounds for grouped incoherent measurements in compressive sensing, IEEE Signal Process., 63, 11, (2015) · Zbl 1394.94463
[29]	Puy, Gilles; Marques, Jose P.; Gruetter, Rolf; Thiran, J.; Van De Ville, Dimitri; Vandergheynst, Pierre; Wiaux, Yves, Spread spectrum magnetic resonance imaging, IEEE Trans. Med. Imag., 31, 3, 586-598, (2012)
[30]	Pan, Xiaochuan; Sidky, Emil Y.; Vannier, Michael, Why do commercial ct scanners still employ traditional, filtered back-projection for image reconstruction?, Inverse Probl., 25, 12, (2009) · Zbl 1185.68811
[31]	Puy, Gilles; Vandergheynst, Pierre; Wiaux, Yves, On variable density compressive sampling, IEEE Signal Process. Lett., 18, 10, 595-598, (2011)
[32]	Rauhut, Holger, Compressive sensing and structured random matrices, Theor. Found. Numer. Methods Sparse Recov., 9, 1-92, (2010) · Zbl 1208.15027
[33]	Roman, Bogdan; Hansen, Anders; Adcock, Ben, On asymptotic structure in compressed sensing, (2014), arXiv preprint · Zbl 1333.94014
[34]	Tauböck, Georg; Hlawatsch, Franz, A compressed sensing technique for ofdm channel estimation in mobile environments: exploiting channel sparsity for reducing pilots, (IEEE International Conference on Acoustics, Speech and Signal Processing, 2008. IEEE International Conference on Acoustics, Speech and Signal Processing, 2008, ICASSP 2008, (2008), IEEE), 2885-2888
[35]	Tropp, Joel A., Just relax: convex programming methods for identifying sparse signals in noise, IEEE Trans. Inform. Theory, 52, 3, 1030-1051, (2006) · Zbl 1288.94025
[36]	Tropp, Joel A., User-friendly tail bounds for sums of random matrices, Found. Comput. Math., 12, 4, 389-434, (2012) · Zbl 1259.60008
[37]	Unnikrishnan, J.; Vetterli, M., Sampling and reconstruction of spatial fields using mobile sensors, IEEE Trans. Signal Process., 61, 9, 2328-2340, (2013)
[38]	Unnikrishnan, Jayakrishnan; Vetterli, Martin, Sampling high-dimensional bandlimited fields on low-dimensional manifolds, IEEE Trans. Inform. Theory, 59, 4, 2103-2127, (2013) · Zbl 1364.94265
[39]	Wiaux, Yves; Jacques, Laurent; Puy, Gilles; Scaife, Anna M. M.; Vandergheynst, Pierre, Compressed sensing imaging techniques for radio interferometry, Mon. Not. R. Astron. Soc., 395, 3, 1733-1742, (2009)