Diliberto-Straus algorithm

An algorithm first proposed in 1951 by S.P. Diliberto and E.G. Straus [a2]. It is concerned with the problem of finding a best approximation to from the subspace . In the original paper, and were closed, bounded intervals in , but there is no difficulty in thinking of them as compact Hausdorff spaces, and then giving the usual supremum norm (cf. also Approximation theory). The subspace might be more properly written as , where is the subspace of consisting of functions that are constant on . For , one defines

and

The algorithm is then given by , and , where and .

Diliberto and Straus showed that is an equicontinuous family of functions (cf. also Equicontinuity) and that . These two facts may be used to deduce, via the Ascoli theorem, that the sequence has cluster points (cf. also Cluster set), and that any such cluster point has the property that is a closest point to from . These results are interesting, because they establish that every has a best approximation in the infinite-dimensional subspace . Diliberto and Straus could not establish that the sequence is convergent. However, they came intriguingly near to such a proof when they apparently verified that in the algorithm the incremental functions and satisfy and as . Unfortunately, a referee demanded that the paper be shortened prior to publication, so the sequence of lemmas needed to establish this result appears without proof. Up till now (1998), no-one has been able to reproduce the series of arguments needed to support some of these lemmas. However, later work by G. Aumann [a1] established that and as independently of the methods of Diliberto and Straus. Armed with this knowledge, Aumann was able to prove that the Diliberto–Straus algorithm converges. A relatively simple proof of the convergence of the algorithm, which contains Aumann's result on and , can be found in [a6].

Generalizations.

There are two natural generalizations of the Diliberto–Straus algorithm. First, one can continue working in the space but increase the complexity of the subspace from to . Here, is the subspace of consisting of all polynomials of degree at most , and has a similar definition. One has to notice now that the operator as defined above has the property that, for each , the number is the best approximation to from . In the present scenario, the correct generalization is to take the mapping to be the polynomial of degree which is the best approximation to from . One can then examine the convergence of the algorithm as before. This was done by N. Dyn [a3], who showed that convergence cannot be guaranteed. In fact, if , then there exists a function such that the algorithm is stationary, that is, for all , but .

Another very natural generalization is to consider the algorithm in different spaces. For example, one could examine the behaviour of the analogous algorithm in , with the subspace , where . In the case , the algorithm takes place in a Hilbert space, and becomes the alternating algorithm of von Neumann. Because of the uniform convexity of for , the analysis of the algorithm can be carried out in considerable generality. The case is more delicate. As with the case studied by Dyn, there exist functions for which the algorithm is stationary, but . However, a class of functions can be identified on which the algorithm can be shown to converge. When working within this set of functions, the task of verifying that the incremental functions satisfy that and tend to is actually easier than the original problem tackled by Aumann. These results can be found in [a4], [a5].

Finally, it was the intention of Diliberto and Straus to consider approximation of multivariate functions by sums of univariate functions, and their paper gives a number of such results. Other generalizations in are given in [a7].

References

[a1]	G. Aumann, "Uber approximative nomographie II" Bayer. Akad. Math. Natur. Kl. Sitzungsber. (1959) pp. 103–109
[a2]	S.P. Diliberto, E.G. Straus, "On the approximation of a function of several variables by the sum of functions of fewer variables" Pacific J. Math. , 1 (1951) pp. 195–210
[a3]	N. Dyn, "A straightforward generalization of Diliberto and Straus' algorithm does not work" J. Approx. Th. , 30 : 4 (1980) pp. 247–250
[a4]	W.A. Light, "Convergence of the Diliberto–Straus algorithm in " Numer. Funct. Anal. Optim. , 3 : 2 (1981) pp. 137–146
[a5]	W.A. Light, "The Diliberto–Straus algorithm in " J. Approx. Th. , 38 : 1 (1983) pp. 1–8
[a6]	W.A. Light, E.W. Cheney, "On the approximation of a bivariate function by the sum of univariate functions" J. Approx. Th. , 29 : 4 (1980) pp. 305–322
[a7]	W.A. Light, S.M. Holland, "The -version of the Diliberto–Straus algorithm in " Proc. Edinburgh Math. Soc. , 27 (1984) pp. 31–45