Adaptive greedy approximations (Q5961558)

Let \({\mathcal H}\) be a Hilbert space. A dictionary \({\mathcal D}\) for \({\mathcal H}\) is a family of unit vectors in \({\mathcal H}\) such that finite linear combinations of \(g_{\gamma }\in {\mathcal D}\) are dense in \({\mathcal H}\). The problem of approximations over a dictionary is studied from different points. \(NP\)-Completeness of the problem is proved under some restriction on dictionary size in a finite-dimensional space \({\mathcal H}\). Suboptimal greedy algorithms of nonorthogonal and orthogonal matching pursuits \textit{S. Mallat} and \textit{Z. Zhang} [IEEE Trans. Signal Process. 41, No. 12, 3397-3415 (1993; Zbl 0842.94004)]; \textit{Y. C. Pati, R. Rezaiifar} and \textit{P. S. Krishnaprasad} [Proc. 27th Annual Asilomar Conf. Signals, Systems, and Computers, 40-44 (IEEE Computer Society Press) (1993)] are reviewed. Group-invariant dictionaries are investigated for the sake of wavelet decomposition. Furthermore, the renormalized matching pursuit map is proved to be a chaotic map for a particular dictionary in a low-dimensional space. Numerical results suggest ergodicity of that map for higher-dimensional matching pursuits, too. Their invariant measures are characterized using dictionary group invariances and by constructing a stochastic differential equation model for the distribution of asymptotic approximation errors for a dictionary consisting of a Dirac and a Fourier basis.