\section{Introduction}
\label{sec:intro}

Computer modelling is used in nearly every field of science and engineering. Often, these computer codes model complex phenomena, have many input parameters, and are \changed{expensive} to evaluate.
In order to explore the behavior of the model under uncertainty (e.g., uncertainty propagation, parameter calibration from data or sensitivity analysis), many model runs are required. However, if the model is costly, only a few model evaluations can be afforded, which often do not suffice for thorough uncertainty quantification.
In engineering and applied sciences, a popular work-around in this situation is to construct a surrogate model.
A surrogate model is a cheap-to-evaluate proxy to the original model, which typically can be constructed from a relatively small number of model evaluations and approximates the input-output relation of the original model well.
Since the surrogate model is cheap to evaluate, uncertainty quantification can be performed at a low cost by using the surrogate model instead of the original model.
Therefore, surrogate modelling aims at constructing a metamodel that provides an accurate approximation to the original model while requiring as few model evaluations as possible for its construction.

In this article, we focus on \textit{nonintrusive regression-based sparse polynomial chaos expansions} (PCE), which is a popular surrogate modelling technique, and within the last decade is has received attention from the communities of applied mathematics and engineering.
PCE express the computational model in terms of a basis of polynomials orthonormal with respect to the input random variables \citep{Xiu2002} and work well for globally smooth problems, which are common in many engineering applications. In addition to being a surrogate model, PCE are also often used for uncertainty propagation and sensitivity analysis, since moments and Sobol' sensitivity indices can be computed analytically \citep{SudretRESS2008b}.
\textit{Nonintrusive} PCE treat the model as a black box (unlike intrusive PCE commonly used for solving stochastic PDEs).
It is often advantageous to compute a \textit{sparse PCE}, which is an expansion for which most coefficients are zero. This can be justified by the \textit{sparsity-of-effects principle} and by \textit{compressibility}:
The sparsity-of-effects principle is a heuristic stating that most models describing physical phenomena are dominated by main effects and interactions of low order \citep{Montgomery:2004}.
Furthermore, PCE of real-world models are usually either sparse or at least compressible, meaning that the PCE coefficients, sorted by magnitude, decay quickly.
Additional advantages of sparse expansions are given in Section \ref{sec:sparsePCEdescription}.

Within the last decade, a large number of articles has been published on the topic of regression-based sparse PCE, each containing promising improvements on how to perform sparse PCE but often lacking a thorough comparison to previously published methods.
In this work, we survey the state-of-the-art literature, develop a general framework into which the various approaches can be fit, and carry out a numerical benchmark of a selection of methods to assess which of the many sparse PCE methods perform best on a representative set of realistic benchmark \changed{models}.

The paper is structured as follows. Section~\ref{sec:sparsePCE} contains the description of our framework for classifying the sparse PCE literature as well as the extensive literature review.
Section~\ref{sec:benchmark} contains the benchmark description and the numerical results. Finally, conclusions are drawn in section~\ref{sec:conclusion}. More detailed descriptions of selected sparse solvers and experimental design techniques are given in the Appendices using unified notation.

\section{Framework and literature survey for sparse polynomial chaos expansions}
\label{sec:background}
\label{sec:sparsePCE}

\subsection{Regression-based polynomial chaos expansions}
\label{sec:PCE}

Let $\ve X$ be a $d$-dimensional random vector on a domain ${\mathcal D} \subset \mathbb{R}^d$ with independent %
components and probability density function $f_{\ve X}(\ve x) = \prod_{i=1}^d f_{X_i}(x_i)$.
Let $L_{f_{\ve X}}^2({\mathcal D})$ be the space of all scalar-valued
models with finite variance under $f_{\ve X}$, i.e.,
$
L_{f_{\ve X}}^2({\mathcal D}) = \{ h: {\mathcal D} \to \mathbb{R} \ | \ \Vare{\ve X}{h(\ve X)} < + \infty \}
$.
Under certain assumptions on the input distribution $f_{\ve X}$ \citep{Xiu2002,Ernst2012}, there exists a polynomial orthonormal basis $\{\psi_{\ve{\alpha}}: {\ve{\alpha}} \in \mathbb{N}^d\}$ for $L_{f_{\ve X}}^2({\mathcal D})$. Since the components of $\ve X$ are assumed to be independent, the basis elements are products of univariate orthonormal polynomials and are characterized by the multi-index ${\ve{\alpha}} \in \mathbb{N}^d$ of polynomial degrees in each dimension.

We consider a particular model ${\mathcal M} \in L_{f_{\ve X}}^2({\mathcal D})$
and denote by $Y = {\mathcal M}(\ve X)$ the corresponding output random \changed{variable}.
$Y$ can be represented exactly through an infinite expansion in $\{\psi_{\ve{\alpha}}: {\ve{\alpha}} \in \mathbb{N}^d\}$.
In practice, however, not all infinitely many coefficients can be computed, and we are interested in a truncated expansion
\begin{equation}
Y = {\mathcal M}(\ve X) \approx {\mathcal M}^\text{PCE}(\ve X) = \sum_{{\ve{\alpha}} \in {\mathcal A}} c_{\ve{\alpha}} \psi_{\ve{\alpha}}(\ve X)
\end{equation}
whose accuracy depends on the choice of the finite set ${\mathcal A} \subset \mathbb{N}^d$ (i.e., on the basis elements used for the expansion) as well as on the coefficients $c_{\ve{\alpha}}$.
Several truncation techniques are described in Section~\ref{sec:basis}.

To compute the coefficients, one well-known and practical approach is regression \citep{Isukapalli, Berveiller2006}%
\footnote{Other, earlier approaches for computing the coefficients are stochastic Galerkin and stochastic collocation methods \citep{Ghanembook1991, Xiu:Hesthaven:2005, Shen2020}. For a comparison of their performance to regression-based PCE, see, e.g., \citet{BerveillerThesis,Hosder2007,Doostan2011,Mathelin2012}.}%
.
The basic regression approach is \textit{ordinary least squares} (OLS).
Let $\{\ve x^{(k)}\}_{k=1}^{N} \subset {\mathcal D}$ be a sample of the input space called \textit{experimental design} (ED). Let $\ve y = (y^{(1)}  , \, \dots \,, y^{(N)})^T$ be the vector of model responses with $y^{(k)} = {\mathcal M}(\ve x^{(k)})$. Define the matrix of basis function evaluations $\ve \Psi$ with entries $\Psi_{ij} = \psi_{j}(\ve x^{(i)})$, where the basis functions are enumerated in an arbitrary way.
Denoting the number of basis functions with $P$, we see that the \textit{regression matrix} $\ve\Psi$ is an $N \times P$-matrix.
Then, the OLS regression problem can be written as
\begin{equation}
\hat{\ve c} = \arg\min_{\ve c \in \mathbb{R}^P} \norme{\ve \Psi \ve c - \ve y}{2}.
\label{eq:OLS}
\end{equation}
For a unique and robust solution, a heuristic number of model evaluations is $N \approx 2P,3P$ \citep{Hosder2007,FajraouiMarelli2017}, which can be infeasible for high-dimensional or high-degree PCE approximations.

\subsection{Sparse PCE}
\label{sec:sparsePCEdescription}

Sparse coefficient vectors are determined through \textit{sparse regression}, which, in addition to a good regression fit, requires that the solution be sparse.
This constraint on sparsity is realized e.g.\ by adding as a regularization term the $\ell^0$-``norm'' or the $\ell^1$-norm of the coefficient vector to the OLS formulation of \eqref{eq:OLS} (see Appendix \ref{app:solvers} for more details).
Many sparse regression methods used in PCE were originally developed in the context of compressive sensing \citep{Donoho2006, Candes2006}.
For an introduction to the concepts and ideas of compressive sensing, see, e.g., \citet{Candes2008a, Bruckstein2009, Kougioumtzoglou2020}.

Unlike OLS, compressive sensing methods allow one to use fewer design points $N$ than basis functions $P$ and still recover the true sparse solution, or find a good sparse approximation to it.
This and its robustness to noise, both of which are induced by the sparsity constraint, are the main reasons why sparse PCE are preferred to full PCE in practical settings when the number of model evaluations necessary for OLS-based PCE would be infeasible to compute.
Note that while the use of sparse PCE for engineering models can be justified by compressibility and the sparsity-of-effects heuristic (section \ref{sec:intro}), the main goal in sparse PCE is to compute a good surrogate model from a few model evaluations and not to find the sparsest possible expansion.
The assumption of sparsity is used as a tool for finding robust solutions to underdetermined systems of linear equations.

The first publications on sparse regression-based PCE proposed greedy forward-backward selection algorithms \citep{BlatmanCras2008, BlatmanPEM2010} and introduced the LARS algorithm for sparse PCE \citep{BlatmanJCP2011}. On the mathematical side, \citet{Doostan2011} analyzes convergence properties for sparse Legendre PCE when the design points are sampled from the uniform distribution.
Another early work is \citet{Mathelin2012} demonstrating that sparse PCE are less costly and more accurate than PCE based on Smolyak sparse grids.
Since then, a large number of articles has been published on the topic of sparse PCE suggesting new methods for specific aspects of the sparse regression procedure. In the following, we present a framework into which the existing literature can be fit. The framework provides an overview of the available choices and enables a structured comparison of their impact on the performance of the resulting sparse PCE. Naturally, some new combinations of methods arise that have not yet been considered in the literature.

\subsection{Framework: Classifying the literature on sparse PCE}
\label{sec:framework}
Here, we present the framework we developed in order to gain an overview of the extensive literature proposing new methods for computing sparse PCE.
Figure~\ref{fig:framework} shows a sketch of this framework. To compute a sparse PCE, the first step is to choose a set ${\mathcal A}$ of candidate polynomials for the expansion (Section \ref{sec:basis}) as well as an experimental design (Section \ref{sec:ED}).
The experimental design defines the locations of the model evaluations.
Once the model evaluations are obtained, the sparse solution can be computed by applying a sparse regression solver (see Section \ref{sec:solvers}). This solver often depends on a number of hyperparameters that have to be selected carefully in order to get good results.
Then, a suitable model selection criterion is evaluated (Section \ref{sec:modelselection}). If the obtained solution is satisfactory, the process can be stopped.
Otherwise, the basis can be adapted (usually augmented; see Section~\ref{sec:basis}), and/or the experimental design can be enriched (see Section~\ref{sec:EDenrichment}).
This process is repeated until the value of the model selection criterion either is satisfactory or cannot be reduced.

In addition to the components shown in Figure~\ref{fig:framework}, there are methods (we call them \textit{enhancements}) that aim at generally improving the solution to the sparse regression problem by, e.g., adapting the input space or preconditioning the regression matrix. They are discussed in Section~\ref{sec:enhancements}.

