Compressed sensing with coherent tight frames via l_q-minimization for 0 < q \leq 1

Previous Article
Detecting the localization of elastic inclusions and Lamé coefficients
IPI Home
This Issue
Next Article
Bayesian image restoration for mosaic active imaging

August 2014, 8(3): 761-777. doi: 10.3934/ipi.2014.8.761

Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$

Song Li ^1, and Junhong Lin ^1,

1.	Department of Mathematics, Zhejiang University, Hangzhou, 310027, China, China

Received June 2011 Revised June 2013 Published August 2014

Abstract
Related Papers

Our aim of this article is to reconstruct a signal from undersampled data in the situation that the signal is sparse in terms of a tight frame. We present a condition, which is independent of the coherence of the tight frame, to guarantee accurate recovery of signals which are sparse in the tight frame, from undersampled data with minimal $l_1$-norm of transform coefficients. This improves the result in [4]. Also, the $l_q$-minimization $(0 < q < 1)$ approaches are introduced. We show that under a suitable condition, there exists a value $q_0\in(0,1]$ such that for any $q\in(0,q_0)$, each solution of the $l_q$-minimization is approximately well to the true signal. In particular, when the tight frame is an identity matrix or an orthonormal basis, all results obtained in this paper appeared in [18] and [17].

Keywords: coherence., $D$-Restricted isometry property, Compressed sensing, sparse recovery, $l_q$-minimization, tight frames.

Mathematics Subject Classification: Primary: 94A12, 94A15, 94A08, 68P30; Secondary: 41A63, 15B52, 42C1.

Citation: Song Li, Junhong Lin. Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$. Inverse Problems and Imaging, 2014, 8 (3) : 761-777. doi: 10.3934/ipi.2014.8.761

References:

