Full recovery from point values: an optimal algorithm for Chebyshev approximability prior (Q6171716): Difference between revisions

The author succeeds in making the claim in the title of the paper come true: the construction of an optimal algorithm for full recovery from point values. Of course (``there is no such thing as a free lunch''), some restrictions on generality have to be posed. The mathematical setting is here: -- \(C(\mathcal{X})\) is a space of continuous functions on a compact set \(\mathcal{X}\), -- the norm used is the uniform norm on \(C(\mathcal{X})\) \[\| f\|_{C(\mathcal{X})} = \max\{|f(x)|,x\in \mathcal{X}\}.\] -- the unknown function \(f\in C(\mathcal{X})\) is observed using point values in \(x^{(i)}\in\mathcal{X}\) \[y_i=f(x^{(i)}),\ i\in \{1,\ldots,m\},\] -- \(f\) is to be restricted to a nodal set \(\mathcal{K}\), -- the recovery procedure ia a map \(\Delta\) from \(\mathbb{R}^m\) into \(C(\mathcal{X})\), viewed through its worst-case error \hphantom{- }over \(\mathcal{K}\) \[\hbox{wce}_{\mathcal{K}}(\Delta)= \sup_{f\in\mathit{K}} \| f-\Delta ([f(x^{(i)});\ldots;f(x^{(m)})]\|_{C(\mathcal{X})}.\] The problem to construct an \textit{optimal recovery procedure} that minimizes \(\hbox{wce}_{\mathcal{K}}(\Delta)\), is of course, too general: one has to use a restriction. The author chooses, given a subset \(\mathcal{V}\) of \(C(\mathcal{X})\) and a parameter \(\varepsilon\geq 0\), the approximation model \[ \mathcal{K}_{\mathcal{V},\varepsilon}=\{f\in C(\mathcal{K})\,:\,\hbox{dist}_{C(\mathcal{K}}(f,\mathcal{V})\leq \varepsilon\}. \] The result is then given in Algorithm 1 in \S2, written in standard programming terms (using for\(\ldots\)end for statements). It is, however, not possible to reproduce the algorithm in full within the space of an ordinary review, but this reviewer urges those who are working in the area to pursue the paper in detail; it is worth it! The layout of the paper is as follows: \S1. Problem setting (\(1\) page) \S2. Description of an optimal algorithm (\(1\) page) \S3. Reminders of Chebyshev spaces (\(1\) page) \S4. Reminders on optimal recovery (\(3\) pages) \S5. Validation of the proposed algorithm (\(3\) pages) \S6. Concluding remarks (\(3\) pages) Puts the results found in perspective. References (\(16\) items)