×

Almost optimality of orthogonal super greedy algorithms for incoherent dictionaries. (English) Zbl 1369.41038

Summary: We investigate the efficiency of weak orthogonal super greedy algorithm (WOSGA) for \(n\)-term approximation with respect to dictionaries which are \((n,D)\)-unconditional in arbitrary Hilbert space \(\mathcal{H}\). For an element \(f\in \mathcal{H}\), let \(f_{An}\) be the output of WOSGA after \(A_n\) steps for some constant \(A\). We show that the residual \(\| f-f_{An}\|\) can be bounded by a constant multiplying the error of best \(n\)-term approximation to \(f\). Moreover, we get an element \(f_n^\ast\), through a simple postprocessing of \(f_{An}\) by retaining its \(n\) largest components in absolute value, which realizes near best \(n\)-term approximation for \(f\). Our results are obtained for dictionaries in \(\mathcal{H}\) which satisfies the weaker assumption than the RIP condition.

MSC:

41A65 Abstract approximation theory (approximation in normed linear spaces and other abstract spaces)
41A50 Best approximation, Chebyshev systems
41A46 Approximation by arbitrary nonlinear expressions; widths and entropy
94A15 Information theory (general)
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Candes, E., Romberg, J. and Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math.59(8) (2006) 1207-1223. · Zbl 1098.94009
[2] Cohen, A., Dahmen, W. and DeVore, R., Compressed sensing and best \(k\)-term approximation, J. Am. Math. Soc.22(1) (2009) 211-231. · Zbl 1206.94008
[3] Cohen, A., Dahmen, W. and DeVore, R., Orthogonal matching pursuit under the restricted isometry property, Constr. Approx.45(1) (2017) 113-127. · Zbl 1379.94014
[4] DeVore, R., Nonlinear approximation, Acta. Numer.7 (1998) 51-150. · Zbl 0931.65007
[5] Günther, M.et al., Reconstruction of images from Gabor graphs with applications in facial image processing, Int. J. Wavelets, Multiresolut. Inf. Process.13(4) (2015), Article ID: 1550019, 25 pp., doi: 10.1142/S0219691315500198. · Zbl 1341.68176
[6] Lindenstrauss, J. and Tzafriri, L., Classical Banach Spaces II (Springer, Berlin, 1979). · Zbl 0403.46022
[7] Liu, E. and Temlyakov, V. N., Super greedy type algorithm, Adv. Comput. Math.37(4) (2012) 493-504. · Zbl 1258.41013
[8] Liu, E. and Temlyakov, V. N., The Orthogonal super greedy algorithm and applications in compressed sensing, IEEE Trans. Inf. Theory.58(4) (2012) 2040-2047. · Zbl 1365.94180
[9] Livshitz, E. D., On the optimality of the Orthogonal Greedy Algorithm for \(\mu \)-coherent dictionaries, J. Approx. Theory.164(5) (2012) 668-681. · Zbl 1248.41048
[10] Livshitz, E. D. and Temlyakov, V. N., Sparse approximation and recovery by greedy algorithms, IEEE Trans. Inform. Theory.60(7) (2014) 3989-4000. · Zbl 1360.94086
[11] Mo, Y., Qian, T. and Mi, W., Sparse representation in Szegö kernels through reproducing kernel Hilbert space theory with applications. Int. J. Wavelets, Multiresolut. Inf. Process.13(4) (2015), Article ID: 1550030, 22 pp., doi: 10.1142/S0219691315500307. · Zbl 1320.93036
[12] Temlyakov, V. N., Weak greedy algorithms, Adv. Comput. Math.12(2-3) (2000) 213-227. · Zbl 0964.65009
[13] Temlyakov, V. N., Greedy Approximation, (Cambridge University Press, Cambridge, 2011). · Zbl 1217.41020
[14] Temlyakov, V. N., Sparse approximation and recovery by greedy algorithms in Banach spaces, Forum Math. Sigma2 (2014), e12, 26 pp. · Zbl 1296.41030
[15] Temlyakov, V. N. and Zheltov, P., On performance of greedy algorithms, J. Approx. Theory.163(9) (2011) 1134-1145. · Zbl 1230.41005
[16] Wang, J., Kwon, S. and Shim, B., Generlized orthogonal matching pursuit, IEEE Trans. Signal Process.60(12) (2012) 6202-6216. · Zbl 1393.94479
[17] Wei, D., Analysis of orthogonal multi-matching pursuit under restricted isometry property, Sci. China. Math.57(10) (2014) 2179-2188. · Zbl 1307.65020
[18] Wei, X. J. and Ye, P. X., Estimates of restricted isometry constant in super greedy algorithms, Int. J. Future Generation Commun. Netw.8(5) (2015) 137-144.
[19] Wei, X. J. and Ye, P. X., Improved bounds on restricted isometry constant for orthogonal multi matching pursuit, J. Comput. Methods Sci. Eng.15(4) (2015) 737-744. · Zbl 1386.94043
[20] X. J. Wei and P. X. Ye, Lebesgue-type inequality for orthogonal super greedy algorithm, Preprint.
[21] Yang, B., Yang, C. and Huang, G., Efficient image fusion with approximate sparse representation, Int. J. Wavelets, Multiresolut. Inf. Process.14(4) (2016), Article ID: 1650024, 15 pp., doi: 10.1142/S0219691316500247. · Zbl 1347.65084
[22] Ye, P. X. and Wei, X. J., Efficiency of weak greedy algorithms for \(m\)-term approximations, Sci. China. Math.59(4) (2016) 697-714. · Zbl 1342.41023
[23] Zhang, T., Sparse recovery with orthogonal matching pursuit under RIP, IEEE Trans. Inf. Theory.57(9) (2011) 6215-6221. · Zbl 1365.94091
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.