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 $f \in C ( S \times T )$ from the subspace $C ( S ) + C ( T )$. In the original paper, $S$ and $T$ were closed, bounded intervals in $\mathbf{R}$, but there is no difficulty in thinking of them as compact Hausdorff spaces, and then giving $C ( S \times T )$ the usual supremum norm (cf. also Approximation theory). The subspace $C ( S ) + C ( T )$ might be more properly written as $C ( S ) \otimes \pi _ { 0 } ( T ) + \pi _ { 0 } ( S ) \otimes C ( T )$, where $\pi_{ 0} ( S )$ is the subspace of $C ( S )$ consisting of functions that are constant on $S$. For $f \in C ( S \times T )$, one defines

$$\begin{equation*} ( \mathcal{M} _ { s } f ) ( t ) = \frac { 1 } { 2 } \operatorname { sup } _ { s } f ( s , t ) + \frac { 1 } { 2 } \operatorname { inf } _ { s } f ( s , t ) \end{equation*}$$

and

$$\begin{equation*} ( M _ { t } f ) ( s ) = \frac { 1 } { 2 } \operatorname { sup } _ { t } f ( s , t ) + \frac { 1 } { 2 } \operatorname { inf } _ { t } f ( s , t ). \end{equation*}$$

The algorithm is then given by $f _ { 1 } = f$, $f _ { 2 n } = f _ { 2 n - 1 } - g _ { n }$ and $f _ { 2 n + 1 } = f _ { 2 n } - h _ { n }$, where $g _ { n } = \mathcal{M} _ { t }\, f _ { 2 n - 1}$ and $h _ { n } = \mathcal{M} _ { s }\, f _ { 2n }$.

Diliberto and Straus showed that $\{ f _ { n } \}$ is an equicontinuous family of functions (cf. also Equicontinuity) and that $\| f _ { n } \| \downarrow \text { dist } ( f , C ( S ) + C ( T ) )$. These two facts may be used to deduce, via the Ascoli theorem, that the sequence $\{ f _ { n } \}$ has cluster points (cf. also Cluster set), and that any such cluster point $f ^ { * }$ has the property that $f ^ { * } - f$ is a closest point to $f$ from $C ( S ) + C ( T )$. These results are interesting, because they establish that every $f \in C ( S \times T )$ has a best approximation in the infinite-dimensional subspace $C ( S ) + C ( T )$. Diliberto and Straus could not establish that the sequence $\{ f _ { n } \}$ is convergent. However, they came intriguingly near to such a proof when they apparently verified that in the algorithm the incremental functions $g _ { n }$ and $h_{n}$ satisfy $\| g _ { n } \| \rightarrow 0$ and $\| h _ { n } \| \rightarrow 0$ as $n \rightarrow \infty$. 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 $\| g _ { n } \| \rightarrow 0$ and $\| h _ { n } \| \rightarrow 0$ as $n \rightarrow \infty$ 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 $\| g _ { n } \|$ and $\| h_n \|$, can be found in [a6].

Generalizations.

There are two natural generalizations of the Diliberto–Straus algorithm. First, one can continue working in the space $C ( S \times T )$ but increase the complexity of the subspace from $C ( S ) \otimes \pi _ { 0 } ( T ) + \pi _ { 0 } ( S ) \otimes C ( T )$ to $C ( S ) \otimes \pi _ { k } ( T ) + \pi _{\ell} ( S ) \otimes C ( T )$. Here, $\pi _ { k } ( T )$ is the subspace of $C ( T )$ consisting of all polynomials of degree at most $k$, and $\pi_{\ell}(S)$ has a similar definition. One has to notice now that the operator ${\cal M} _ { s }$ as defined above has the property that, for each $t \in T$, the number $( \mathcal{M} _ { s } f ) ( t )$ is the best approximation to $f (\, \cdot\, , t )$ from $\pi_{ 0} ( S )$. In the present scenario, the correct generalization is to take the mapping $s \mapsto ( \mathcal{M} _ { s } f ) ( t )$ to be the polynomial of degree $k$ which is the best approximation to $f (\, \cdot\, , t )$ from $\pi _ { k } ( S )$. 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 $k , \ell \geq 1$, then there exists a function $f \in C ( S \times T )$ such that the algorithm is stationary, that is, $f _ { n } = f$ for all $n \geq 1$, but $\| f \| \neq \operatorname { dist } ( f , C ( S ) \otimes \pi _ { k } ( T ) + \pi_{\ell}( S ) \otimes C ( T ) )$.

Another very natural generalization is to consider the algorithm in different spaces. For example, one could examine the behaviour of the analogous algorithm in $L _ { p } ( S \times T )$, with the subspace $L _ { p } ( S ) + L _ { p } ( T )$, where $1 \leq p \leq \infty$. In the case $p = 2$, the algorithm takes place in a Hilbert space, and becomes the alternating algorithm of von Neumann. Because of the uniform convexity of $L _ { p } ( S \times T )$ for $1 < p < \infty$, the analysis of the algorithm can be carried out in considerable generality. The case $p = 1$ is more delicate. As with the case studied by Dyn, there exist functions $f \in L _ { 1 } ( S \times T )$ for which the algorithm is stationary, but $\| f \| \neq \operatorname { dist } ( f , L _ { 1 } ( S ) + L _ { 1 } ( T ) )$. However, a class of functions $\mathcal F \subset L _ { 1 } ( S \times T )$ 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 $\| g _ { n } \|$ and $\| h_n \|$ tend to $0$ 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 $L _ { 1 } ( S \times T )$ 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 $L _ { 1 } ( X \times Y )$" Numer. Funct. Anal. Optim. , 3 : 2 (1981) pp. 137–146
[a5]	W.A. Light, "The Diliberto–Straus algorithm in $L _ { 1 } ( X \times Y )$" 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 $L_1$-version of the Diliberto–Straus algorithm in $C ( T \times S )$" Proc. Edinburgh Math. Soc. , 27 (1984) pp. 31–45