title: Can dictionary-based computational models outperform the best linear ones?
abstract: Approximation capabilities of two types of computational models are explored: dictionary-based models (i.e., linear combinations of n-tuples of basis functions computable by units belonging to a set called "dictionary") and linear ones (i.e., linear combinations of n fixed basis functions). The two models are compared in terms of approximation rates, i.e., speeds of decrease of approximation errors for a growing number n of basis functions. Proofs of upper bounds on approximation rates by dictionary-based models are inspected, to show that for individual functions they do not imply estimates for dictionary-based models that do not hold also for some linear models. Instead, the possibility of getting faster approximation rates by dictionary-based models is demonstrated for worst-case errors in approximation of suitable sets of functions. For such sets, even geometric upper bounds hold.
authors.affiliation: Department of Communications, Computer, and System Sciences (DIST), University of Genoa, Via Opera Pia 13, 16145 Genova, Italy. giorgio.gnecco@dist.unige.it
authors.forename: Giorgio
authors.initials: G
authors.lastname: Gnecco
authors.forename: Věra
authors.initials: V
authors.lastname: Kůrková
authors.forename: Marcello
authors.initials: M
authors.lastname: Sanguineti
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D016014:Linear Models; D016571:Neural Networks, Computer; D015203:Reproducibility of Results