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

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].
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 l1 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

Metrics

  • PDF downloads (4)
  • HTML views (0)
  • Cited by (9)

Other articles
by authors

[Back to Top]