\begin{figure}
	\centering
	\includegraphics[width=.5\textwidth]{M131577_Fig1.pdf}
	\caption{Framework for computing sparse PCE. For each component of the framework, a number of methods has been proposed in the literature. In the first part (section~\ref{sec:background}) of this paper, we review the literature for each of the components. Details on selected methods are given in Appendices \ref{app:ED} and \ref{app:solvers}. In the second part (section~\ref{sec:benchmark}), we conduct a benchmark of selected methods for the components marked in orange, performing a single iteration of the framework. Iterative basis adaptation and experimental design enrichment are not considered in this work and are left for future benchmarks.}
	\label{fig:framework}
\end{figure}

\subsection{Choice of basis and basis adaptation}
\label{sec:basis}
\label{sec:iterativealgs}

The approximation quality of a truncated PCE hinges on the polynomial functions available for building the surrogate model, which are characterized by the associated set of multi-indices ${\mathcal A} \subset \mathbb{N}^d$.
We call the finite set of polynomials $\{\psi_{\ve{\alpha}}: {\ve{\alpha}} \in {\mathcal A}\}$ included in the current truncated PCE model \textit{basis} and call its members \textit{candidate polynomials} or \textit{candidate basis functions}.
A sparse PCE algorithm will find nonzero coefficients only for a subset ${\mathcal A}^\text{active} \subset {\mathcal A}$ of the basis functions, which we call \textit{active basis functions}.
On the one hand, ${\mathcal A}$ should include enough candidate polynomials to facilitate a good approximation. On the other hand, unnecessary basis functions decrease the ratio $N/P$ of model evaluations to unknown coefficients and
deteriorate the regression matrix.
Therefore, it is beneficial to carefully select the polynomials to be included in the expansion.

The choice of basis is often motivated by the \textit{sparsity-of-effects principle}, a heuristic guideline stating that most real-world models are well approximated by terms of low degree and low interaction order.
The following are popular ways to construct a basis:
\begin{itemize}
	\item \textit{Total-degree} A total-degree basis of degree $p$ is defined by
	$ {\mathcal A}^p = \{{\ve{\alpha}}: \norme{{\ve{\alpha}}}{1} \leq p \} $.
	\item \textit{Hyperbolic truncation}
	Let $p$ be fixed. Define the q-norm-truncated basis
	\begin{equation}
	{\mathcal A}^{p,q} = \{ {\ve{\alpha}}: \norme{{\ve{\alpha}}}{q} \leq p \}
	\end{equation}
	with $q \in (0,1]$ \citep{BlatmanJCP2011} \changed{and the quasi-norm $\norme{\ve x}{q} = \left(\sum_{i=1}^d|x_i|^q\right)^{\frac{1}{q}}$}. For $q = 1$, \changed{${\mathcal A}^{p,1}$} is the total-degree basis of order $p$. For smaller $q$, this truncation scheme excludes terms with high interaction order while keeping univariate polynomials up to degree $p$.
	\item \textit{Interaction order}
	The interaction order of the basis can be restricted by defining
	\begin{equation}
	{\mathcal A}^{p, r} = \{{\ve{\alpha}} \in {\mathcal A}^p: \#\{i:\alpha_i \neq 0, i = 1  , \, \dots \,, d\} \leq r\}
	\end{equation}
	\citep{BlatmanCras2008,UQdoc_13_104}.
	This is useful for reducing the number of basis functions especially in high dimensions and when it is known (e.g., for physical reasons) that only a certain number of variables might interact.
\end{itemize}

Instead of using a fixed basis ${\mathcal A}$, it can be beneficial to employ an iterative scheme which starts from a small set of basis functions (low-dimensional, low-order) and, after computing a sparse solution, repeatedly adapts the basis by including a set of the most promising candidate polynomials and possibly removing others. This is called \textit{basis adaptivity} (not to be confused with Gaussian adaptation \citep{Tipireddy2014}; see also Section \ref{sec:enhancements}).

A simple instance of basis adaptivity is \textit{degree adaptivity} \citep{BlatmanPEM2010}, which is based on total-degree bases. The procedure starts with a basis of low total degree and iteratively increases the total degree of the basis.
Finally, a model selection criterion is used to select the best basis and associated sparse solution.
Similarly, q-norm and interaction order, or a combination of all three, can also be used to design a basis adaptation scheme \citep{BlatmanPEM2010,BlatmanJCP2011}.
This basis adaptivity is solution-agnostic in the sense that it does not use any information from the solutions computed in previous runs for the augmentation of the basis.
Another solution-agnostic method is the dimension- and order-incrementing algorithm of \citet{Alemazkoor2017}.
Two methods that adapt the basis based on the active terms of the previous sparse solution are \changed{forward neighbor basis adaptivity}
\changed{\citep{Sargsyan2014, Jakeman2015}} and \changed{anisotropic degree basis adaptivity}
\citep{Hampton2018}.
These approaches keep the size of the basis small by strictly controlling which functions are added to the basis, often starting with a constant surrogate model and adding dimensions only when necessary.
A discussion and benchmark of basis-adaptive methods for sparse PCE is available in \citet{LuethenIJUQ2021}.

\subsection{Experimental design}
\label{sec:ED}

Generally, experimental design techniques aim to select points in order to achieve certain goals related to exploration of the space (space-filling design), or to achieve certain properties of the regression matrix such as (in expectation) orthonormal columns, small determinant, small condition number, etc.
For regression-based PCE, there are several main classes of experimental design techniques:
\begin{itemize}
	\item \textit{Sampling based on the input distribution.} The samples are drawn from the input distribution. Techniques like Latin hypercube sampling (LHS) can be used to improve the space-filling properties.
	\item \textit{Sampling from a different distribution} \changed{(also called \textit{induced sampling} \citep{Guo2020}).} A different distribution and associated basis are constructed that have better properties than the input distribution and its basis.
	\item \textit{Choosing points according to an optimality criterion from a candidate set.} Certain properties of the regression matrix are optimized by choosing the design points from a suitable candidate set.
\end{itemize}
Note that none of these sampling methods considers the evaluations $\ve y$ of the computational model.
For model-aware sampling techniques (active and supervised learning), see Section \ref{sec:EDenrichment}.

The following sections contain an overview of available sampling methods for sparse PCE. Selected experimental design techniques are described in more detail in Appendix \ref{app:ED}.
Note that due to the large amount of literature on experimental design for sparse PCE, our review cannot be exhaustive. There are many more approaches available, including the deterministic Weil points \citep{Zhou2014}, sparse grids \citep{Perko2014}, randomized or subsampled quadrature points \citep{Berveiller2006, Tang2014, Guo2017}, etc.

\subsubsection{Sampling based on the input distribution}
The most basic sampling method is Monte Carlo (MC) sampling, where the points are sampled independently from the input distribution \citep{Doostan2011,Hampton2015}.
LHS \citep{McKay1979} aims at distributing the design points in a more space-filling way than MC sampling, using a stratification of the input quantile space in each dimension.
LHS is known to filter main effects; i.e., it reduces the variance of linear regression estimators when the quantity of interest is dominated by terms of interaction order one \citep{Shields2016}.
LHS with sample decorrelation can further reduce the variance \citep{Owen1994}.
LHS can also be used together with a criterion such as maximin distance (maximize the minimal distance between the design points in quantile space) \citep{Pronzato2012}, where several LHS designs are generated and the one that optimizes the criterion is returned.

A generalization of LHS that combines it with stratified sampling is \textit{Latinized partially stratified sampling} \citep{Shields2016}, which filters both main effects and low-order interaction terms and has been shown to consistently outperform LHS in high-dimensional cases.

Other space-filling/low-discrepancy methods are Sobol' sequences \citep{Sobol1967} and Halton sequences \citep{Halton1960}, which are deterministic but appear to be quasi-random and space-filling in low dimensions.

\subsubsection{Sampling from a different distribution}
Several methods consider the \textit{coherence} parameter of a basis, defined by
\begin{equation}
\mu({\mathcal A}, \{\psi_{\ve{\alpha}}\}) = \sup_{\ve x \in {\mathcal D}} \max_{{\ve{\alpha}} \in {\mathcal A}} |\psi_{\ve{\alpha}}(\ve x)|^2,
\label{eq:coherence}
\end{equation}
which can be used to bound the number of samples needed for accurate recovery by $\ell^1$-minimization \citep{Candes2011, Hampton2015}.
For Hermite and Legendre polynomial bases, the coherence parameter of a total-degree basis grows exponentially with the total degree $p$ \citep{Rauhut2012,Yan2012,Hampton2015}.

To construct a \textit{coherence-optimal design}, a new probability distribution and its associated orthonormal basis are constructed that achieve minimal coherence \citep{Hampton2015, Hampton2015b}.
The new basis can be derived from the original PCE basis by multiplying each member by a weight function.
Coherence-optimal samples can be drawn by Markov Chain Monte Carlo (MCMC) \citep{Hampton2015} or by rejection sampling (see section~\ref{app:coh-opt-rejection}).
A related sampling scheme is obtained by constructing a new probability distribution and associated orthonormal basis which have improved but not optimal coherence; however, the distribution is constructed to belong to some classical family and is therefore straightforward to sample. This is called \textit{asymptotic sampling} \citep{Hampton2015, Hampton2015b} and results in a Chebyshev distribution for uniform input, and in a uniform distribution (within a ball of degree-dependent radius) for Gaussian input.
Numerical experiments confirm the expected performance gain of coherence-optimal sampling over both MC and asymptotic sampling, and of asymptotic sampling over MC in the case of low dimension $d$ and high total degree $p$. For high-dimensional problems with low degree, MC often performs better than asymptotic sampling \citep{Hampton2015}.

The so-called \textit{Christoffel sparse approximation (CSA)} \changed{\citep{Jakeman2017,Narayan2017,Cohen2017}} is a related approach which constructs a new orthonormal basis that minimizes the quantity
\begin{equation}
\tilde\mu({\mathcal A}, \{\psi_{\ve{\alpha}}\}) = \sup_{\ve x \in {\mathcal D}} \left(\frac{1}{|{\mathcal A}|} \sum_{{\ve{\alpha}} \in {\mathcal A}} |\psi_{\ve{\alpha}}(\ve x)|^2\right)^\frac12.
\label{eq:CSA_coherence}
\end{equation}
As for coherence-optimal sampling, the new basis can be derived from the original basis by multiplying each member by a weight function, which results in a weighted regression problem.
The corresponding probability distribution is chosen to be the so-called \textit{weighted pluripotential equilibrium measure}, which for bounded distributions is the Chebyshev distribution.
For one-dimensional Gaussian input, this measure is a symmetric Beta distribution with degree-dependent bounds.

Note that all three sampling methods described in this section introduce weights and therefore modify the objective function into a weighted regression problem $ \ve W \ve \Psi \ve c \approx \ve W \ve y$. Since the objective function belongs to the scope of the solver, these methods cannot be considered as pure sampling methods in the sense of being completely independent of the solver.

\subsubsection{Choosing points according to an optimality criterion from a candidate set}
The following methods choose points from a candidate set in order to optimize properties of the regression matrix. Candidate points can be sampled, e.g., using MC, LHS \citep{FajraouiMarelli2017}, coherence-optimal sampling \citep{Diaz2018, Alemazkoor2018}, or Christoffel sampling \citep{Shin2016b}. Note that some of these methods introduce weights, resulting in a weighted regression problem. The candidate set can have a large influence on the resulting design.

\begin{itemize}
	\item \textit{D-optimal sampling} aims at maximizing the determinant
	$
	D(\ve \Psi) = \det(\frac1N \ve \Psi^T \ve \Psi)^\frac1P
	$
	of the information matrix \citep{Kiefer1959}. Note that $D(\ve \Psi) = 0$ if $N < P$.
	Maximizing the D-value is connected to minimizing the variance of the coefficients of the PCE estimate \citep{Zein2013}.
	Algorithms for D-optimal designs include greedy augmentation \citep{Dykstra1971}, exchange techniques \citep{Fedorov2013, Cook1980, Nguyen1992, Zein2013},
	maxvol \citep{Mikhalev2018}, gradient descent \citep{Zankin2018}, and rank-revealing QR decomposition (RRQR)/subset selection \citep{Diaz2018, Gu1996}.
	The advantage of the last method is that it can also be applied for wide matrices $\ve\Psi \in \mathbb{R}^{N \times P} $ where $N < P$.

	\item \textit{S-optimal sampling} (also called ``quasi-optimal'' in \citet{Shin2016a}) selects samples from a large pool of candidate points so that the PCE coefficients computed using the selected set are as close as possible to the coefficients computed from the whole set of candidate points \citep{Shin2016a}.
	The S-value is defined by%
	\footnote{This definition assumes that the columns of the matrix $\ve\Psi_\text{cand}$, containing the evaluations of all candidate points, are mutually orthogonal.}
	\begin{equation}
	S(\ve\Psi) = \left( \frac{\sqrt{\det \ve\Psi^T \ve\Psi}}{\prod_{i=1}^P \norme{\Psi_i}{2}} \right)^{\frac1P}
	\end{equation}
	where $\Psi_i$ denotes the $i$th column of the regression matrix. Its maximization has the effect of maximizing the column orthogonality of the regression matrix while at the same time maximizing the determinant of the information matrix \citep{Shin2016a}.
	Note that $S(\ve\Psi) = 0$ if $N < P$.
	An S-optimal experimental design can be computed using a greedy exchange algorithm \citep{Shin2016a, Shin2016b, FajraouiMarelli2017}.

	\item \textit{Near-optimal sampling} simultaneously minimizes the two matrix properties \textit{mutual coherence} and \textit{average cross-correlation} \citep{Alemazkoor2018}, both of which quantify the correlation between normalized columns of the regression matrix
	(see section~\ref{sec:near-opt} for the definitions of these properties).
	A near-optimal design can be built by a greedy algorithm \citep{Alemazkoor2018}.
	Note that for near-optimal sampling, it is not necessary that $N \geq P$\changed{, since this method does not rely on the determinant of the information matrix}.

\end{itemize}

\subsubsection{Sequential enrichment of the experimental design}
\label{sec:EDenrichment}
Instead of sampling the whole experimental design at once, it has been proposed to use \textit{sequential enrichment}.
Starting with a small experimental design, additional points are chosen based on the last computed sparse PCE solution or on an augmented basis.
In the context of machine learning, sequential sampling is also known as \textit{active learning} \citep{Settles2012}.
Sequential enrichment has been proposed in the context of S-optimal sampling \citep{FajraouiMarelli2017}, D-optimal sampling \citep{Diaz2018}, and coherence-optimal sampling \citep{Hampton2018}.
\citet{Zhou2019b} suggest an enrichment strategy based on approximations to the expected quadratic loss function, i.e., the mean-squared error. \citet{Ji2008} and \citet{Seeger2008} propose choosing points that minimize the differential entropy of the posterior distribution of the coefficients (using a Bayesian regression setting).
In all cases, numerical examples show that the sequential strategy generally leads to solutions with a smaller validation error compared to nonsequential strategies.
Due to the complexity of the topic and the already large extent of our benchmark, this strategy, albeit promising, is not explored further in this paper.

\subsection{Solution of the minimization problem}
\label{sec:solvers}

There are many formulations of the regression problem that lead to a sparse solution, such as $\ell^0$-minimization, $\ell^1$-minimization (basis pursuit denoising (BPDN), LASSO), $\ell^1-\ell^2$ minimization, Bayesian methods, etc.\ (see also Appendix \ref{app:solvers}).
Based on these formulations, a vast number of sparse solvers has been proposed in the compressed sensing literature; see, e.g., \citet{carronWebsite} and the surveys of \citet{Qaisar2013, Zhang2015c, Arjoune2017}.
We focus here on solvers that have been proposed in the context of sparse PCE.
Of course, it is straightforward to use any other sparse solver to compute a sparse PCE.

The following solvers have been proposed in the sparse PCE literature:
\begin{itemize}
	\item \textit{Convex optimization solvers.}
	$\ell^1$-minimization in its various formulations is a (constrained) convex optimization problem.
	Least angle regression (LARS) \citep{Efron2004, BlatmanJCP2011,UQdoc_13_104} is an iterative method that adds regressors one by one according to their correlation with the current residual, and updates the coefficients following a least angle strategy. With the LARS-LASSO modification, which allows for backwards elimination of regressors, LARS is able to generate the whole LASSO path \citep{Efron2004}. Unmodified LARS can also be classified as a greedy method.
	SPGL1 \citep{Vandenberg2008, SPGL1} solves the BPDN formulation by solving a succession of LASSO instances using the spectral projected gradient (SPG) method.
	Other solvers belonging to this class are e.g.\ the solvers implemented in $\ell_1$magic \citep{L1Magic} and SparseLab \citep{SparseLab}.

	\item \textit{Greedy methods} are variants of stepwise regression where the regressors are added to the model one by one according to some selection criterion, aiming at finding a heuristic solution to the intractable $\ell^0$-minimization formulation.
	Orthogonal matching pursuit (OMP) \citep{Tropp2007,Doostan2011,UQdoc_13_104} is a classical forward selection algorithm in which orthonormalized regressors are added to the model one by one according to their correlation with the residual, and the coefficients are computed by least-squares. \citet{Baptista2019} suggests extensions to OMP such as parallelization, randomization and a modified regressor selection procedure.
	Subspace pursuit (SP) \citep{Dai2009, Diaz2018, SPcode} is an iterative algorithm that repeatedly uses least squares on a subset of regressors.
	LARS \citep{Efron2004, BlatmanJCP2011} without the LASSO modification (allowing for removal of regressors) can also be classified as a greedy method.
	Another greedy method is ranking-based sparse PCE \citep{Tarakanov2019} which employs batch updating, coordinatewise gradient descent of the elastic net formulation, and a correlation- and stability-based ranking procedure for the regressors.
	Many more greedy stepwise regression techniques have been proposed, utilizing various selection criteria, solvers, and stopping criteria. An overview of methods following this scheme is given in section~\ref{app:greedystepwise}.

	\item \textit{Bayesian compressive sensing (BCS)} (a.k.a.\ sparse Bayesian learning) is a class of methods that use a Bayesian setting to find a sparse solution. They impose a sparsity-inducing prior on the coefficients, whose parameters are again considered to be random variables with a hyperprior \changed{\citep{Tipping2001,Ji2008,Sargsyan2014,Tsilifis2020}}. The solution is typically the maximum a posteriori estimate of the coefficients and can be computed e.g.\ by differentiation \citep{Tipping2001}, expectation-maximization \citep{Figueiredo2003, Wipf2004b}, expectation-propagation \citep{Seeger2008}\changed{, variational inference \citep{Tsilifis2020, Bhattacharyya2020}}, or a fast approximate algorithm \citep{Faul2002, Tipping2003}.
	An extension called FastLaplace with an additional layer of hyperparameters has been proven to attain even sparser solutions \citep{Babacan2010, FastLaplace}.
	A greedy algorithm using the Bayesian setting to select the regressors is the greedy Bayesian Kashyap information criterion (KIC)-based algorithm \citep{Shao2017}.

	\item \textit{Iteratively reweighted methods.}
	Iteratively reweighted $\ell^1$-minimization uses the coefficients computed in a previous iteration to
	construct a weighted $\ell^1$-minimization problem \citep{Candes2008b, Yang2013}.
	\citet{Cheng2018b} suggest an iterative reweighted method with D-MORPH regression \citep{Li2010} as its computational core, which is a technique that follows a certain path, defined by a quadratic objective function, on the manifold of solutions to the underdetermined system.

\end{itemize}

Each of the solvers mentioned above features one or more hyperparameters whose values must be calibrated. This is usually done by cross-validation. Popular choices are leave-one-out (LOO) cross-validation (accelerated for least-squares solutions) \citep{BlatmanPEM2010, BlatmanJCP2011}, LOO cross-validation with a modification factor for small sample sizes \citep{Chapelle2002, BlatmanJCP2011}, and $k$-fold cross-validation
\citep{Doostan2011,Jakeman2015,Huan2018}.

Selected sparse regression solvers are described in more detail in Appendix \ref{app:solvers}.

\subsection{Model selection criterion}
\label{sec:modelselection}
\label{sec:crossvalidation}

To decide whether to continue iterating in the framework or stop the process, we need to assess how well the current sparse solution performs.
Our main quantity of interest is the \textit{generalization error}, which quantifies the mean-square accuracy of the surrogate.
It is given by
\begin{align}
E_\text{gen} = \Espe{\ve X}{\left( {\mathcal M}(\ve X) - {\mathcal M}^\text{PCE}(\ve X) \right)^2}
\label{eq:generalizationerror}
\end{align}
where ${\mathcal M}$ is the computational model, $\ve X$ is the random input vector, and ${\mathcal M}^\text{PCE}$ is the sparse PC surrogate.

The generalization error can be approximated by the \textit{validation error}, which is the MC estimate of \eqref{eq:generalizationerror} on a validation set $\{(\ve x^{(i)}_\text{\tiny val}, y^{(i)}_\text{\tiny val}): \ve x^{(i)}_\text{\tiny val} \sim_\text{i.i.d.} f_{\ve X}, y^{(i)}_\text{\tiny val} = {\mathcal M}(\ve x^{(i)}_\text{\tiny val}), i=1 , \, \dots \,, N_\text{val}\}$.
To make the validation error independent of the scaling of the model, it is convenient to use the \textit{relative mean-squared error} defined by
\begin{align}
\text{RelMSE} = \frac{\sum_{i=1}^{N_\text{val}} (y^{(i)}_\text{\tiny val} - {\mathcal M}^\text{PCE}(\ve x^{(i)}_\text{\tiny val}))^2}{\sum_{i=1}^{N_\text{val}} (y^{(i)}_\text{\tiny val} - \bar{y})^2}
\label{eq:RelMSE}
\end{align}
where $\bar{y} = \frac{1}{N_\text{val}} \sum_{i=1}^{N_\text{val}} y^{(i)}_\text{\tiny val}$.

The best surrogate model ${\mathcal M}^\text{PCE}$ (defined by ${\mathcal A}$ and $\ve c$) is the one that has the smallest generalization error.
In practical applications, the generalization error typically cannot be computed, and a large validation set is not available due to computational constraints.
Instead, we define a \textit{model selection criterion} that acts as a proxy for the generalization error.
A typical stopping criterion in the PCE framework of Figure \ref{fig:framework} is the observation that the model selection criterion no longer improves.
The following model selection criteria have been proposed in the sparse PCE literature:
\begin{itemize}
	\item \textit{$k$-fold cross-validation (CV)} \citep{Hastie:2001, Jakeman2015, Hampton2018}, which approximates the validation error by building a surrogate several times on different subsets of the data, and evaluating the error on the remaining data points.

	\item \textit{Leave-one-out (LOO) cross-validation} \citep{Hastie:2001,BlatmanPEM2010, BlatmanJCP2011}, which is $N$-fold cross-validation (where $N$ is the size of the experimental design).
	For PCE approximations computed by OLS, there exists an efficient formula to evaluate the LOO error \cite[Appendix D]{BlatmanJCP2011}.

	\item \textit{Modified LOO} \citep{BlatmanJCP2011}, which uses a correction factor for the LOO which was derived for the empirical error for OLS with small sample size \citep{Chapelle2002}. The correction factor depends on the experimental design and the active basis functions.

	\item \textit{Kashyap information criterion (KIC)} \citep{Shao2017,Zhou2019c}, an approximation to the Bayesian model evidence, which is the likelihood of observations given the model.

	\item \textit{Sparsity} \citep{Alemazkoor2017}, which uses the idea that a larger basis should lead to a sparser solution when the necessary basis functions enter the model, unless the ratio of basis functions to model evaluations becomes too large.

\end{itemize}

A model selection criterion is also often used to determine the hyperparameter of the sparse solver (see Section \ref{sec:solvers}).

If cross-validation is used to select the solver hyperparameter, this estimate of the validation error is often too optimistic due to model selection bias. Instead of reusing this estimate for model selection, it is better to perform an outer loop of $k$-fold or LOO cross-validation, a procedure called \textit{double cross-validation} or cross-model validation \citep{Baumann2014, LiuWiart2020b}.

\subsection{Further enhancements of sparse PCE}
\label{sec:enhancements}
There are many enhancements to the simple scheme for sparse PCE presented in Figure \ref{fig:framework}.
The following methods have been suggested to improve the accuracy of the solution and reduce the number of model evaluations needed:
\begin{itemize}
	\item \citet{Alemazkoor2018b} construct a preconditioning matrix for a given regression matrix which reduces the mutual coherence while avoiding deterioration of the signal-to-noise ratio.
	\item \citet{Huan2018} suggest a technique called stop-sampling, which guides the decision of whether to obtain more samples (sequential ED enrichment) by observing the decrease of the CV error.
	\item In the case when \changed{prior} information about the magnitude of the coefficients is available, \citet{Peng2014} use this information to construct a weighted regression problem which allows a more accurate solution with fewer points (similar to iteratively reweighted $\ell^1$-minimization).
	\item \citet{LiuWiart2020a} use resampled PCE, which is a technique for improving the PCE solution by aggregating the results of several solver runs on different subsets of the data. Only the terms that are chosen most often by the solvers are retained in the final solution.

	\item Several methods exist to reduce the dimension of the input space before computing the sparse PCE.
	Unsupervised methods are principal component analysis (PCA) and kernel PCA \citep{Lataniotis2019}.
	``Basis adaptation'' methods (referring to a basis of the input random space) determine a suitable rotation of the input space, often assumed to be independent standard Gaussian, into new coordinates which permit a sparser representation in fewer coordinates (see \citet{Tipireddy2014,Yang2018,Tsilifis2019} and others).
	A related technique is nonlinear PCE-driven partial least squares (PLS) \citep{Papaioannou2019, Zhou2020}, which reduces the input dimension by identifying directions in the input space that are able to explain the output well in terms of a sum of one-dimensional PCEs.

\end{itemize}

\section{Numerical results}
\label{sec:benchmark}

\subsection{Benchmark design}
While the number of methods for computing sparse PCE is large, to the best of the authors' knowledge there is no comprehensive benchmark study on this topic. Most publications only compare the newly developed method to one or two baseline methods.
An overview of publications containing comparisons of sparse PCE methods is presented in Appendix~\ref{app:benchmarkstudies}.

Since the number of possible combinations of sampling schemes, sparse regression solvers, basis adaptation schemes, model evaluation criteria etc.\ is huge (see Section \ref{sec:framework} and thereafter), we restrict our benchmark as follows to some of the most promising and best-known methods:
\begin{itemize}
	\item We consider the sampling schemes MC, LHS, coherence-optimal, and D-optimal.
	LHS is used together with a maximin criterion to improve the space-filling property (using the MATLAB function \texttt{lhsdesign}).
	D-optimal designs are constructed from a coherence-optimal candidate set%
	\footnote{We have also conducted all benchmark experiments with D-optimal designs constructed from LHS candidate sets, but we do not display these results, because we found that in most cases, D-opt(LHS) sampling performs (significantly) worse than most other sampling schemes, and often worse than its candidate set LHS. This matches with the results of \citet{FajraouiMarelli2017} who observed this in a sequential enrichment setting and with the LARS solver.}
	using the subset selection/RRQR algorithm, which allows for the construction of D-optimal experimental designs with size $N$ smaller than the number of regressors $P$ \citep{Diaz2018}. There is no such algorithm for S-optimal sampling, which is why we do not consider the latter in this benchmark.
	We do not consider Sobol' sequences, since they have been shown to be outperformed by LHS in sparse PCE applications \citep{FajraouiMarelli2017}.
	Near-optimal sampling can realistically be used only for rather small bases ($P \in {\mathcal O}(100)$), since its algorithm scales as \changed{${\mathcal O}(MP^2)$, with $M = 10P$ as suggested by \citep{Diaz2018} (see below)}. We use it with a coherence-optimal candidate set for two models with small basis.
	\item We consider the sparse regression solvers LARS, OMP, subspace pursuit (SP), FastLaplace (which we call here BCS), and SPGL1.
	Each of these solvers involves at least one hyperparameter, whose range is chosen according to reasonable guesses. For LARS and OMP, the hyperparameter is the number $K$ of selected regressors and its range is $[1, \min\{P,N-1\}]$. For SP, $K$ must fulfill $2K \leq \min\{P, N\}$. For BCS and SPGL1, the hyperparameter $\sigma$ is chosen from the range $\sigma^2 \in  N \changedmath{\cdot} \Varhat{\ve y} \changedmath{\cdot} [10^{-16}, 10^{-1}]$ which resembles a suitable range of possible relative MSE values. The hyperparameter values of LARS and OMP are determined by modified LOO cross-validation, while the hyperparameters of SP, BCS, and SPGL1 are determined by $k$-fold cross-validation (Section \ref{sec:solvers}).
	\changed{In addition, we consider a variant of SP which uses LOO cross-validation instead of $k$-fold cross-validation, which we name \emph{$\text{SP}_\text{LOO}${}}.}
	\item We only consider the nonadaptive setting, in which both the basis and the size of the experimental design are fixed before the sparse PCE is computed.
	\item For each model, we define a reasonable range of \changed{5--7} experimental design sizes. Each experiment is repeated 30--50 times to account for statistical uncertainty. The experimental designs are generated anew for each repetition and each ED size. All solvers are tested on the same ED realizations.
	\item The \changed{coherence-optimal} candidate sets \changed{from which the D-optimal designs are selected} have size $M = 10P$ as in \citep{Diaz2018}. For computational reasons, \changed{they}
	are not sampled completely anew for each replication, but are rather drawn uniformly at random without replacement from a larger set of size $2M = 20P$ as in \citep{Diaz2018}.
	\item Since we are interested in sparse PCE for the purpose of surrogate modelling, our main quantity of interest is the relative mean-squared error%
	\footnote{Note that some authors such as \citet{Doostan2011,Hampton2015,Diaz2018, Alemazkoor2018} choose to normalize instead by $\sum_{\ve x \in {\mathcal X}_\text{val}} {\mathcal M}(\ve x)^2$  or use the unnormalized mean-squared error \citep{Shin2016b}. To assess the recovery of sparse vectors just as in compressed sensing, some consider the error in the coefficient vector instead of the error in the model approximation \citep{Alemazkoor2018}.
	\footnote{Since a typical application of PCE is the computation of moments and Sobol' indices, the error in these quantities is another possible performance measure. However, globally accurate prediction as considered in this paper is more challenging that the prediction of moments and Sobol' indices, which are accurate if the largest-in-magnitude coefficients are estimated accurately. If a globally accurate surrogate model can be constructed, typically also the moments and Sobol' indices are accurate.}
	(RelMSE) as defined in \eqref{eq:RelMSE}.
	We investigate the RelMSE for several models, sparse solvers, and experimental design techniques.
	Typically, the practical interest lies in small experimental designs.
	\item Since the experimental design is random, the resulting validation error is a random variable. We visualize the data with boxplots. When comparing the performance of different methods, we consider the median performance and the spread of the resulting validation error. However, often there can be considerable overlap of validation errors between methods.
\end{itemize}

\subsection{Software}
For the implementation of the benchmark, we use the general-purpose uncertainty quantification software UQLab \citep{MarelliUQLab2014}.
UQLab supports the integration of other software packages.%
\footnote{A description of how to use custom sparse solvers and sampling schemes in the UQLab framework can be found in the supplementary material.}
We utilize the following code:
\begin{itemize}
	\item UQLab for MC sampling and LHS \citep{MarelliUQLab2014}.
	\item \texttt{DOPT\_PCE} for D-optimal sampling (subset selection/RRQR) and subspace pursuit \citep{Diaz2018, SPcode}.
	\item An in-house developed rejection-based implementation of coherence-optimal sampling.
	\item An in-house implementation of near-optimal sampling based on the description by \citet{Alemazkoor2018}.
	\item UQLab for the solvers LARS and OMP \citep{MarelliUQLab2014}.
	\item \texttt{spgl1-1.9} for SPGL1 \citep{Vandenberg2008, SPGL1}.
	\item \texttt{FastLaplace} for the hierarchical implementation ``FastLaplace'' of BCS \citep{Babacan2010, FastLaplace}.
\end{itemize}

\subsection{Benchmark: Considered models}
\label{sec:benchmark_models}
\changed{Our benchmark is performed on a selection of 11 computational models of varying complexity and input dimensionality, which are typical benchmark models in the context of sensitivity and reliability analysis.
An overview of these models is given in Table~\ref{table:models}. For details on the models, we refer the reader to the respective publications supplied in the last column of the table.
While of course not representative of all possible classes of engineering models, we believe that this sample provides a good testing ground for the comparative performance among different approaches for computing sparse PCE. }

\begin{table}[htbp]
	\footnotesize
	\centering
	\caption{\changed{Overview of the 11 computational models used in our benchmark. Italic font denotes finite element (FE) models , all other models are analytical.
			For each model, a static total-degree basis with hyperbolic truncation defined by $p$ and $q$ is used. The values are chosen to fulfill $P \approx \frac{10}{3} N_\text{max}$, where $N_\text{max}$ is the largest tested experimental design size.
			The values for $p$ in parentheses for the Ishigami and borehole models refer to the smaller basis used in Section~\ref{sec:results_nearopt}.
			The column ``Reference'' provides the relevant literature in which the models and their probabilistic inputs are described in detail. }}
	\label{table:models}
	\renewcommand{\arraystretch}{1.2}
	\begin{tabular}{l c >{\centering}p{.22\textwidth} >{\centering}p{.11\textwidth} >{\centering}p{.05\textwidth} >{\centering\arraybackslash}p{.11\textwidth}}
		\hline
		Model & Dimension & Input distributions & Basis & $N_\text{max}$ & Reference \\
		\hline
		%
		Ishigami function & 3 & uniform & $p = 14$ ($12$), \newline $q=1$& $200$&  \citep{BlatmanJCP2011}  \\
		Undamped oscillator & 6 & Gaussian & $p = 5$, \newline $q=1$& $150$ &\citep{Echard2013}  \\
		Borehole function & 8 & Gaussian, lognormal, uniform & $p = 5$ ($4$), \newline $q=1$& $300$ & \citep{Harper1983}  \\
		Damped oscillator & 8 & lognormal & $p = 5$, \newline $q=1$ & $400$ &\citep{DubourgThesis} \\
		Wingweight function & 10 & uniform  & $p = 4$, \newline $q=1$& $300$ &\citep{Forrester2008} \\
		\textit{Truss model} & 10 & lognormal, Gumbel  & $p = 4$, \newline $q=1$& $300$ & \citep{BlatmanJCP2011} \\

		Morris function & 20 & uniform & $p = 8$, \newline $q=0.5$& $400$ & \citep{BlatmanRESS2010}  \\

		\textit{Structural frame model} & 21 & lognormal, Gaussian; {dependent input variables} & $p = 8$, \newline $q=0.5$& $400$ & \citep{BlatmanPEM2010}  \\
		\textit{$2$-dim diffusion model} & 53 & Gaussian & $p = 4$, \newline $q=0.5$& $500$ & \citep{KonakliRESS2016}  \\
		\textit{$1$-dim diffusion model} & 62 & Gaussian & $p = 4$, \newline $q=0.5$& $500$ & \citep{FajraouiMarelli2017}  \\
		\changed{$100$D} function & 100 & uniform & $p = 4$, \newline $q=0.5$& $1400$ & UQLab \newline example\footnotemark  \\
		\hline
	\end{tabular}
\end{table}

\changed{In addition to analyzing aggregated performance on all 11 models, we investigate the behavior of the methods in detail on a subset of four \textit{spotlight models}, each of which possesses characteristic properties that might influence the approximation quality of sparse PCE methods:
the \textit{Ishigami function} is low-dimensional and highly compressible in the PCE basis but requires a high-degree basis to be approximated accurately. The \textit{borehole function} is smooth and nonlinear and therefore is an example for a well-behaved engineering model. A \textit{two-dimensional diffusion model}, a stochastic heat diffusion PDE in two physical dimensions, is high-dimensional, not analytical, and the magnitude of its expansion coefficients decays only slowly. Finally, the \textit{$100$D function} is high-dimensional, analytical, and compressible.}

The Ishigami model is the well-known three-dimensional, highly nonlinear, smooth analytical function
\begin{equation}
f(X_1, X_2, X_3) = \sin(X_1) + a \sin^2(X_2) + b X_3^4 \sin(X_1)
\end{equation}
taking uniform input $\ve X \sim {\mathcal U}([-\pi, \pi]^3)$. A typical choice is $a = 7, b = 0.1$. For this function, any sparse solver should be able to find a sparse solution.

The borehole function simulates the water flow through a borehole between two aquifers \citep{Harper1983}. It is an eight-dimensional nonlinear function which, despite having an analytical form, is not trivial to approximate. It is defined by
\begin{equation}
B(r_w, L, K_w, T_u, T_l, H_u, H_l, r) = \frac{2\pi T_u (H_u - H_l)}{\ln\left(r / r_w\right) \left( 1 + \frac{2 L T_u}{\ln\left(r / r_w\right) r_w^2 K_w} + \frac{T_u}{T_l}\right)}.
\end{equation}
Its input random variables and their distributions are provided in Table \ref{table:borehole}.

\begin{table}
	\caption{Borehole function: Input random variables and their distributions}
	\label{table:borehole}
	\centering
	\footnotesize
	\begin{tabular}{l l l}
		\hline
		Variable & Distribution & Description \\
		\hline
		$r_w$ & ${\mathcal N}(0.10, 0.0161812)$ & borehole radius \\
		$L$ & ${\mathcal U}([1120, 1680])$ & borehole length \\
		$K_w$ & ${\mathcal U}([9855, 12045])$ & borehole hydraulic conductivity  \\
		$T_u$ & ${\mathcal U}([63070, 115600])$ & transmissivity of upper aquifer  \\
		$T_l$ & ${\mathcal U}([63.1, 116])$ & transmissivity of lower aquifer  \\
		$H_u$ & ${\mathcal U}([990, 1110])$ & potentiometric head of upper aquifer  \\
		$H_l$ & ${\mathcal U}([700, 820])$ &  potentiometric head of lower aquifer \\
		$r$ & $ \text{Lognormal}([7.71, 1.0056])$ & radius of influence  \\
		\hline
	\end{tabular}
\end{table}

The two-dimensional heat diffusion model \citep{KonakliRESS2016} is defined by the partial differential equation (PDE)
\begin{equation}
- \nabla \cdot (\kappa(\ve x) \nabla T(\ve x)) = Q \mathbb{1}_A(\ve x) \qquad \text{ in }\Omega = [-0.5, 0.5]^2
\end{equation}
with boundary conditions $T = 0$ on the top boundary and $\nabla T \cdot \ve n = 0$ on the left, lower, and right boundaries of the square domain $\Omega$, where $\ve n$ denotes the outer unit normal (see \citep{KonakliRESS2016} for an illustration of the setup).
Here, the source is in $A = [0.2, 0.3]^2$ with strength $Q = 500$.
The output quantity of interest is the average temperature in $B = [-0.3, -0.2]^2$.
The diffusion coefficient $\kappa(\ve x)$ is modelled by a lognormal random field with mean $\mu_\kappa = 1$ and standard deviation $\sigma_\kappa = 0.3$. The autocorrelation function of the underlying Gaussian random field is an isotropic squared-exponential with length scale $l = 0.2$.
The random field $\kappa(\ve x)$ is discretized using the EOLE method \citep{DerKiureghian1993} with $d = 53$ terms, which comprises $99\%$ of its variance.
The solution to an individual heat diffusion problem is computed using an in-house finite \changed{element} code \citep{KonakliRESS2016}.
The input comprises $d=53$ independent standard normal random variables.

Finally, the so-called \changed{100D} function is an analytical model of the form
\begin{align}
	f(\ve X) &= 3 - \frac{5}{d} \sum_{i = 1}^{d} i X_i +
	\frac{1}{d}\sum_{i = 1}^{d} i X_i^3  +
	\frac{1}{3d}\sum_{i = 1}^{d} i  \ln\left(X_i^2 + X_i^4\right) \\
	& \quad + X_1 X_2^2  + X_2 X_4 - X_3 X_5 + X_{51} + X_{50}X_{54}^2
	\nonumber
\end{align}
taking uniform inputs $X_i \sim {\mathcal U}([1,2]), i \neq 20$, and $X_{20} \sim {\mathcal U}([1,3])$.
We use $d = 100$.
This function was designed for sensitivity analysis: the first-order sensitivity indices of the input variables are generally nonlinearly increasing with their index, with certain variables having especially high sensitivity. The model also contains four interaction terms.
It is an example from UQLab.\textsuperscript{\ref{fn:uqlab}}
\footnotetext{\url{https://www.uqlab.com/sensitivity-high-dimension}\label{fn:uqlab}}

For each of the models, we use a fixed basis for the benchmark. In general, the best total degree $p$ and the hyperbolic truncation $q$ are a priori unknown. We heuristically choose $q = 1$ for low-dimensional models ($d \leq 10$) and $q = 0.5$ for high-dimensional models (\changedmath{$d \geq 20$}). The degree $p$ is chosen so that the number of basis functions $P$ is approximately $\frac{10}{3}N_\text{max}$, where $N_\text{max}$ is the largest number of experimental design points for the specific benchmark. This choice is based on the reasoning that for an experimental design of size $N$, sparse solvers like LARS often select an active basis of size $ \approx \frac{N}{3}$, and that the candidate basis might be 10 times larger than the final active basis to be sufficiently rich.
We focus on rather small experimental designs, since our goal is not to investigate the convergence of the methods as $N \to \infty$ (which has been demonstrated elsewhere), but to decide which methods are most efficient for small $N$.
This results in
\changed{the choice of values for $p$, $q$, and $N_\text{max}$ displayed in Table~\ref{table:models}.}

\subsection{Results: Comparison of solvers}
\label{sec:results_only_solvers}
First, we use a fixed sampling scheme (LHS) to compare the performance of the \changed{six} solvers LARS, OMP, subspace pursuit (SP) using $k$-fold cross-validation, \changed{Subspace Pursuit using LOO cross-validation ($\text{SP}_\text{LOO}${}{})}, FastLaplace (BCS), and SPGL1 on \changed{all 11} benchmark models described above.

In \changed{Figure~\ref{fig:results_onlysolvers}} we display boxplots (50 replications) of relative MSE against experimental design size for all \changed{six} solvers \changed{for the four spotlight models}.
\changed{For the remaining seven models, the corresponding boxplots (30 replications) of relative MSE against experimental design size are provided in Figure~\ref{fig:results_more_models} in Appendix~\ref{app:additional_results}.}
In the plots, the lines as well as the dot inside the white circle denote the median of the relative MSE.
We make the following observations:
\begin{itemize}
	\item For the smallest experimental designs, all solvers perform similarly \changed{poorly: there is not enough information in the ED to construct an accurate surrogate model}. For larger experimental designs, there can be considerable differences between the solvers' generalization errors of up to several orders of magnitude\changed{, which demonstrates that the solvers do not use the available information in identical ways}.
	\item BCS, \changed{$\text{SP}_\text{LOO}${}{},} and OMP are often among the best solvers. BCS performs especially well for smaller experimental design sizes.
	In the case of the Ishigami model, it seems to plateau earlier than the other solvers. It also tends to find sparser solutions than the other solvers (not shown in plots)\changed{, which might explain these observations: sparse solutions are advantageous when only limited data is available, but at the same time they carry the risk of ignoring important terms}. For \changed{large ED sizes and the two highly compressible models (Ishigami and \changed{100D} function), BCS} has a larger spread than the other solvers\changed{, possibly because the sparsity-enforcing procedure does not always include all of the important terms}. \changed{In contrast, the greedy solver OMP returns rather dense solutions, which seem to generalize well.}
	\changed{$\text{SP}_\text{LOO}${}{} performs well in general for low-dimensional models.}
	\item SP does not perform well for small ED sizes, but for large ED sizes it \changed{sometimes} outperforms the other solvers. Together with BCS, it tends to find sparser solutions than the other solvers \changed{(not shown in plots)}.
	\item LARS and SPGL1 \changed{often achieve a similar generalization error, which is often larger, sometimes significantly, than that of the other solvers.} SPGL1 tends to return rather dense solutions (not shown in plots)\changed{, which might not generalize as well as other solutions}.
	\item \changed{Some models characterized by relatively poor compressibility (e.g. diffusion and frame) show comparable performance among all solvers. This is expected, as in such cases the sparsity assumption is a rather weak proxy for solution quality.}
	\item \changed{The exceptions to the general observations outlined above are the damped oscillator and the Morris function, for which the solver performance is reversed, with LARS and SPGL1 among the best solvers, and OMP and $\text{SP}_\text{LOO}${}{} among the worst.
		In these cases, however, none of the methods achieves satisfactory accuracy within the available computational budget.}
\end{itemize}

\begin{figure}[htbp]
	\centering
	\subfloat[][Ishigami function]
	{\includegraphics[width=.49\textwidth]{M131577_Fig2a.pdf}\label{fig:onlysolvers_ishigami}}
	\hfill
	\subfloat[][Borehole model]
	{\includegraphics[width=.49\textwidth]{M131577_Fig2b.pdf}\label{fig:onlysolvers_borehole}}
	\\
	\subfloat[][Two-dimensional diffusion]
	{\includegraphics[width=.49\textwidth]{M131577_Fig2c.pdf}\label{fig:onlysolvers_diffusion2D}}
	\hfill
	\subfloat[][\changed{100D} function]
	{\includegraphics[width=.49\textwidth]{M131577_Fig2d.pdf}\label{fig:onlysolvers_highdimfct}}
	%
	\caption{\changed{Boxplots of relative MSE against ED size from the solver benchmark for the four spotlight models. Results for six sparse solvers and LHS design. For the corresponding plots for the seven remaining models, see Figure~\ref{fig:results_more_models} in Appendix~\ref{app:additional_results}.}}
	\label{fig:results_onlysolvers}
\end{figure}

	To objectively assess the performance of the methods, we now aggregate the results across models. Since all solvers are tested on the same set of experimental designs, we can determine the ranking of solvers for each experimental design (50 replications $\times$ $6-7$ ED sizes for the four spotlight models, and 30 replications $\times$ $5-7$ ED sizes for each of the seven additional models, resulting in 2620 PCEs) and count how often each solver achieved each rank. This is displayed in Figure~\ref{fig:results_more_models_aggregated} in the form of stacked bar plots, where the counts are given as percentages. The counts have been normalized by the number of replications and ED sizes used for each model, so that each of the models contributes equally to the final percentages.

	This ranking alone, however, does not provide a complete picture; e.g., a solver ranked last can be off by orders of magnitude or barely worse than the best-performing one. Therefore, we added an additional set of triangle markers detailing for how many of the EDs
	the respective solver returned a result that was within two, five, or 10 times the smallest relative MSE attained by any of the six solvers on the same ED. For example, the red triangle in the top row of Figure~\ref{fig:results_more_models_aggregated1} indicates that in ca.\ 30\% of the runs, the solution returned by LARS had a validation error that was at most twice as large as that of the best solution on the same ED.

	We have grouped the analysis results separately for the 6 low-dimensional ($d \leq 10$) and the 5 high-dimensional ($d \geq 20$) models, because we observed that dimension had a significant impact on the rankings, and this information is readily available even for black-box models. We also analyze small and large ED sizes separately, where the first half of considered ED sizes (3--4) are regarded small, and the second half large.

	\begin{figure}[htbp]
		\centering
		\subfloat[][low-dim models ($d \leq 10$), small ED sizes]
		{\includegraphics[width=.56\textwidth]{M131577_Fig3a.pdf}\label{fig:results_more_models_aggregated1}}
		\hfill
		\subfloat[][low-dim models ($d \leq 10$), large ED sizes]
		{\includegraphics[width=.435\textwidth, trim = 0 0 8.2cm 0, clip]{M131577_Fig3b.pdf}\label{fig:results_only_solvers_lowdim_largeED}}
		\\
		\subfloat[][high-dim models ($d \geq 20$), small ED sizes]
		{\includegraphics[width=.56\textwidth]{M131577_Fig3c.pdf}}
		\hfill
		\subfloat[][high-dim models ($d \geq 20$), large ED sizes]
		{\includegraphics[width=.435\textwidth, trim = 0 0 8.2cm 0, clip]{M131577_Fig3d.pdf}}
		%
		\caption{\changed{Aggregated results for the solver benchmark (Section~\ref{sec:results_only_solvers}), separately for low-dimensional (a),(b) and high-dimensional models (c),(d). Left: small ED sizes. Right: large ED sizes. For each model and experimental design, the ranking of the six solvers is determined. The stacked bar plots visualize how often each solver achieved the respective rank. The triangle markers in hues of red additionally demonstrate in how many runs the obtained relative MSE was within a factor of $\{2,5,10\}$ of the smallest relative MSE achieved on this experimental design.}
		}
		\label{fig:results_more_models_aggregated}
	\end{figure}

	We make the following observations:
	\begin{itemize}
		\item \textit{Low-dimensional models, small ED sizes}:
		BCS is the best solver most often (31\% of runs) and also most often within two times the smallest error (72\% of runs). However, it comes within one order of magnitude of the smallest relative MSE (a property which we here call \textit{robustness}) in only 87\% of runs, while $\text{SP}_\text{LOO}${}{} achieves this in 94\% of runs. In the two former metrics, $\text{SP}_\text{LOO}${}{} comes second.
		LARS and SP perform worst, followed by OMP and SPGL1. Here and in the following, we observe that OMP and $\text{SP}_\text{LOO}${}{} often result in quite robust solutions.

		\item \textit{Low-dimensional models, large ED sizes}:
		$\text{SP}_\text{LOO}${}{} outperforms the other solvers in all respects. It provides the smallest relative MSE of all solvers in 42\% of runs, is in 73\% of runs within two times of the smallest relative MSE, and is even in 99\% of runs within one order of magnitude of the smallest relative MSE.
		For the other solvers, the statistics confirm the observations highlighted by the spotlight models: LARS and SPGL1 overall do not perform well. SP and BCS come close to the best solution quite often, but are less robust, whereas OMP is robust but often not as close to the best solution.

		\item \textit{High-dimensional models}:
		For the small as well as the large ED sizes, we see that BCS performs exceptionally well. It is the best solver in 45\% (53\%) of runs and comes within two times the smallest relative MSE in even 96\% (97\%) of runs. Both BCS and OMP attain in \textit{all} cases a relative MSE within 10 times the smallest relative MSE. SP performs better for large rather than small ED sizes.
		While $\text{SP}_\text{LOO}${}{} performed best for the low-dimensional models, here it shows poor performance.
		Note that all solvers come within 10 times the smallest relative MSE in more than 89\% of all runs, showing that the choice of solver has a smaller impact for high-dimensional than for low-dimensional models.

	\end{itemize}

\subsection{Results: Comparison of sampling schemes together with solvers}
\label{sec:results_sampling}

	We pair the five solvers LARS, OMP, SP, $\text{SP}_\text{LOO}${}{}, and BCS%
	\footnote{Since SPGL1 did not perform well in the previous section, and is quite slow, we do not include it further in this benchmark.}
	with the sampling schemes MC, LHS, coherence-optimal, and D-optimal based on a coherence-optimal candidate set. We use the abbreviations coh-opt and D-opt(coh-opt) for the latter two.
	Since $\text{SP}_\text{LOO}${}{} performed poorly for high-dimensional models in the solver benchmark of the previous section, we do not consider it here for the high-dimensional models.

	We run the benchmark for the low-dimensional models Ishigami, undamped oscillator, borehole, damped oscillator, and wingweight function, and for the high-dimensional models Morris function, two-dimensional diffusion, one-dimensional diffusion, and \changed{100D} function. The truss model has Gumbel input, for which we (as of now) cannot construct a coherence-optimal sample. The same holds for the structural frame model with its dependent input.

	Detailed boxplots of the relative MSE against ED size for the spotlight models, showing how each solver performed when paired with the sampling schemes, can be found in Appendix~\ref{app:additional_results}, Figures~\ref{fig:results_ishigami_additional}--\ref{fig:results_highdimfct_additional}.
	For the sake of readability, in this section we only show results that are aggregated over models, separately for the low- and high-dimensional cases.
	For every model and repetition index, we determine the relative ranking of the 20 (16) combinations (5 (4) solvers $\times$ 4 sampling strategies). We also determine which of the combinations came within a factor of $\{2,5,10\}$ of the smallest relative MSE among this set (robustness).
	Then, we count how often each combination achieved each rank, and how often each combination achieved a relative MSE within a factor of the smallest relative MSE.
	The results are displayed in Figure~\ref{fig:results_sampling_aggregated} in the form of stacked bar plots for the ranks, with triangle markers denoting the percentage of robust runs.
	The combinations are sorted by the percentage of runs in which they achieved a relative MSE within two times the smallest relative MSE, because we find that this metric is a good compromise between performance and robustness.
	We analyze small and large ED sizes separately, where the first half of considered ED sizes (3--4) are regarded as small and the second half as large.

	\begin{figure}[htbp]
		\centering
		\subfloat[][$d \leq 10$, small ED sizes]
		{\includegraphics[width=.55\textwidth]{M131577_Fig4a.pdf}
			\label{fig:results_sampling_aggregated_small}}
		%
		\subfloat[][$d \leq 10$, large ED sizes]
		{\includegraphics[width=.43\textwidth,trim=0 0 8.5cm 0, clip]{M131577_Fig4b.pdf}
			\label{fig:results_sampling_aggregated_large}}
		\\
		\subfloat[][$d \geq 20$, small ED sizes]
		{\includegraphics[width=.55\textwidth]{M131577_Fig4c.pdf}
			\label{fig:results_sampling_aggregated_small_highdim}}
		%
		\subfloat[][$d \geq 20$, large ED sizes]
		{\includegraphics[width=.43\textwidth,trim=0 0 8.3cm 0, clip]{M131577_Fig4d.pdf}
			\label{fig:results_sampling_aggregated_large_highdim}}
		%
		\caption{\changed{Aggregated results for the five low-dimensional models Ishigami, undamped oscillator, borehole, damped oscillator, and wingweight (top), and for the four high-dimensional models Morris function, structural frame, two-dimensional diffusion, and \changed{100D} function (bottom). Separately for small (a),(c) and large (b),(d) experimental designs. For the low-dimensional (high-dimensional) case, we investigate five (four) solvers and four sampling schemes, resulting in 20 (16) combinations. For each model and repetition, the ranking of all the combinations is determined (note that as opposed to Figure~\ref{fig:results_more_models_aggregated}, here the comparison is done on different EDs, which are matched randomly. Results are bootstrapped four times by random permutations to increase robustness). The stacked bar plots visualize how often each combination achieved the respective rank. The triangle markers in hues of red additionally demonstrate in how many runs the obtained relative MSE was within a factor of $\{2,5,10\}$ of the smallest relative MSE achieved in this comparison.
				The combinations are sorted by the percentage of runs in which they achieved a relative MSE within two times the smallest relative MSE of the respective random pairing (red triangle marker).
				Plots of relative MSE against ED size for the spotlight models can be found in Appendix~\ref{app:additional_results}, Figures~\ref{fig:results_ishigami_additional}--\ref{fig:results_highdimfct_additional}.}}
		\label{fig:results_sampling_aggregated}
	\end{figure}

	Note that, as opposed to the aggregated results in Figure~\ref{fig:results_more_models_aggregated}, where the solvers are compared on the same experimental designs, here the comparison is done on \textit{different} experimental designs, which are matched randomly.%
	\footnote{\changed{The relative MSE of each combination is interpreted as a random variable $E_\text{solver}^\text{sampling}$, where the randomness is induced by the randomness in the experimental design. E.g., $E_\text{BCS}^\text{LHS}$ is the random variable of relative MSE attained by BCS applied to an LHS design of specified size. The reference error (``smallest relative MSE'') $E^*$ is a random variable as well, defined as the minimum over \textit{one realization} of each combination of methods: $E^* = \min_{s \in \text{sampling}, t \in \text{solvers}} E_{s}^{t}$. The plots in Figure~\ref{fig:results_sampling_aggregated} are therefore read as follows: e.g., in the low-dimensional, small ED size case (Figure~\ref{fig:results_sampling_aggregated_small}):
			$ \Prob{E_\text{BCS}^\text{D-opt} = E^*} = 0.16, \quad \Prob{E_\text{BCS}^\text{D-opt} \leq 10 E^*} = 0.78.$%
		}}
	Our results in Figure~\ref{fig:results_sampling_aggregated} are bootstrapped four times using random permutations of the replication index, corresponding in total to 250 replications, to minimize the influence of this randomness (which is in any case not large, as can be seen from permutation tests).

	\changed{From Figure~\ref{fig:results_sampling_aggregated} and Figures~\ref{fig:results_ishigami_additional}--\ref{fig:results_highdimfct_additional}, we} make the following observations:
	\begin{itemize}
		\item \changed{There can be considerable differences in the performance of different combinations of solvers and sampling schemes. The differences are larger for low-dimensional models, visible in the spread of triangle markers in Figures~\ref{fig:results_sampling_aggregated_small} and \ref{fig:results_sampling_aggregated_large}.
			For high-dimensional models, many combinations find an error that is close to the smallest error, which can be seen from the red triangle markers at high percentages in Figures~\ref{fig:results_sampling_aggregated_small_highdim} and \ref{fig:results_sampling_aggregated_large_highdim}, and from the clustered boxplots in Figures~\ref{fig:results_diffusion2D_additional} and \ref{fig:results_highdimfct_additional}, (e) and (f).}

		\item MC and LHS perform comparably, and for the high-dimensional models almost identically. For the low-dimensional models, LHS sampling has, in most cases, median error and variability that are the same as or smaller than MC.
		This is consistent with the literature \citep{Shields2016}.
		\changed{These observations are confirmed by the plots in Figure~\ref{fig:results_sampling_aggregated}: for almost every solver, the combination with LHS is slightly better than the corresponding one with MC in each of the metrics.
		}

		\item \changed{The advanced sampling schemes coh-opt and D-opt(coh-opt) show a clear advantage over MC and LHS sampling for low-dimensional models and large experimental designs (consistent with theoretical considerations and numerical experiments \citep{Hampton2015}). For low-dimensional models and small experimental designs, they show mixed performance; for high-dimensional models, they perform the same as or worse than LHS and MC.}

		\changed{It is known that coh-opt sampling leads to a greater improvement over MC sampling for low-dimensional, high-degree expansions than for high-dimensional, low-degree expansions \citep{Hampton2015,Alemazkoor2018}.
			Note also that all numerical experiments in the literature testing coh-opt sampling were performed in $d \leq 30$ dimensions, using only models with uniform input, or manufactured sparse PCE, i.e., polynomial models with an exactly sparse representation \citep{Hampton2015,Hampton2015b,Alemazkoor2018,Diaz2018}.}

		\changed{Both} coh-opt and D-opt are sampling methods that aim to improve properties of the regression matrix. They are adapted to the candidate basis. If the candidate basis is large and contains many regressors that are not needed in the final sparse expansion, this adaptation might even deteriorate the solution.

		\item \changed{BCS is one of the best-performing solvers, almost regardless of sampling scheme. The exceptions are low-dimensional models with large experimental designs, where $\text{SP}_\text{LOO}${}{} with coh-opt sampling outperforms all other solvers. This might be related to BCS plateauing earlier than other solvers (see Figure~\ref{fig:onlysolvers_ishigami} and \ref{fig:onlysolvers_borehole}). It seems BCS is preferable whenever the information content is low (small ED sizes or high-dimensional models).}

		\item \changed{OMP and $\text{SP}_\text{LOO}${}{} are generally quite robust (within one order of magnitude of the best solution). However, OMP often does not come close to the best solution, especially when paired with LHS or MC. BCS is more robust for high-dimensional models than for low-dimensional models. LARS and SP show mixed performance, with LARS being one of the least robust solvers.}

		\item \changed{Aggregating the results for each sampling scheme separately (not shown), we observe that the behavior of the solvers is very similar in terms of ranking and robustness to the behavior observed on LHS (Figure~\ref{fig:results_more_models_aggregated}), suggesting that the ranking of solvers is mostly independent of the sampling scheme.
	}

	\end{itemize}

	Note that the results in Figures~\ref{fig:results_ishigami_additional}, \ref{fig:results_borehole_additional}, and \ref{fig:results_highdimfct_additional} exhibit plateauing for larger sample sizes. This indicates that the maximal accuracy achievable with this set of basis functions has been reached. \changed{Using a larger basis might lead to more accurate solutions, if it contains an important regressor that was previously missing. However, note that a larger basis can also lead to less accurate solutions: when the experimental design size is held fixed while a larger basis is used, }
	the ratio of experimental design points to basis functions \changed{is}
	smaller, and the properties of the regression matrix might deteriorate.

	\subsection{Results: Comparison of sampling schemes together with solvers, using a smaller candidate basis}
	\label{sec:results_nearopt}

	We repeat the experiments from the previous section for the Ishigami and borehole models, using a smaller candidate basis for which near-optimal sampling is feasible. The tested solvers are LARS, OMP, SP, \changed{$\text{SP}_\text{LOO}${}{},} and BCS. We use the sampling schemes MC, LHS, coh-opt, D-opt(coh-opt) and near-opt(coh-opt).
	\changed{Boxplots of relative MSE against ED size} are shown in Figures~\ref{fig:results_ishigami_smallbasis} and \ref{fig:results_borehole_smallbasis}.
	\changed{For the sake of conciseness, we only show the combinations involving OMP and $\text{SP}_\text{LOO}${}{}. The remaining plots are provided in Appendix~\ref{app:additional_results}, Figure~\ref{fig:results_smallbasis_additional}.}

	We observe the following:
	\begin{itemize}
		\item Since the basis is smaller, the relative MSE reaches a plateau already for smaller experimental design sizes.

		\item Most qualitative observations regarding solver and sampling performance are the same as in the previous section, where a larger basis was used.
		\item Near-optimal sampling often achieves the same or a slightly smaller error than \changed{coh-opt} sampling, which is consistent with \citep{Alemazkoor2018}. In many cases, near-optimal sampling achieves the smallest median error. For the Ishigami \changed{model}, near-opt\changed{imal sampling} additionally exhibits small variability\changed{, while for} the borehole model, \changed{it} has a rather large spread, i.e., several outliers.
	\end{itemize}

	\begin{figure}[htbp]
		\centering
		\subfloat[][OMP]{\includegraphics[width=.49\textwidth, height=0.25\textheight, keepaspectratio]{M131577_Fig5a.pdf}}
		\hfill
		\subfloat[][$\text{SP}_\text{LOO}${}{}]{\includegraphics[width=.49\textwidth, height=0.25\textheight, keepaspectratio]{M131577_Fig5b.pdf}}
		%
		\caption{\changed{Results for the Ishigami model with a smaller basis ($d = 3, p = 12, q=1$). Results for two sparse solvers and five experimental design schemes. 50 replications. For the remaining plots, see Figure~\ref{fig:results_smallbasis_additional} in Appendix~\ref{app:additional_results}.}}
		\label{fig:results_ishigami_smallbasis}
	\end{figure}

	\begin{figure}[htbp]
		\centering
		\subfloat[][OMP]{\includegraphics[width=.49\textwidth, height=0.25\textheight, keepaspectratio]{M131577_Fig6a.pdf}}
		\hfill
		\subfloat[][$\text{SP}_\text{LOO}${}{}]{\includegraphics[width=.49\textwidth, height=0.25\textheight, keepaspectratio]{M131577_Fig6b.pdf}}
		%
		\caption{\changed{Results for the borehole model with a smaller basis ($d = 8, p = 4, q = 1$). Results for two sparse solvers and five experimental design schemes. 50 replications. For the remaining plots, see Figure~\ref{fig:results_smallbasis_additional} in Appendix~\ref{app:additional_results}.}}
		\label{fig:results_borehole_smallbasis}
	\end{figure}

	\FloatBarrier

\section{\changed{Discussion and conclusions}}
\label{sec:conclusion}

In this paper, we investigated sparse PCE methods with the goal of computing accurate surrogate models based on a few model evaluations.

We presented a literature survey and a framework describing the general computation procedure for sparse PCE.
We have seen that the existing literature on sparse PCE can be fit into this framework and that methods developed for different components of the framework can naturally be combined.

In order to give recommendations to practitioners who want to use sparse PCE surrogates for their applications, we performed a numerical benchmark based on \changed{11} example functions which are intended to resemble real-world engineering problems presenting different challenges.
We tested several popular sparse solvers and sampling schemes on a fixed set of basis functions, using a range of experimental design sizes and \changed{30--}50 replications, and
made the following observations:
\begin{itemize}
	\item The choice of sampling scheme and sparse regression solver can make a difference of up to several orders of magnitude for the relative MSE. Mostly, the rankings of solvers and sampling schemes seem to be independent of one another: an experimental design that works best for one solver will also perform well with other solvers, and the ranking of solvers looks similar independent of which sampling scheme is used. \changed{Both solvers and} sampling schemes make a greater difference for low-dimensional models.
	\item \changed{For low-dimensional models and small ED sizes, the solver BCS performs best, regardless of sampling scheme (with D-opt(coh-opt) being slightly preferable), while the solver $\text{SP}_\text{LOO}${}{} (a variant of SP) appears to be especially robust.}
	\item \changed{For low-dimensional models and large ED sizes, $\text{SP}_\text{LOO}${}{} together with coherence-optimal sampling outperforms all other combinations.}
	\item \changed{For low-dimensional models, and when the basis is small enough to make it feasible, near-optimal sampling outperforms all other sampling schemes, regardless of the solver}.
	\item \changed{For high-dimensional models, BCS is by far the best solver. All solvers perform better when paired with LHS; in other words, no advanced sampling scheme appears competitive compared to LHS for such problems, whatever the solver used.
	}
\end{itemize}
\changed{The benchmark results demonstrate that in costly, real-world applications it is worth choosing the sparse PCE training strategy carefully, since the methods can make a substantial difference in the quality of the resulting surrogate.
	While a more accurate surrogate model is generally desirable, in industrial applications it might have a higher impact for purposes such as optimization, rather than, e.g., sensitivity analysis.
}

\changed{Our conclusions are based on a number of benchmark models, which we consider representative of engineering models in terms of dimensionality and complexity. Naturally, however, no selection of models can cover the whole space of engineering models.}
\changed{Further work would be required to understand the connection among model properties, basis choice, experimental design size, and sparse PCE techniques like solvers and sampling schemes.}

All results were obtained using a fixed basis based on a heuristic choice (see Section \ref{sec:benchmark_models}).
Generally, when the optimal degree of the basis is unknown, degree adaptivity (based on a cross-validation error) can be a useful strategy.
\changed{Due to time and space constraints, this} was not investigated in the present work.
Adaptivity critically depends on the availability of an accurate error estimator.
Some of the best solvers in this study (i.e., OMP and BCS)
tend to underestimate the generalization error (not shown in the plots), which might be a drawback in the setting of adaptive degree selection and might change the effect and ranking of solvers and sampling methods.
\changed{For a detailed discussion and benchmark of basis-adaptive schemes, we refer the reader to \citep{LuethenIJUQ2021}.}

\changed{As evident from the extensive literature on the topic, sparse PCE is an already well-established technique, as well as an active field of methodological research. Recent innovations include Bayesian techniques for sparse PCE and the identification of suitable rotated coordinates for the expansion.
	Such innovative ideas are expected to lead to further improvements in the computation of sparse PCE, which will in turn benefit applications as well as all advanced methods that use sparse PCE as one of their building blocks (see, e.g., \citep{SchoebiIJUQ2015,Chatterjee2019,ZhuIJUQ2020,MarelliSPCE2021}).}

\changed{PCE is a popular metamodelling tool in the engineering community, and many different methods are available. Up to now, the choice of which of the many PCE methods to apply was mostly left to chance or the personal experience of the practitioner.
	In our benchmark, we explored a significant set of methods that have received attention in the past few years. We hope that this work can serve as a basis for further benchmarking efforts, in order to identify which of the many available methods are most suitable for real-world problems. These might include sequential enrichment of experimental design, Gaussian adaptation of the input space, stepwise regression algorithms and many other ideas for sparse solvers, as well as methods for extremely high-dimensional problems.
}

\changed{Our benchmark code is available on request. The solvers BCS and $\text{SP}_\text{LOO}${}{} will be made available in the 1.4.0 release of UQLab. For a description of how to add custom sampling schemes and sparse solvers for PCE to UQLab, we refer the reader to the supplementary material accompanying this paper.}
\changed{
	To facilitate easier benchmarking of PCE techniques on a large number of examples in a standardized setup, we are actively engaging in designing and developing a benchmarking platform for surrogate modelling methods similar to the UCI machine learning repository%
	\footnote{\url{https://archive.ics.uci.edu}}
	or the structural reliability platform RPrepo%
	\footnote{\url{https://rprepo.readthedocs.io/en/latest/reliability_problems.html}}
	where data sets, models, and methods can be made available for testing and benchmarking.}

\section*{Acknowledgments}
We thank Dr.\ Emiliano Torre for helpful discussions.


\section{Introduction}
Astronomy and Astrophysics (AA) is one of the research areas in Physics that needs more and more high performing software and infrastructures, as the necessity for supercomputers arises both in the observational and theoretical realms of AA.
The amount of data produced by the upcoming generation of surveys and scientific instruments (e.g.  Square Kilometer Array,  Cherenkov Telescope Array,  Extremely Large Telescope E-ELT,  James Webb Space Telescope,  Euclid satellite, and eROSITA All-Sky Survey), needs more and more resources to be efficiently post-processed, analyzed and stored.
Moreover, numerical simulations, a theoretical counterpart capable of reproducing the formation and evolution of the cosmic structures of our Universe, must reach both larger volumes and higher resolutions to cope with a large amount of data of the upcoming surveys.

In the last decade, the National Institute of Astrophysics in Italy (INAF)  contributed to a number of HPC and HTC projects  (e.g. ExaNeSt \citep{KATEVENIS201858, 8049832}, EuroExa, EGI-Engage \citep{BERTOCCO201836}, EOSC-Pilot, DHTCS-IT).
Moreover, INAF recognized the importance to offer computing facilities of medium size to its user community and to invest in developing know-how in computing and data analytic.

In this paper, we present the experiment to coordinate the use of, and access to,  high throughput computing (HTC) and high-performance computing (HPC) and data processing resources.

\section{Scope and objective of the project}
CHIPP is a coordinated action supported by INAF and based on existing infrastructure and benefit of the know-how offered by the involved centres.   CHIPP main objectives are:
\begin{itemize}
    \item  Investigate to what extent the Italian astronomical community is interested in using a distributed computing infrastructure;
    \item Investigate whether the infrastructure meets the Astronomers requirements and collect comment and suggestions to optimize it;
    \item Investigate the best approach to offer the resources (e.g. periodic call, rolling based, on-demand access)
    \item Implement efficient user support and investigate which support level is required (system management, support for software development, support for optimization and debugging)
\end{itemize}

This project is the prototype and test case for the development of an extensive distributed computing infrastructure for astronomers able to offer multiple resources: HPC, HTC, Cloud.

\section{CHIPP computing resources}
The CHIPP project benefits of two computing centres located at  INAF--OATs and INAF--OACt.

The HOTCAT Cluster at INAF--OATs \citep{P6.7_adassxxix} is an HPC infrastructure with 1400 INTEL Haswell E5-4627v3 cores with 6GB RAM per Core (8.5TB RAM total) and 500 TB parallel storage based on BeeGFS. The interconnect is Infiniband ConnectX -3 Pro Dual QSFP+ 54Gbs. Beside the HPC cluster, INAF--OATs is also providing an OpenStack based cloud stack with 200INTEL Westmere E5620 cores with 8GB RAM per Core and 75 TB Swift ObjectStorage.

INAF--OACt MUP cluster is a HTC infrastructure with 384 INTEL E5-2620V2  with  5.2GB RAM per Core (1TB RAM total) and  70 TB parallel storage (NFS).  The interconnect is a 10 Gbs Ethernet network.

All the computing infrastructures are equipped with more than 60 software environment for Astronomical data reduction and analysis. They offer tools for software development, profiling and debugging.

\section{CHIPP Implementation}
CHIPP pilot is coordinating the services offered by the two computing centres, and it is verifying that the INAF community is profiting successfully of the computing resources.

The computing centres provide the system support and the installation and maintenance of libraries and tools. During this first implementation of the pilot project, the computing centres are not providing any support to optimize and debug users codes.
Due to a large number of requests for this type of service,  in the new implementation of the project, we will extend our support towards software optimization and debugging.

CHIPP collects the requirements and suggestions from the users to improve the platforms.  Computing centres provide customized environments based on the collected requirements.

\begin{table}[!ht]
\caption{The results of the four calls for proposals. For each call we present the number of submitted proposals, the number of accepted proposals, the total amount of core hours reserved for all the projects. We report also the completion rate, i.e the percentage of core hours actually consumed.}
\smallskip
\begin{center}
{\small
\begin{tabular}{lcccc}
\tableline
\noalign{\smallskip}
            & I Call     & II Call & III Call & IV call  \\
\noalign{\smallskip}
\tableline
\noalign{\smallskip}
Date &  15 May 2017 & 15 Jan 2018 & 30 July 2018 & 30 May 2019 \\
\# of proposals         & 25         & 14      & 9        & 13       \\
\# of proposal accepted & 16         & 14      & 9        & 13       \\
Core hours allocated    & $2.5x10^6$ & $1.8x10^6$ & $1.2x10^6$  & $1.4x10^6$  \\
Completion rate         & 33\%       & 50\%    & 55\%     & on-going \\
\noalign{\smallskip}
\tableline\
\end{tabular}
}
\end{center}
\label{table1}
\end{table}

The main CHIPP activity is promoting periodic competitive calls for computing resources, one every 6 months for large projects (~80000 core hours) and rolling open calls for small projects (<10000 core hours) of one month. Projects supported by CHIPP are chosen based on innovation potential, scientific excellence and relevance criteria.

In Table~\ref{table1}, we show the results of the 4 call for proposals.
The number of proposals presented during the first call was extremely high compared to the others; then it is steadily around 10 to 15  proposals each call.
According to our experience,  that corresponds to greater user awareness of what a computing resource can offer in terms of capabilities and environment.

During the project, we also modify the way a user can ask for computing resources,
thanks to the introduction of the rolling open calls.
This kind of calls allows astronomers with an un-planned need of computing resources to access to the infrastructure efficiently.

\section{Conclusion and future activities}

The INAF CHIPP pilot project is offering a distributed computing and storage resources to astronomers and projects on a call based approach.

CHIPP is a successful experiment that aims to help grow a community of experts in numerical AA and consolidate know--how in usage, maintenance and
support of computing resources.

The use of distributed computing infrastructure instead of a single computing centre is an architectural choice, in line with the architecture of the  European Open Science Cloud. That allows us to experiment with the operations and services activities necessary in more significant projects as the SKA Regional Center networks.

The small or middle-sized resources offered in CHIPP, are excellent for developing and debugging codes, medium-size production activities, data analysis, and according to our experience, they respond to a specific community requirement,  not covered by supercomputing centres.
CHIPP resources can also be beneficial for small (and large) projects during their start-up when they need computing resources that are not offered by the project yet.

CHIPP is a successful experiment to define requirements, investigate the type of use and necessities of a broad astronomical community.
It is offering support to astronomers for the use of the resources and building science platforms based singularity containers, Jupyter notebooks and/or remote desktop.

The experience gained during the project and the requisites collected are the foundations for the design and development of an extensive distributed computing infrastructure for astronomy in Italy (Tier-1 like): the Data-Star project.