×

zbMATH — the first resource for mathematics

Sparse recovery by non-convex optimization - instance optimality. (English) Zbl 1200.90158
The authors discuss the theoretical properties of a class of compressed sensing decoders that rely on \(\ell^P\) minimization with \(0<p<1\). For an introduction to the topic one may consult a paper by E. J Candès, J. Romberg and T. Tao [Commun. Pure Appl. Math. 59, No. 8, 1207–1223 (2006; Zbl 1098.94009)] that treats the case \(p=1\).

MSC:
90C30 Nonlinear programming
Software:
PDCO
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baraniuk, R.; Davenport, M.; DeVore, R.; Wakin, M., A simple proof of the restricted isometry property for random matrices, Constr. approx., 28, 3, 253-263, (2008) · Zbl 1177.15015
[2] Candès, E.J.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE trans. inform. theory, 52, 489-509, (2006) · Zbl 1231.94017
[3] Candès, E.J.; Romberg, J.; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Comm. pure appl. math., 59, 1207-1223, (2006) · Zbl 1098.94009
[4] Candès, E.J.; Tao, T., Decoding by linear programming, IEEE trans. inform. theory, 51, 12, 489-509, (2005)
[5] Candès, E.J.; Tao, T., Near-optimal signal recovery from random projections: universal encoding strategies?, IEEE trans. inform. theory, 52, 12, 5406-5425, (2006) · Zbl 1309.94033
[6] Candès, E.J., The restricted isometry property and its implications for compressed sensing, C. R. math., 346, 9-10, 589-592, (2008) · Zbl 1153.94002
[7] Chartrand, R.; Staneva, V., Restricted isometry properties and nonconvex compressive sensing, Inverse problems, 24, (2008), 035020 · Zbl 1143.94004
[8] Chartrand, R., Exact reconstructions of sparse signals via nonconvex minimization, IEEE signal process. lett., 14, 10, 707-710, (2007)
[9] Chen, S.; Donoho, D.; Saunders, M., Atomic decomposition by basis pursuit, SIAM J. sci. comput., 20, 1, 33-61, (1999) · Zbl 0919.94002
[10] Cohen, A.; Dahmen, W.; DeVore, R., Compressed sensing and best k-term approximation, J. amer. math. soc., 22, 1, 211-231, (2009) · Zbl 1206.94008
[11] I. Daubechies, R. DeVore, M. Fornasier, S. Gunturk, Iteratively re-weighted least squares minimization for sparse recovery, Comm. Pure Appl. Math., in press · Zbl 1202.65046
[12] Davies, M.; Gribonval, R., Restricted isometry constants where \(\ell^p\) sparse recovery can fail for \(0 < p \leqslant 1\), IEEE trans. inform. theory, 55, 5, 2203-2214, (2009) · Zbl 1367.94083
[13] Donoho, D.; Elad, M., Optimally sparse representation in general (nonorthogonal) dictionaries via \(\ell^1\) minimization, Proc. natl. acad. sci. USA, 100, 5, 2197-2202, (2003) · Zbl 1064.94011
[14] Donoho, D.; Huo, X., Uncertainty principles and ideal atomic decomposition, IEEE trans. inform. theory, 47, 2845-2862, (2001) · Zbl 1019.94503
[15] Donoho, D., Compressed sensing, IEEE trans. inform. theory, 52, 4, 1289-1306, (2006) · Zbl 1288.94016
[16] Figueiredo, M.; Nowak, R.; Wright, S., Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE J. sel. top. signal process., 1, 4, 586-597, (2007)
[17] Foucart, S.; Lai, M., Sparsest solutions of underdetermined linear systems via \(\ell^q\)-minimization for \(0 < q \leqslant 1\), Appl. comput. harmon. anal., 26, 3, 395-407, (2009) · Zbl 1171.90014
[18] Gordon, Y.; Kalton, N., Local structure theory for quasi-normed spaces, Bull. sci. math., 118, 441-453, (1994) · Zbl 0821.46001
[19] R. Gribonval, R.M. Figueras i Ventura, P. Vandergheynst, A simple test to check the optimality of sparse signal approximations, in: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP’05), vol. 5, 2005, pp. V/717-V/720 · Zbl 1163.94342
[20] Gribonval, R.; Figueras i Ventura, R.M.; Vandergheynst, P., A simple test to check the optimality of sparse signal approximations, Special issue on sparse approximations in signal and image processing, EURASIP signal process., 86, 3, 496-510, (2006) · Zbl 1163.94342
[21] Gribonval, R.; Nielsen, M., On the strong uniqueness of highly sparse expansions from redundant dictionaries, () · Zbl 1133.94011
[22] Gribonval, R.; Nielsen, M., Highly sparse representations from dictionaries are unique and independent of the sparseness measure, Appl. comput. harmon. anal., 22, 3, 335-355, (2007) · Zbl 1133.94011
[23] Guedon, O.; Litvak, A., Euclidean projections of p-convex body, (), 95-108 · Zbl 0988.52010
[24] Peck, N., Banach – mazur distances and projections on p-convex spaces, Math. Z., 177, 1, 131-142, (1981) · Zbl 0448.46018
[25] R. Saab, R. Chartrand, O. Yilmaz, Stable sparse approximations via nonconvex optimization, in: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2008, pp. 3885-3888
[26] Tropp, J., Recovery of short, complex linear combinations via \(l^1\) minimization, IEEE trans. inform. theory, 51, 4, 1568-1570, (2005) · Zbl 1288.94020
[27] P. Vandergheynst, P. Frossard, Efficient image representation by anisotropic refinement in matching pursuit, in: IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), vol. 3, 2001
[28] van den Berg, E.; Friedlander, M., In pursuit of a root, UBC Computer Science Technical Report TR-2007-16
[29] Ventura, R.; Vandergheynst, P.; Frossard, P., Low rate and scalable image coding with redundant representations, IEEE trans. image process., 15, 3, 726-739, (2006)
[30] P. Wojtaszczyk, Stability and instance optimality for gaussian measurements in compressed sensing, Found. Comput. Math. (2009), doi:10.1007/s10208-009-9046-4, in press · Zbl 1189.68060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.