Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$

Song Li; Junhong Lin

doi:10.3934/ipi.2014.8.761

Article Contents

2014, Volume 8, Issue 3: 761-777. Doi: 10.3934/ipi.2014.8.761

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

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

Received: May 31, 2011

Revised: May 31, 2013

Published: July 2014

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 94A12, 94A15, 94A08, 68P30; Secondary: 41A63, 15B52, 42C15.

Citation:

Related Papers

Cited by

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-263.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, Serie I, 346 (2008), 589-592.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-73.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-509.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-1223.doi: 10.1002/cpa.20124.
[7]	E. J. Candès and T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory, 51 (2005), 4203-4215.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-1308.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-4394.doi: 10.1109/TIT.2010.2054730.
[10]	R. Chartrand, Exact reconstructions of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14 (2007), 707-710.doi: 10.1109/LSP.2007.898300.
[11]	R. Chartrand and V. Staneva, Restricted isometry properties and nonconvex compressive sensing, Inverse Problems, 24 (2008), 1-14.doi: 10.1088/0266-5611/24/3/035020.
[12]	D. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306.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-38.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-2214.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-407.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-299.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-468.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-3415.doi: 10.1109/78.258082.
[20]	B. K. Natarajan, Sparse approximate solutions to linear systems, SIAM J. Comput., 24 (1995), 227-234.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-321.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-2219.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-1045.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, Speech, and Signal Processing (ICASSP), (2008), 3885-3888.doi: 10.1109/ICASSP.2008.4518502.
[25]	Q. Sun, Recovery of sparsest signals via $l_q$-minimization, Appl. Comput. Harmon. Anal., 32 (2012), 329-341.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-2242.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).