RATES OF CONVEX APPROXIMATION IN NON-HILBERT SPACES

This paper deals with sparse approximations by means of convex combina tions of elements from a predetermined ''basis'' subset S of a functio n space. Specifically, the focus is on the rate at which the lowest ac hievable error can be reduced as larger subsets of S are allowed when constructing an approximant. The new results extend those given for Hi lbert spaces by Jones and Barren, including, in particular, a computat ionally attractive incremental approximation scheme. Bounds are derive d for broad classes of Banach spaces; in particular, for L(p) spaces w ith 1 < p < infinity, the O(n(-1/2)) bounds of Barren and Jones are re covered when p = 2. One motivation for the questions studied here aris es from the area of ''artificial neural networks,'' where the problem can be stated in terms of the growth in the number of ''neurons'' (the elements of S) needed in order to achieve a desired error rate. The f ocus on non-Hilbert spaces is due to the desire to understand approxim ation in the more ''robust'' (resistant to exemplar noise) L(p), 1 les s than or equal to p < 2, norms. The techniques used borrow from resul ts regarding moduli of smoothness in functional analysis as well as fr om the theory of stochastic processes on function spaces.