Namespaces
Variants
Actions

Difference between revisions of "Diliberto-Straus algorithm"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (AUTOMATIC EDIT (latexlist): Replaced 77 formulas out of 78 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
Line 1: Line 1:
An algorithm first proposed in 1951 by S.P. Diliberto and E.G. Straus [[#References|[a2]]]. It is concerned with the problem of finding a best approximation to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d1201601.png" /> from the subspace <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d1201602.png" />. In the original paper, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d1201603.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d1201604.png" /> were closed, bounded intervals in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d1201605.png" />, but there is no difficulty in thinking of them as compact Hausdorff spaces, and then giving <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d1201606.png" /> the usual supremum norm (cf. also [[Approximation theory|Approximation theory]]). The subspace <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d1201607.png" /> might be more properly written as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d1201608.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d1201609.png" /> is the subspace of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016010.png" /> consisting of functions that are constant on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016011.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016012.png" />, one defines
+
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016013.png" /></td> </tr></table>
+
Out of 78 formulas, 77 were replaced by TEX code.-->
 +
 
 +
{{TEX|semi-auto}}{{TEX|partial}}
 +
An algorithm first proposed in 1951 by S.P. Diliberto and E.G. Straus [[#References|[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|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
 
and
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016014.png" /></td> </tr></table>
+
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016015.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016016.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016017.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016019.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016020.png" /> is an equicontinuous family of functions (cf. also [[Equicontinuity|Equicontinuity]]) and that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016021.png" />. These two facts may be used to deduce, via the [[Ascoli theorem|Ascoli theorem]], that the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016022.png" /> has cluster points (cf. also [[Cluster set|Cluster set]]), and that any such cluster point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016023.png" /> has the property that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016024.png" /> is a closest point to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016025.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016026.png" />. These results are interesting, because they establish that every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016027.png" /> has a best approximation in the infinite-dimensional subspace <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016028.png" />. Diliberto and Straus could not establish that the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016029.png" /> is convergent. However, they came intriguingly near to such a proof when they apparently verified that in the algorithm the incremental functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016030.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016031.png" /> satisfy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016032.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016033.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016034.png" />. 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 [[#References|[a1]]] established that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016035.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016036.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016037.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016039.png" />, can be found in [[#References|[a6]]].
+
Diliberto and Straus showed that $\{ f _ { n } \}$ is an equicontinuous family of functions (cf. also [[Equicontinuity|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|Ascoli theorem]], that the sequence $\{ f _ { n } \}$ has cluster points (cf. also [[Cluster set|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 [[#References|[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 [[#References|[a6]]].
  
 
==Generalizations.==
 
==Generalizations.==
There are two natural generalizations of the Diliberto–Straus algorithm. First, one can continue working in the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016040.png" /> but increase the complexity of the subspace from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016041.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016042.png" />. Here, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016043.png" /> is the subspace of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016044.png" /> consisting of all polynomials of degree at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016045.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016046.png" /> has a similar definition. One has to notice now that the operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016047.png" /> as defined above has the property that, for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016048.png" />, the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016049.png" /> is the best approximation to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016050.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016051.png" />. In the present scenario, the correct generalization is to take the mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016052.png" /> to be the polynomial of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016053.png" /> which is the best approximation to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016054.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016055.png" />. One can then examine the convergence of the algorithm as before. This was done by N. Dyn [[#References|[a3]]], who showed that convergence cannot be guaranteed. In fact, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016056.png" />, then there exists a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016057.png" /> such that the algorithm is stationary, that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016058.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016059.png" />, but <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016060.png" />.
+
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 _{\text{l}} ( S ) \otimes C ( T )$. Here, $\pi _ { k } ( T )$ is the subspace of $C ( T )$ consisting of all polynomials of degree at most $k$, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016046.png"/> 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 [[#References|[a3]]], who showed that convergence cannot be guaranteed. In fact, if $k , \text{l} \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_{\text{l}}( 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016061.png" />, with the subspace <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016062.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016063.png" />. In the case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016064.png" />, the algorithm takes place in a Hilbert space, and becomes the alternating algorithm of von Neumann. Because of the uniform convexity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016065.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016066.png" />, the analysis of the algorithm can be carried out in considerable generality. The case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016067.png" /> is more delicate. As with the case studied by Dyn, there exist functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016068.png" /> for which the algorithm is stationary, but <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016069.png" />. However, a class of functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016070.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016071.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016072.png" /> tend to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016073.png" /> is actually easier than the original problem tackled by Aumann. These results can be found in [[#References|[a4]]], [[#References|[a5]]].
+
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 &lt; p &lt; \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 [[#References|[a4]]], [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016074.png" /> are given in [[#References|[a7]]].
+
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 [[#References|[a7]]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G. Aumann,  "Uber approximative nomographie II"  ''Bayer. Akad. Math. Natur. Kl. Sitzungsber.''  (1959)  pp. 103–109</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  N. Dyn,  "A straightforward generalization of Diliberto and Straus' algorithm does not work"  ''J. Approx. Th.'' , '''30''' :  4  (1980)  pp. 247–250</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  W.A. Light,  "Convergence of the Diliberto–Straus algorithm in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016075.png" />"  ''Numer. Funct. Anal. Optim.'' , '''3''' :  2  (1981)  pp. 137–146</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  W.A. Light,  "The Diliberto–Straus algorithm in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016076.png" />"  ''J. Approx. Th.'' , '''38''' :  1  (1983)  pp. 1–8</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  W.A. Light,  S.M. Holland,  "The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016077.png" />-version of the Diliberto–Straus algorithm in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120160/d12016078.png" />"  ''Proc. Edinburgh Math. Soc.'' , '''27'''  (1984)  pp. 31–45</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  G. Aumann,  "Uber approximative nomographie II"  ''Bayer. Akad. Math. Natur. Kl. Sitzungsber.''  (1959)  pp. 103–109</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  N. Dyn,  "A straightforward generalization of Diliberto and Straus' algorithm does not work"  ''J. Approx. Th.'' , '''30''' :  4  (1980)  pp. 247–250</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  W.A. Light,  "The Diliberto–Straus algorithm in $L _ { 1 } ( X \times Y )$"  ''J. Approx. Th.'' , '''38''' :  1  (1983)  pp. 1–8</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a7]</td> <td valign="top">  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</td></tr></table>

Revision as of 17:02, 1 July 2020

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 _{\text{l}} ( S ) \otimes C ( T )$. Here, $\pi _ { k } ( T )$ is the subspace of $C ( T )$ consisting of all polynomials of degree at most $k$, and 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 , \text{l} \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_{\text{l}}( 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
How to Cite This Entry:
Diliberto-Straus algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Diliberto-Straus_algorithm&oldid=22355
This article was adapted from an original article by W. Light (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article