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

Metrics

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

Other articles
by authors

[Back to Top]