## 3 Reconstruction Algorithms
### Algorithm
Initialization:  Get the worst quality point and its index: \(\bullet\quad q^{\[i_{+}^{(n)}=\operatorname*{arg\,max}_{1\leq i\leq I^{(n)}-1}\{a_{i}^{(n)}\} \tag{8}\]

and adds a new point \(x_{\text{new}}\) at the middle of this biggest rectangle. Then, it computes a new data value \(y_{\text{new}}=G(x_{\text{new}},q_{\text{new}})\) with a new quality \(q_{\text{new}}\). In both cases, the numerical parameters \(q_{\text{new}}\) (for example several iterations, or the size of a sampling set or a population) are arbitrary and any value can be chosen in practice each time a new point \(x_{\text{new}}\) is added to the dataset. They can be increased arbitrarily as well each time such a new point has to be improved. Indeed, the numerical parameters \(q\) of the optimisation routine we have access to can be increased as much as desired, and increasing them will improve the estimates \(G(x,q)\) of the true function \(F^{\dagger}(x)\) uniformly in \(x\); see Assumption 1. The algorithm then verifies the consistency of the dataset by checking the quality of each point. If there is any inconsistent point, the algorithm computes a new value until obtaining consistency by improving successively the corresponding reliability. This is achieved in a finite number of steps starting from an inconsistent point and exploring the dataset from the left to the right. Finally, the algorithm updates the quality vector \(\{q_{i}^{(n+1)}\}_{i=1}^{I^{(n+1)}}\), the area vector \(\{a_{i}^{(n+1)}\}_{i=1}^{I^{(n+1)}}\), the worst quality \(q_{-}^{(n+1)}\) and the index \(i_{-}^{(n+1)}\) of the corresponding point, the biggest rectangle \(a_{+}^{(n+1)}\) and its index \(i_{+}^{(n+1)}\), and then the new weighted area WA\({}^{(n+1)}\). ### Proof of Convergence

We denote by \(I^{(n)}\) the number of data points, and \(\{x_{i}^{(n)},y_{i}^{(n)},q_{i}^{(n)}\}_{i=1}^{I^{(n)}}\) the positions of the data points, the observations given by the optimization algorithm at these positions, and the qualities associated with the optimization algorithm at the step \(n\) of Algorithm 1. For each \(i=1,\dots,I^{(n)}-1\), we define \(s_{i}^{(n)}=[x_{i}^{(n)},x_{i+1}^{(n)}]\subset[a,b]\) and the vector containing all rectangle areas \(\{a_{i}^{(n)}\}_{i=1}^{I^{(n)}-1}\) by:

\[a_{i}^{(n)}=(x_{i+1}^{(n)}-x_{i}^{(n)})\times(y_{i+1}^{(n)}-y_{i}^{(n)})\,. \tag{9}\]

The pointwise observation \(y_{i}^{(n)}=G(x_{i}^{(n)},q_{i}^{(n)})\) is thus associated with the quality \(q_{i}^{(n)}\in\mathbb{R}_{+}\), which quantifies the confidence we have in this observation as outlined in the problem description in Section 2. This number can represent the inverse error achieved by the optimization algorithm, for example, or the number of iterations, or the number of individuals in a population, or any other numerical parameter pertaining to this optimization process. The higher it is, the closer the observation is to the true target value. Therefore we consider the following assumption on the numerical process \(G\). **Assumption 1**. : \(G(x,q)\) _converges to \(F^{\dagger}(x)\) as \(q\to+\infty\) uniformly in \(x\in[a,b]\), that is:_

\[\forall\epsilon>0\,,\ \exists Q>0\text{ such that }\forall q\geq Q\,,\ \forall x\in[a,b]\,,\ \Big{|}G(x,q)-F^{\dagger}(x)\Big{|}\leq\epsilon\,.\]

Moreover, we can guarantee that:

\[\forall x\in[a,b]\,,\quad\forall q\in\mathbb{R}_{+}\,,\quad G(x,q)\leq F^{ \dagger}(x). \tag{10}\]

That is, the optimisation algorithm will always underestimate the true value \(F^{\dagger}(x)\). In this way, one can model the relationship between the numerical estimate \(G\) and the true value \(F^{\dagger}\) as:

\[\forall x\in[a,b]\,,\quad\forall q\in\mathbb{R}_{+}\,,\quad G(x,q)=F^{\dagger }(x)-\epsilon(x,q)\,, \tag{11}\]

where \(\epsilon\) is a positive random variable. These assumptions imply some robustness and stability of the algorithm we use. In the following, we will assume that \(I^{(0)}\geq 2\). That is, we have at least two data points at the beginning of the reconstruction algorithm.