Compressed sensing with coherent tight frames via l

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

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$

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 & 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. 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, 346* (2008), 589. 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. 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. 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. doi: 10.1002/cpa.20124.
[7]	E. J. Candès and T. Tao, Decoding by linear programming,, IEEE Trans. Inform. Theory, 51 (2005), 4203. 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. 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. doi: 10.1109/TIT.2010.2054730.
[10]	R. Chartrand, Exact reconstructions of sparse signals via nonconvex minimization,, IEEE Signal Process. Lett., 14 (2007), 707. doi: 10.1109/LSP.2007.898300.
[11]	R. Chartrand and V. Staneva, Restricted isometry properties and nonconvex compressive sensing,, Inverse Problems, 24 (2008), 1. doi: 10.1088/0266-5611/24/3/035020.
[12]	D. Donoho, Compressed sensing,, IEEE Trans. Inform. Theory, 52 (2006), 1289. 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. 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. 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. 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. 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. 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. doi: 10.1109/78.258082.
[20]	B. K. Natarajan, Sparse approximate solutions to linear systems,, SIAM J. Comput., 24 (1995), 227. 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. 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. 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. 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, (2008), 3885. doi: 10.1109/ICASSP.2008.4518502.
[25]	Q. Sun, Recovery of sparsest signals via $l_q$-minimization,, Appl. Comput. Harmon. Anal., 32 (2012), 329. 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. 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. 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, 346* (2008), 589. 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. 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. 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. doi: 10.1002/cpa.20124.
[7]	E. J. Candès and T. Tao, Decoding by linear programming,, IEEE Trans. Inform. Theory, 51 (2005), 4203. 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. 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. doi: 10.1109/TIT.2010.2054730.
[10]	R. Chartrand, Exact reconstructions of sparse signals via nonconvex minimization,, IEEE Signal Process. Lett., 14 (2007), 707. doi: 10.1109/LSP.2007.898300.
[11]	R. Chartrand and V. Staneva, Restricted isometry properties and nonconvex compressive sensing,, Inverse Problems, 24 (2008), 1. doi: 10.1088/0266-5611/24/3/035020.
[12]	D. Donoho, Compressed sensing,, IEEE Trans. Inform. Theory, 52 (2006), 1289. 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. 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. 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. 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. 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. 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. doi: 10.1109/78.258082.
[20]	B. K. Natarajan, Sparse approximate solutions to linear systems,, SIAM J. Comput., 24 (1995), 227. 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. 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. 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. 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, (2008), 3885. doi: 10.1109/ICASSP.2008.4518502.
[25]	Q. Sun, Recovery of sparsest signals via $l_q$-minimization,, Appl. Comput. Harmon. Anal., 32 (2012), 329. 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. 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 & Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487
[2]	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
[3]	Ying Zhang, Ling Ma, Zheng-Hai Huang. On phaseless compressed sensing with partially known support. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-8. doi: 10.3934/jimo.2019014
[4]	Markus Grasmair. Well-posedness and convergence rates for sparse regularization with sublinear $l^q$ penalty term. Inverse Problems & Imaging, 2009, 3 (3) : 383-387. doi: 10.3934/ipi.2009.3.383
[5]	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
[6]	Lingchen Kong, Naihua Xiu, Guokai Liu. Partial $S$-goodness for partially sparse signal recovery. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 25-38. doi: 10.3934/naco.2014.4.25
[7]	Wanyou Cheng, Zixin Chen, Donghui Li. Nomonotone spectral gradient method for sparse recovery. Inverse Problems & Imaging, 2015, 9 (3) : 815-833. doi: 10.3934/ipi.2015.9.815
[8]	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 & Management Optimization, 2017, 13 (1) : 135-146. doi: 10.3934/jimo.2016008
[9]	Yi Shen, Song Li. Sparse signals recovery from noisy measurements by orthogonal matching pursuit. Inverse Problems & Imaging, 2015, 9 (1) : 231-238. doi: 10.3934/ipi.2015.9.231
[10]	Samer Dweik. $ L^{p, q} $ estimates on the transport density. Communications on Pure & Applied Analysis, 2019, 18 (6) : 3001-3009. doi: 10.3934/cpaa.2019134
[11]	Der-Chen Chang, Jie Xiao. $L^q$-Extensions of $L^p$-spaces by fractional diffusion equations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (5) : 1905-1920. doi: 10.3934/dcds.2015.35.1905
[12]	Wengu Chen, Huanmin Ge. Recovery of block sparse signals under the conditions on block RIC and ROC by BOMP and BOMMP. Inverse Problems & Imaging, 2018, 12 (1) : 153-174. doi: 10.3934/ipi.2018006
[13]	Yonggui Zhu, Yuying Shi, Bin Zhang, Xinyan Yu. Weighted-average alternating minimization method for magnetic resonance image reconstruction based on compressive sensing. Inverse Problems & Imaging, 2014, 8 (3) : 925-937. doi: 10.3934/ipi.2014.8.925
[14]	Pia Heins, Michael Moeller, Martin Burger. Locally sparse reconstruction using the $l^{1,\infty}$-norm. Inverse Problems & Imaging, 2015, 9 (4) : 1093-1137. doi: 10.3934/ipi.2015.9.1093
[15]	Lei Wu, Zhe Sun. A new spectral method for $l_1$-regularized minimization. Inverse Problems & Imaging, 2015, 9 (1) : 257-272. doi: 10.3934/ipi.2015.9.257
[16]	Yingying Li, Stanley Osher, Richard Tsai. Heat source identification based on $l_1$ constrained minimization. Inverse Problems & Imaging, 2014, 8 (1) : 199-221. doi: 10.3934/ipi.2014.8.199
[17]	Kanghui Guo, Demetrio Labate. Optimally sparse 3D approximations using shearlet representations. Electronic Research Announcements, 2010, 17: 125-137. doi: 10.3934/era.2010.17.125
[18]	A. Naga, Z. Zhang. The polynomial-preserving recovery for higher order finite element methods in 2D and 3D. Discrete & Continuous Dynamical Systems - B, 2005, 5 (3) : 769-798. doi: 10.3934/dcdsb.2005.5.769
[19]	Damiano Foschi. Some remarks on the $L^p-L^q$ boundedness of trigonometric sums and oscillatory integrals. Communications on Pure & Applied Analysis, 2005, 4 (3) : 569-588. doi: 10.3934/cpaa.2005.4.569
[20]	Karen Yagdjian, Anahit Galstian. Fundamental solutions for wave equation in Robertson-Walker model of universe and $L^p-L^q$ -decay estimates. Discrete & Continuous Dynamical Systems - S, 2009, 2 (3) : 483-502. doi: 10.3934/dcdss.2009.2.483

2018 Impact Factor: 1.469

American Institute of Mathematical Sciences