American Institute of Mathematical Sciences

Advanced
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

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).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

R. Chartrand, Exact reconstructions of sparse signals via nonconvex minimization,, IEEE Signal Process. Lett., 14 (2007), 707.  doi: 10.1109/LSP.2007.898300.  Google Scholar

[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.  Google Scholar

[12]

D. Donoho, Compressed sensing,, IEEE Trans. Inform. Theory, 52 (2006), 1289.  doi: 10.1109/TIT.2006.871582.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

M. J. Lai and L. Y. Liu, A new estimate of restricted isometry constants for sparse solutions,, manuscript., ().   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

B. K. Natarajan, Sparse approximate solutions to linear systems,, SIAM J. Comput., 24 (1995), 227.  doi: 10.1137/S0097539792240406.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[27]

A. M. Zoubir and D. R. Iskander, Bootstrap Methods in Signal Processing,, IEEE Signal Proc. Mag., 24 (2007).   Google Scholar

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).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

R. Chartrand, Exact reconstructions of sparse signals via nonconvex minimization,, IEEE Signal Process. Lett., 14 (2007), 707.  doi: 10.1109/LSP.2007.898300.  Google Scholar

[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.  Google Scholar

[12]

D. Donoho, Compressed sensing,, IEEE Trans. Inform. Theory, 52 (2006), 1289.  doi: 10.1109/TIT.2006.871582.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

M. J. Lai and L. Y. Liu, A new estimate of restricted isometry constants for sparse solutions,, manuscript., ().   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

B. K. Natarajan, Sparse approximate solutions to linear systems,, SIAM J. Comput., 24 (1995), 227.  doi: 10.1137/S0097539792240406.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[27]

A. M. Zoubir and D. R. Iskander, Bootstrap Methods in Signal Processing,, IEEE Signal Proc. Mag., 24 (2007).   Google Scholar

[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]

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
[3]

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
[4]

Ying Zhang, Ling Ma, Zheng-Hai Huang. On phaseless compressed sensing with partially known support. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1519-1526. doi: 10.3934/jimo.2019014
[5]

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
[6]

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
[7]

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
[8]

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
[9]

Hang Xu, Song Li. Analysis non-sparse recovery for relaxed ALASSO. Communications on Pure & Applied Analysis, 2020, 19 (8) : 4055-4068. doi: 10.3934/cpaa.2020179
[10]

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
[11]

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
[12]

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
[13]

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
[14]

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
[15]

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
[16]

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
[17]

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
[18]

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
[19]

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
[20]

Yifu Feng, Min Zhang. A $p$-spherical section property for matrix Schatten-$p$ quasi-norm minimization. Journal of Industrial & Management Optimization, 2020, 16 (1) : 397-407. doi: 10.3934/jimo.2018159

2019 Impact Factor: 1.373

Tools

Metrics

  • PDF downloads (28)
  • HTML views (0)
  • Cited by (14)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences