Rate of convergence of the discrete Pólya-1 algorithm (Q1318242)

Let \(V\) be a finite dimensional subspace of \(\mathbb{R}^ n\). The well-known \(p\)-norms \(|\cdot\|_ p\) \((1\leq p<\infty)\) and \(\| x\|_ \infty= \max_ i | x_ i|\) form a parameterized family of norms on \(\mathbb{R}^ n\). For \(1<p<\infty\) the \(p\)-norm \(\|\cdot \|_ p\) is strictly convex, so that for this \(p\) and \(z\in \mathbb{R}^ n\setminus V\) there is a unique best approximation \(x^ p\) in \(V\). The problem of the dependence on \(p\) of best approximations has been extensively studied. Of particular interest is the behavior of the arc \(x^ p\) as \(p\to\infty\) (resp. as \(p\to 1\)). In the literature such a limit is referred to as the Polya algorithm (resp. as the Polya-1 algorithm). In the subspace setting it is known that the Polya algorithm converges and that the rate of this convergence is \(O(1/p)\). The Polya-1 algorithm converges in a very general setting, but little is known about the rate at which the Polya-1 algorithm converges. In this paper the rate of convergence of the Polya-1 algorithm is studied. Examples are given to show that the rates derived are sharp.