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]

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

Leanne Dong. Random attractors for stochastic Navier-Stokes equation on a 2D rotating sphere with stable Lévy noise. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020352
[3]

Weinan E, Weiguo Gao. Orbital minimization with localization. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 249-264. doi: 10.3934/dcds.2009.23.249
[4]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044
[5]

Giulia Cavagnari, Antonio Marigonda. Attainability property for a probabilistic target in wasserstein spaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 777-812. doi: 10.3934/dcds.2020300
[6]

Xianbo Sun, Zhanbo Chen, Pei Yu. Parameter identification on Abelian integrals to achieve Chebyshev property. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020375
[7]

Darko Dimitrov, Hosam Abdo. Tight independent set neighborhood union condition for fractional critical deleted graphs and ID deleted graphs. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 711-721. doi: 10.3934/dcdss.2019045
[8]

Bo Tan, Qinglong Zhou. Approximation properties of Lüroth expansions. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020389
[9]

Guojie Zheng, Dihong Xu, Taige Wang. A unique continuation property for a class of parabolic differential inequalities in a bounded domain. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020280
[10]

Hua Zhong, Xiaolin Fan, Shuyu Sun. The effect of surface pattern property on the advancing motion of three-dimensional droplets. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020366
[11]

Thabet Abdeljawad, Mohammad Esmael Samei. Applying quantum calculus for the existence of solution of $ q $-integro-differential equations with three criteria. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020440
[12]

Bingyan Liu, Xiongbing Ye, Xianzhou Dong, Lei Ni. Branching improved Deep Q Networks for solving pursuit-evasion strategy solution of spacecraft. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021016
[13]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074
[14]

Meng Ding, Ting-Zhu Huang, Xi-Le Zhao, Michael K. Ng, Tian-Hui Ma. Tensor train rank minimization with nonlocal self-similarity for tensor completion. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021001
[15]

Helin Guo, Huan-Song Zhou. Properties of the minimizers for a constrained minimization problem arising in Kirchhoff equation. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1023-1050. doi: 10.3934/dcds.2020308
[16]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136
[17]

Bao Wang, Alex Lin, Penghang Yin, Wei Zhu, Andrea L. Bertozzi, Stanley J. Osher. Adversarial defense via the data-dependent activation, total variation minimization, and adversarial training. Inverse Problems & Imaging, 2021, 15 (1) : 129-145. doi: 10.3934/ipi.2020046
[18]

Luis Caffarelli, Fanghua Lin. Nonlocal heat flows preserving the L2 energy. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 49-64. doi: 10.3934/dcds.2009.23.49
[19]

Editorial Office. Retraction: Wei Gao and Juan L. G. Guirao, Preface. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : ⅰ-ⅰ. doi: 10.3934/dcdss.201904i
[20]

Magdalena Foryś-Krawiec, Jiří Kupka, Piotr Oprocha, Xueting Tian. On entropy of $ \Phi $-irregular and $ \Phi $-level sets in maps with the shadowing property. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1271-1296. doi: 10.3934/dcds.2020317

2019 Impact Factor: 1.373

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences