## 2 Theory and Methodology
### Sparse Adaptive Leja Interpolation
#### 2.4.1 Generalized Sparse Grid Interpolation  
Given a multi-index set \(\Lambda\), the interpolation-based approximation of the multivariate input-output map \(g(\mathbf{y})\) reads:  
\[\mathcal{I}_{\Lambda}\left[g\right]\left(\mathbf{y}\right)=\sum_{\mathbf{i} \in\Lambda}\Delta_{\mathbf{i}}\left[g\right]\left(\mathbf{y}\right). \tag{11}\]  
We note that Equation (11) is not in general interpolatory, i.e., the interpolation property \(\mathcal{I}_{\Lambda}\left[g\right]\left(\mathbf{y}_{*}\right)=g\left( \mathbf{y}_{*}\right)\), where \(\mathbf{y}_{*}\) is a multivariate interpolation node, does not necessarily hold. The interpolation property holds only if \(\Lambda\) is a downward-closed set and the underlying univariate interpolation rules are based on nested nodes [6]. Downward-closed sets, also known as monotone or lower sets, satisfy the property:  
\[\forall\mathbf{i}\in\Lambda\Rightarrow\mathbf{i}-\mathbf{e}_{n}\in\Lambda, \forall n=1,2,\ldots,N,\text{ with }i_{n}>0, \tag{12}\]  
where \(\mathbf{e}_{n}\) denotes the unit vector in the \(n\)th dimension. If, additionally, the multi-index set \(\Lambda\) satisfies some sparsity constraint, then Equation (11) is a sparse interpolation formula, while the corresponding sparse grid is given by:  
\[Z_{\Lambda}=\bigcup_{\mathbf{i}\in\Lambda}Z_{\mathbf{i}}=\bigcup_{\mathbf{i} \in\Lambda}\left(Z_{1j_{1}}\times Z_{2j_{2}}\times\cdots\times Z_{Nj_{N}} \right).\]  
A commonly used sparsity constraint is:  
\[\Lambda=\left\{\mathbf{i}:\sum_{n=1}^{N}i_{n}\leq i_{\text{max}}\right\},\]  
resulting in the so-called isotropic sparse grids [5; 6]. Compared to full isotropic tensor grids, i.e., those given by:  
\[\Lambda=\left\{\mathbf{i}:\max_{n=1,\ldots,N}i_{n}\leq i_{\text{max}}\right\},\]  
the complexity of which is \(\mathcal{O}\left(m\left(i_{\text{max}}\right)^{N}\right)\), isotropic sparse grids delay significantly the curse of dimensionality, since their complexity is reduced to \(\mathcal{O}\left(m\left(i_{\text{max}}\right)\left(\log m\left(i_{\text{max}} \right)\right)^{N-1}\right)\)[45]. Nonetheless, isotropic sparse grids still grow exponentially with respect to the number of parameters.  
In most practical cases, the influence of the input parameters upon the QoI is anisotropic. For example, the QoI may be more sensitive to some parameters compared to others, in the sense that variations in the first set of parameters result in comparably greater variations in the QoI. Accordingly, the functional dependence of the QoI on a certain parameter might be significantly more difficult to approximate compared to another, e.g., a highly nonlinear versus a linear relation.  
The interpolation of Equation (11) can be constructed such that this anisotropy is represented in its terms, equivalently in the multi-indices comprising the set \(\Lambda\)[16; 17]. This is accomplished via an anisotropic refinement of the parameter space according to the contribution of each parameter to the interpolation accuracy. Compared to isotropic schemes, anisotropic interpolations typically result in great computational savings for the same approximation accuracy, or, equivalently, in greater interpolation accuracy for an equal cost. Since, in most cases, the parameter anisotropy cannot be a priori estimated in an accurate way [46], anisotropic interpolations are usually constructed using greedy, adaptive algorithms [18; 47; 48]. For the particular case of Leja nodes, such an algorithm is discussed in Section 2.4.2. Leja-based, adaptive, anisotropic sparse-grid interpolation algorithms are also available in [16; 30].