[1]	R. Baraniuk, E. J. Candès, R. Nowak and M. Vetterli, Sensing, Sampling, and Compression, IEEE Signal Proc. Mag., 25, (2008).
[2]	R. Baraniuk, M. Davenport, R. DeVore and M. Wakin, A simple proof of the restricted isometry property for random matrices, Constr. Approx., 28 (2008), 253-263. doi: 10.1007/s00365-007-9003-x.
[3]	E. J. Candès., The restricted isometry property and its implications for compressed sensing, C. R. Math. Acad. Sci. Paris, Serie I, 346 (2008), 589-592. doi: 10.1016/j.crma.2008.03.014.
[4]	E. J. Candès, Y. C. Eldar and D. Needell, Compressed Sensing with Coherent and Redundant Dictionaries, Appl. Comput. Harmon. Anal., 31 (2011), 59-73. doi: 10.1016/j.acha.2010.10.002.
[5]	E. J. Candès, J. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52 (2006), 489-509. doi: 10.1109/TIT.2005.862083.
[6]	E. J. Candès, J. Romberg and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math., 59 (2006), 1207-1223. doi: 10.1002/cpa.20124.
[7]	E. J. Candès and T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory, 51 (2005), 4203-4215. doi: 10.1109/TIT.2005.858979.
[8]	T. Cai, L. Wang and J. Zhang, Shifting inequality and recovery of sparse signals, IEEE Trans. Inform. Theory, 58 (2010), 1300-1308. doi: 10.1109/TSP.2009.2034936.
[9]	T. Cai, L. Wang and G. Xu, New bounds for restricted isometry constants, IEEE Trans. Inform. Theory, 56 (2010), 4388-4394. doi: 10.1109/TIT.2010.2054730.
[10]	R. Chartrand, Exact reconstructions of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14 (2007), 707-710. doi: 10.1109/LSP.2007.898300.
[11]	R. Chartrand and V. Staneva, Restricted isometry properties and nonconvex compressive sensing, Inverse Problems, 24 (2008), 1-14. doi: 10.1088/0266-5611/24/3/035020.
[12]	D. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582.
[13]	I. Daubechies, R. Devore, M. Fornasier and S. Gunturk, Iteratively reweighted least squares minimization for sparse recovery, Comm. Pure. Appl. Math., 63 (2010), 1-38. doi: 10.1002/cpa.20303.
[14]	M. E. Davies and R. Gribonval, Restricted isometry properties where $l_p$ sparse recovery can fail for $0 < p \leq 1$, IEEE Trans. Inform. Theory, 55 (2009), 2203-2214. doi: 10.1109/TIT.2009.2016030.
[15]	S. Foucart and M. J. Lai, Sparsest solutions of underdetermined linear systems via $l_q$ minimization for $0 < q \leq1$, Appl. Comput. Harmon. Anal., 26 (2009), 395-407. doi: 10.1016/j.acha.2008.09.001.
[16]	D. D. Ge, X. Y. Jiang and Y. Y. Ye, A note on complexity of $l_p$ minimization, Mathematical Programming, 129 (2011), 285-299. doi: 10.1007/s10107-011-0470-2.
[17]	M. J. Lai and L. Y. Liu, A new estimate of restricted isometry constants for sparse solutions,, manuscript., ().
[18]	Q. Mo and S. Li, New bounds on the restricted isometry constant $\delta_{2k}$, Appl. Comput. Harmon. Anal., 31 (2011), 460-468. doi: 10.1016/j.acha.2011.04.005.
[19]	S. G. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries, IEEE Trans. Signal Process., 41 (1993), 3397-3415. doi: 10.1109/78.258082.
[20]	B. K. Natarajan, Sparse approximate solutions to linear systems, SIAM J. Comput., 24 (1995), 227-234. doi: 10.1137/S0097539792240406.
[21]	D. Needell and J. A. Tropp, CoSaMP: Iterative signal recovery from noisy samples, Appl. Comput. Harmon. Anal., 26 (2009), 301-321. doi: 10.1016/j.acha.2008.07.002.
[22]	H. Rauhut, K. Schnass and P. Vandergheynst, Compressed sensing and redundant dictionaries, IEEE Trans. Inform. Theory, 54 (2008), 2210-2219. doi: 10.1109/TIT.2008.920190.
[23]	M. Rudelson and R. Vershynin, On sparse reconstruction from Fourier and Gaussian measurements, Comm. Pure Appl. Math., 61 (2008), 1025-1045. doi: 10.1002/cpa.20227.
[24]	R. Saab, R. Chartrand and O. Yilmaz, Stable sparse approximations via nonconvex optimization, Proceedings of the 33rd IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), (2008), 3885-3888. doi: 10.1109/ICASSP.2008.4518502.
[25]	Q. Sun, Recovery of sparsest signals via $l_q$-minimization, Appl. Comput. Harmon. Anal., 32 (2012), 329-341. doi: 10.1016/j.acha.2011.07.001.
[26]	J. A. Tropp, Greed is good: Algorithmic results for sparse approximation, IEEE Trans. Info. Theory, 50 (2004), 2231-2242. doi: 10.1109/TIT.2004.834793.
[27]	A. M. Zoubir and D. R. Iskander, Bootstrap Methods in Signal Processing, IEEE Signal Proc. Mag., 24 (2007).

show all references

References:

