Sparse recovery by non-convex optimization - instance optimality. (English) Zbl 1200.90158

Saab, Rayan; Yılmaz, Özgür

Appl. Comput. Harmon. Anal. 29, No. 1, 30-48 (2010).

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

Reviewer: Alberto Seeger (Avignon)

MSC:

90C30

Nonlinear programming

Keywords:

compressed sensing; compressive sampling; \(\ell ^{1}\) minimization; \(\ell ^p\) minimization; sparse reconstruction; instance optimality; instance optimality in probability

Citations:

Zbl 1098.94009

Software:

PDCO

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
[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
[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. 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, (International Conference on Independent Component Analysis (ICA’04). International Conference on Independent Component Analysis (ICA’04), Lecture Notes in Comput. Sci., vol. 3195 (2004), Springer-Verlag: Springer-Verlag Granada, Spain) · 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, (GAFA. GAFA, Lecture Notes in Math., vol. 1745 (2000)), 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
[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
[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)