9 - Approximation Algorithms

Summary

We are interested in algorithmic methods for finding best approximations from spaces of linear combinations of ridge functions. The main problem we will consider is that of approximating from the linear space

over some domain in Rⁿ, where r is finite and each f_i(Aⁱx) is in an appropriate normed linear space X. Recall that the Aⁱ are fixed d × n matrices and the dvariate functions Aⁱ are the variables. That is, we are looking at the question of approximating by generalized ridge functions with fixed directions. We are also interested in the problem of approximating from the set of ridge functions with variable directions. This problem is significantly different.

We predicate these algorithmic approximation methods on the following basic assumption. For each i ∊ {1, …, r}, set

where Aⁱ is a fixed d × n matrix and f(Aⁱx) lies in the appropriate space. Let P_i be a best approximation operator to M(Aⁱ), i.e., to each G the element P_iG is a best approximation to G from M(A_i). The major assumption underlying the methods discussed in this chapter is that each P_i is computable (see Example 8.1). Based on this assumption we outline various approximation approaches.

In Section 9.1 we discuss approximation algorithms in a Hilbert space setting. The theory is the most detailed when M(A¹, …, A^r) is closed. However, some convergence results are also known without the closure property. In Section 9.2 we generalize the above to consider a “greedy-type algorithm”. This permits us to deal with the possibility of an infinite number of directions. In Section 9.3 we consider the same problem as in Section 9.1, but in a uniformly convex and uniformly smooth Banach space.