[1]	R. Baraniuk, E. J. Candès, R. Nowak and M. Vetterli, Sensing, Sampling, and Compression, IEEE Signal Proc. Mag., 25, (2008).
[2]	R. Baraniuk, M. Davenport, R. DeVore and M. Wakin, A simple proof of the restricted isometry property for random matrices, Constr. Approx., 28 (2008), 253-263. doi: 10.1007/s00365-007-9003-x.
[3]	E. J. Candès., The restricted isometry property and its implications for compressed sensing, C. R. Math. Acad. Sci. Paris, Serie I, 346 (2008), 589-592. doi: 10.1016/j.crma.2008.03.014.
[4]	E. J. Candès, Y. C. Eldar and D. Needell, Compressed Sensing with Coherent and Redundant Dictionaries, Appl. Comput. Harmon. Anal., 31 (2011), 59-73. doi: 10.1016/j.acha.2010.10.002.
[5]	E. J. Candès, J. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52 (2006), 489-509. doi: 10.1109/TIT.2005.862083.
[6]	E. J. Candès, J. Romberg and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math., 59 (2006), 1207-1223. doi: 10.1002/cpa.20124.
[7]	E. J. Candès and T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory, 51 (2005), 4203-4215. doi: 10.1109/TIT.2005.858979.
[8]	T. Cai, L. Wang and J. Zhang, Shifting inequality and recovery of sparse signals, IEEE Trans. Inform. Theory, 58 (2010), 1300-1308. doi: 10.1109/TSP.2009.2034936.
[9]	T. Cai, L. Wang and G. Xu, New bounds for restricted isometry constants, IEEE Trans. Inform. Theory, 56 (2010), 4388-4394. doi: 10.1109/TIT.2010.2054730.
[10]	R. Chartrand, Exact reconstructions of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14 (2007), 707-710. doi: 10.1109/LSP.2007.898300.
[11]	R. Chartrand and V. Staneva, Restricted isometry properties and nonconvex compressive sensing, Inverse Problems, 24 (2008), 1-14. doi: 10.1088/0266-5611/24/3/035020.
[12]	D. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582.
[13]	I. Daubechies, R. Devore, M. Fornasier and S. Gunturk, Iteratively reweighted least squares minimization for sparse recovery, Comm. Pure. Appl. Math., 63 (2010), 1-38. doi: 10.1002/cpa.20303.
[14]	M. E. Davies and R. Gribonval, Restricted isometry properties where $l_p$ sparse recovery can fail for $0 < p \leq 1$, IEEE Trans. Inform. Theory, 55 (2009), 2203-2214. doi: 10.1109/TIT.2009.2016030.
[15]	S. Foucart and M. J. Lai, Sparsest solutions of underdetermined linear systems via $l_q$ minimization for $0 < q \leq1$, Appl. Comput. Harmon. Anal., 26 (2009), 395-407. doi: 10.1016/j.acha.2008.09.001.
[16]	D. D. Ge, X. Y. Jiang and Y. Y. Ye, A note on complexity of $l_p$ minimization, Mathematical Programming, 129 (2011), 285-299. doi: 10.1007/s10107-011-0470-2.
[17]	M. J. Lai and L. Y. Liu, A new estimate of restricted isometry constants for sparse solutions,, manuscript., ().
[18]	Q. Mo and S. Li, New bounds on the restricted isometry constant $\delta_{2k}$, Appl. Comput. Harmon. Anal., 31 (2011), 460-468. doi: 10.1016/j.acha.2011.04.005.
[19]	S. G. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries, IEEE Trans. Signal Process., 41 (1993), 3397-3415. doi: 10.1109/78.258082.
[20]	B. K. Natarajan, Sparse approximate solutions to linear systems, SIAM J. Comput., 24 (1995), 227-234. doi: 10.1137/S0097539792240406.
[21]	D. Needell and J. A. Tropp, CoSaMP: Iterative signal recovery from noisy samples, Appl. Comput. Harmon. Anal., 26 (2009), 301-321. doi: 10.1016/j.acha.2008.07.002.
[22]	H. Rauhut, K. Schnass and P. Vandergheynst, Compressed sensing and redundant dictionaries, IEEE Trans. Inform. Theory, 54 (2008), 2210-2219. doi: 10.1109/TIT.2008.920190.
[23]	M. Rudelson and R. Vershynin, On sparse reconstruction from Fourier and Gaussian measurements, Comm. Pure Appl. Math., 61 (2008), 1025-1045. doi: 10.1002/cpa.20227.
[24]	R. Saab, R. Chartrand and O. Yilmaz, Stable sparse approximations via nonconvex optimization, Proceedings of the 33rd IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), (2008), 3885-3888. doi: 10.1109/ICASSP.2008.4518502.
[25]	Q. Sun, Recovery of sparsest signals via $l_q$-minimization, Appl. Comput. Harmon. Anal., 32 (2012), 329-341. doi: 10.1016/j.acha.2011.07.001.
[26]	J. A. Tropp, Greed is good: Algorithmic results for sparse approximation, IEEE Trans. Info. Theory, 50 (2004), 2231-2242. doi: 10.1109/TIT.2004.834793.
[27]	A. M. Zoubir and D. R. Iskander, Bootstrap Methods in Signal Processing, IEEE Signal Proc. Mag., 24 (2007).

