Nonlinear function approximation: computing smooth solutions with an adaptive greedy algorithm
type: Item
instance of: scholarly article
title: Nonlinear function approximation: computing smooth solutions with an adaptive greedy algorithm
zbMATH Open document ID: 1106.41024
author: Andreas Hofinger
published in: Journal of Approximation Theory
publication date: 2007-01-26T00:00:00Z
review text: Let \(G\) be a set contained in the unit ball of the Hilbert space \(H\). Given an \(f \in H\) and a natural number \(n\), one has to find a good approximation to \(f\) by a linear combination of \(\leq n\) elements of \(G\) in a computationally effective way. The starting point of the paper is a version of the well-known greedy approximation algorithm. It is assumed that \(f \in \overline {\text{co}}( b G) \) for some \(b \in {\mathbb R}\). In the algorithm, elements \(g_k \in bG\) are chosen one after another and approximating elements \(f_k\) are built iteratively, starting with \(f_0=0\), as convex combinations of \(f_{k-1}\) and \(g_k\). To apply the algorithm, one needs to choose some number \(M\) satisfying \(M>b^2-\| f\| ^2\). It can then be proved that \(\| f-f_k\| ^2 \leq M/k\). For practical applications the author suggests a modification of the algorithm which deals with perturbed data \(f^\delta\), \(\| f -f^\delta\| \leq \delta\). Another problem is that the constant \(b\) is usually unknown apriori. To address this issue, an heuristic adaptive greedy algorithm is proposed which does not need \(b\) but rather recovers it iteratively from the available data. The applicability of this algorithm is demonstrated by numerical experiments.
Mathematics Subject Classification ID: 41A46
Mathematics Subject Classification ID: 41A65
zbMATH DE Number: 5118800
zbMATH Keywords: greedy algorithm
zbMATH Keywords: adaptive
zbMATH Keywords: data noise
zbMATH Keywords: regularization
reviewed by: Yuly Makovoz
MaRDI profile type: Publication
full work available at URL: j.jat.2006.03.016
OpenAlex ID: W2016220370
cites work: Universal approximation bounds for superpositions of a sigmoidal function
cites work: Regularized data-driven construction of fuzzy controllers
cites work: Regularized greedy algorithms for network training with data noise
cites work: Error bounds for approximation with neural networks
cites work: Q3598192
cites work: On the mathematical foundations of learning
cites work: Optimal nonlinear approximation
cites work: Some remarks on greedy algorithms
cites work: Rates of convex approximation in non-Hilbert spaces
cites work: Learning a function from noisy samples at a finite sparse set of points
cites work: On a conjecture of Huber concerning the convergence of projection pursuit regression
cites work: A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training
cites work: Local greedy approximation for nonlinear regression and neural network training.
cites work: Efficient agnostic learning of neural networks with bounded fan-in
cites work: Generalization bounds for function approximation from scattered noisy data
cites work: Q3344608
cites work: Remarks on projection pursuit regression and density estimation
cites work: Shannon sampling and function reconstruction from point values
cites work: Weak greedy algorithms
cites work: Nonlinear methods of approximation
DOI: 10.1016/J.JAT.2006.03.016
Recommended article: Adaptive algorithms of nonlinear approximation with finite terms
Recommended article: Q4233471
Recommended article: Q4191060
Recommended article: Best linear and nonlinear approximations for smooth functions
Recommended article: An optimal adaptive algorithm for the approximation of concave functions
Recommended article: A smooth approximation method for nonlinear \(l_1\) problem
Recommended article: Q4520055
Recommended article: Smoothing approximations to nonsmooth optimization problems
Recommended article: Greedy algorithm for functions with low mixed smoothness
Recommended article: Q4885366
description: scientific article; zbMATH DE number 5118800