[1]	Yingying Li, Stanley Osher. Coordinate descent optimization for l¹ minimization with application to compressed sensing; a greedy algorithm. Inverse Problems and Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487
[2]	Ting Chen, Fusheng Lv, Wenchang Sun. Uniform Approximation Property of Frames with Applications to Erasure Recovery. Communications on Pure and Applied Analysis, 2022, 21 (3) : 1093-1107. doi: 10.3934/cpaa.2022011
[3]	Pengbo Geng, Wengu Chen. Unconstrained $ \ell_1 $-$ \ell_2 $ minimization for sparse recovery via mutual coherence. Mathematical Foundations of Computing, 2020, 3 (2) : 65-79. doi: 10.3934/mfc.2020006
[4]	Steven L. Brunton, Joshua L. Proctor, Jonathan H. Tu, J. Nathan Kutz. Compressed sensing and dynamic mode decomposition. Journal of Computational Dynamics, 2015, 2 (2) : 165-191. doi: 10.3934/jcd.2015002
[5]	Ying Zhang, Ling Ma, Zheng-Hai Huang. On phaseless compressed sensing with partially known support. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1519-1526. doi: 10.3934/jimo.2019014
[6]	Zohre Aminifard, Saman Babaie-Kafaki. Diagonally scaled memoryless quasi–Newton methods with application to compressed sensing. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021191
[7]	Markus Grasmair. Well-posedness and convergence rates for sparse regularization with sublinear $l^q$ penalty term. Inverse Problems and Imaging, 2009, 3 (3) : 383-387. doi: 10.3934/ipi.2009.3.383
[8]	Seungkook Park. Coherence of sensing matrices coming from algebraic-geometric codes. Advances in Mathematics of Communications, 2016, 10 (2) : 429-436. doi: 10.3934/amc.2016016
[9]	Lingchen Kong, Naihua Xiu, Guokai Liu. Partial $S$-goodness for partially sparse signal recovery. Numerical Algebra, Control and Optimization, 2014, 4 (1) : 25-38. doi: 10.3934/naco.2014.4.25
[10]	Wanyou Cheng, Zixin Chen, Donghui Li. Nomonotone spectral gradient method for sparse recovery. Inverse Problems and Imaging, 2015, 9 (3) : 815-833. doi: 10.3934/ipi.2015.9.815
[11]	Hang Xu, Song Li. Analysis non-sparse recovery for relaxed ALASSO. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4055-4068. doi: 10.3934/cpaa.2020179
[12]	Xuemei Chen, Julia Dobrosotskaya. Inpainting via sparse recovery with directional constraints. Mathematical Foundations of Computing, 2020, 3 (4) : 229-247. doi: 10.3934/mfc.2020025
[13]	María Andrea Arias Serna, María Eugenia Puerta Yepes, César Edinson Escalante Coterio, Gerardo Arango Ospina. $ (Q,r) $ Model with $ CVaR_α $ of costs minimization. Journal of Industrial and Management Optimization, 2017, 13 (1) : 135-146. doi: 10.3934/jimo.2016008
[14]	Yi Shen, Song Li. Sparse signals recovery from noisy measurements by orthogonal matching pursuit. Inverse Problems and Imaging, 2015, 9 (1) : 231-238. doi: 10.3934/ipi.2015.9.231
[15]	Samer Dweik. $ L^{p, q} $ estimates on the transport density. Communications on Pure and Applied Analysis, 2019, 18 (6) : 3001-3009. doi: 10.3934/cpaa.2019134
[16]	Der-Chen Chang, Jie Xiao. $L^q$-Extensions of $L^p$-spaces by fractional diffusion equations. Discrete and Continuous Dynamical Systems, 2015, 35 (5) : 1905-1920. doi: 10.3934/dcds.2015.35.1905
[17]	Yonggui Zhu, Yuying Shi, Bin Zhang, Xinyan Yu. Weighted-average alternating minimization method for magnetic resonance image reconstruction based on compressive sensing. Inverse Problems and Imaging, 2014, 8 (3) : 925-937. doi: 10.3934/ipi.2014.8.925
[18]	Wengu Chen, Huanmin Ge. Recovery of block sparse signals under the conditions on block RIC and ROC by BOMP and BOMMP. Inverse Problems and Imaging, 2018, 12 (1) : 153-174. doi: 10.3934/ipi.2018006
[19]	Pia Heins, Michael Moeller, Martin Burger. Locally sparse reconstruction using the $l^{1,\infty}$-norm. Inverse Problems and Imaging, 2015, 9 (4) : 1093-1137. doi: 10.3934/ipi.2015.9.1093
[20]	Lei Wu, Zhe Sun. A new spectral method for $l_1$-regularized minimization. Inverse Problems and Imaging, 2015, 9 (1) : 257-272. doi: 10.3934/ipi.2015.9.257

2020 Impact Factor: 1.639

Tools

Metrics

Other articles
by authors

on AIMS
Song Li Junhong Lin
on Google Scholar
Song Li Junhong Lin

[Back to Top]