## 2020 |

Jakeman, John; Eldred, Michael S; Geraci, Gianluca; Gorodetsky, Alex Adaptive multi-index collocation for uncertainty quantification and sensitivity analysis Journal Article International Journal for Numerical Methods in Engineering, 121 (6), pp. 1314-1343, 2020. Abstract | Links | BibTeX | Tags: Multifidelity Methods, Sensitivity Analysis, Surrogate models, Uncertainty Quantification, Validation @article{Jakeman2020, title = {Adaptive multi-index collocation for uncertainty quantification and sensitivity analysis}, author = {John Jakeman and Michael S. Eldred and Gianluca Geraci and Alex Gorodetsky}, url = {https://arxiv.org/abs/1909.13845 https://doi.org/10.1002/nme.6268}, doi = {https://doi.org/10.1002/nme.6268}, year = {2020}, date = {2020-02-19}, journal = {International Journal for Numerical Methods in Engineering}, volume = {121}, number = {6}, pages = {1314-1343}, abstract = {Summary In this paper, we present an adaptive algorithm to construct response surface approximations of high-fidelity models using a hierarchy of lower fidelity models. Our algorithm is based on multi-index stochastic collocation and automatically balances physical discretization error and response surface error to construct an approximation of model outputs. This surrogate can be used for uncertainty quantification (UQ) and sensitivity analysis (SA) at a fraction of the cost of a purely high-fidelity approach. We demonstrate the effectiveness of our algorithm on a canonical test problem from the UQ literature and a complex multiphysics model that simulates the performance of an integrated nozzle for an unmanned aerospace vehicle. We find that, when the input-output response is sufficiently smooth, our algorithm produces approximations that can be over two orders of magnitude more accurate than single fidelity approximations for a fixed computational budget.}, keywords = {Multifidelity Methods, Sensitivity Analysis, Surrogate models, Uncertainty Quantification, Validation}, pubstate = {published}, tppubtype = {article} } Summary In this paper, we present an adaptive algorithm to construct response surface approximations of high-fidelity models using a hierarchy of lower fidelity models. Our algorithm is based on multi-index stochastic collocation and automatically balances physical discretization error and response surface error to construct an approximation of model outputs. This surrogate can be used for uncertainty quantification (UQ) and sensitivity analysis (SA) at a fraction of the cost of a purely high-fidelity approach. We demonstrate the effectiveness of our algorithm on a canonical test problem from the UQ literature and a complex multiphysics model that simulates the performance of an integrated nozzle for an unmanned aerospace vehicle. We find that, when the input-output response is sufficiently smooth, our algorithm produces approximations that can be over two orders of magnitude more accurate than single fidelity approximations for a fixed computational budget. |

## 2019 |

Wildey, T; Gorodetsky, Alex A; Belme, A C; Shadid, John N Robust uncertainty quantification using response surface approximations of discontinuous functions Journal Article International Journal for Uncertainty Quantification, 9 (5), pp. 415–437, 2019, ISSN: 2152-5080. Abstract | Links | BibTeX | Tags: Support Vector Machines, Surrogate models, Uncertainty Quantification @article{Wildey2019, title = {Robust uncertainty quantification using response surface approximations of discontinuous functions}, author = {T. Wildey and Alex A. Gorodetsky and A.C. Belme and John N. Shadid}, url = {http://www.alexgorodetsky.com/wp-content/uploads/2019/04/robust_UQ_discontinuous_surrogate.pdf doi:10.1615/Int.J.UncertaintyQuantification.2019026974}, doi = {10.1615/Int.J.UncertaintyQuantification.2019026974 }, issn = {2152-5080}, year = {2019}, date = {2019-04-30}, journal = {International Journal for Uncertainty Quantification}, volume = {9}, number = {5}, pages = {415--437}, abstract = {This paper considers response surface approximations for discontinuous quantities of interest. Our objective is not to adaptively characterize the interface defining the discontinuity. Instead, we utilize an epistemic description of the uncertainty in the location of a discontinuity to produce robust bounds on sample-based estimates of probabilistic quantities of interest. We demonstrate that two common machine learning strategies for classification, one based on nearest neighbors (Voronoi cells) and one based on support vector machines, provide reasonable descriptions of the region where the discontinuity may reside. In higher dimensional spaces, we demonstrate that support vector machines are more accurate for discontinuities defined by smooth interfaces. We also show how gradient information, often available via adjoint-based approaches, can be used to define indicators to effectively detect a discontinuity and to decompose the samples into clusters using an unsupervised learning technique. Numerical results demonstrate the epistemic bounds on probabilistic quantities of interest for simplistic models and for a compressible fluid model with a shock-induced discontinuity.}, keywords = {Support Vector Machines, Surrogate models, Uncertainty Quantification}, pubstate = {published}, tppubtype = {article} } This paper considers response surface approximations for discontinuous quantities of interest. Our objective is not to adaptively characterize the interface defining the discontinuity. Instead, we utilize an epistemic description of the uncertainty in the location of a discontinuity to produce robust bounds on sample-based estimates of probabilistic quantities of interest. We demonstrate that two common machine learning strategies for classification, one based on nearest neighbors (Voronoi cells) and one based on support vector machines, provide reasonable descriptions of the region where the discontinuity may reside. In higher dimensional spaces, we demonstrate that support vector machines are more accurate for discontinuities defined by smooth interfaces. We also show how gradient information, often available via adjoint-based approaches, can be used to define indicators to effectively detect a discontinuity and to decompose the samples into clusters using an unsupervised learning technique. Numerical results demonstrate the epistemic bounds on probabilistic quantities of interest for simplistic models and for a compressible fluid model with a shock-induced discontinuity. |

Gorodetsky, Alex; Karaman, Sertac; Marzouk, Youssef A Continuous Analogue of the Tensor-Train Decomposition Journal Article Computer Methods in Applied Mechanics and Engineering, 347 , pp. 59-84, 2019. Abstract | Links | BibTeX | Tags: Chebfun, Low-rank approximation, Polynomial Approximation, Surrogate models, Tensor decompositions, Tensor-train decomposition, Uncertainty Quantification @article{Gorodetsky2018d, title = {A Continuous Analogue of the Tensor-Train Decomposition}, author = {Alex Gorodetsky and Sertac Karaman and Youssef Marzouk}, url = {http://www.alexgorodetsky.com/wp-content/uploads/2018/12/ftrain.pdf }, doi = {10.1016/j.cma.2018.12.015}, year = {2019}, date = {2019-04-15}, journal = {Computer Methods in Applied Mechanics and Engineering}, volume = {347}, pages = {59-84}, abstract = {We develop new approximation algorithms and data structures for representing and computing with multivariate functions using the functional tensor-train (FT), a continuous extension of the tensor-train (TT) decomposition. The FT represents functions using a tensor-train ansatz by replacing the three-dimensional TT cores with univariate matrix-valued functions. The main contribution of this paper is a framework to compute the FT that employs adaptive approximations of univariate fibers, and that is not tied to any tensorized discretization. The algorithm can be coupled with any univariate linear or nonlinear approximation procedure. We demonstrate that this approach can generate multivariate function approximations that are several orders of magnitude more accurate, for the same cost, than those based on the conventional approach of compressing the coefficient tensor of a tensor-product basis. Our approach is in the spirit of other continuous computation packages such as Chebfun, and yields an algorithm which requires the computation of âcontinuousâ matrix factorizations such as the LU and QR decompositions of vector-valued functions. To support these developments, we describe continuous versions of an approximate maximum-volume cross approximation algorithm and of a rounding algorithm that re-approximates an FT by one of lower ranks. We demonstrate that our technique improves accuracy and robustness, compared to TT and quantics-TT approaches with fixed parameterizations, of high-dimensional integration, differentiation, and approximation of functions with local features such as discontinuities and other nonlinearities.}, keywords = {Chebfun, Low-rank approximation, Polynomial Approximation, Surrogate models, Tensor decompositions, Tensor-train decomposition, Uncertainty Quantification}, pubstate = {published}, tppubtype = {article} } We develop new approximation algorithms and data structures for representing and computing with multivariate functions using the functional tensor-train (FT), a continuous extension of the tensor-train (TT) decomposition. The FT represents functions using a tensor-train ansatz by replacing the three-dimensional TT cores with univariate matrix-valued functions. The main contribution of this paper is a framework to compute the FT that employs adaptive approximations of univariate fibers, and that is not tied to any tensorized discretization. The algorithm can be coupled with any univariate linear or nonlinear approximation procedure. We demonstrate that this approach can generate multivariate function approximations that are several orders of magnitude more accurate, for the same cost, than those based on the conventional approach of compressing the coefficient tensor of a tensor-product basis. Our approach is in the spirit of other continuous computation packages such as Chebfun, and yields an algorithm which requires the computation of âcontinuousâ matrix factorizations such as the LU and QR decompositions of vector-valued functions. To support these developments, we describe continuous versions of an approximate maximum-volume cross approximation algorithm and of a rounding algorithm that re-approximates an FT by one of lower ranks. We demonstrate that our technique improves accuracy and robustness, compared to TT and quantics-TT approaches with fixed parameterizations, of high-dimensional integration, differentiation, and approximation of functions with local features such as discontinuities and other nonlinearities. |

## 2018 |

Eldred, Michael S; Geraci, Gianluca; Gorodetsky, Alex; Jakeman, John Multilevel-Multifidelity Approaches for Forward UQ in the DARPA SEQUOIA project Inproceedings 2018 AIAA Non-Deterministic Approaches Conference, AIAA SciTech Forum, Kissimmee, Florida, 2018. Abstract | Links | BibTeX | Tags: Multifidelity Methods, Polynomial Approximation, Surrogate models, Tensor decompositions @inproceedings{Eldred2018, title = {Multilevel-Multifidelity Approaches for Forward UQ in the DARPA SEQUOIA project}, author = {Michael S. Eldred and Gianluca Geraci and Alex Gorodetsky and John Jakeman}, url = {https://alexgorodetsky.com/wp-content/uploads/2018/02/main-1.pdf}, doi = {10.2514/6.2018-1179 }, year = {2018}, date = {2018-01-08}, booktitle = {2018 AIAA Non-Deterministic Approaches Conference, AIAA SciTech Forum}, address = {Kissimmee, Florida}, abstract = {Within the SEQUOIA project, funded by the DARPA EQUiPS program, we pursue algorithmic approaches that enable comprehensive design under uncertainty, through in- clusion of aleatory/parametric and epistemic/model form uncertainties within scalable for- ward/inverse UQ approaches. These statistical methods are embedded within design pro- cesses that manage computational expense through active subspace, multilevel-multifidelity, and reduced-order modeling approximations. To demonstrate these methods, we focus on the design of devices that involve multi-physics interactions in advanced aerospace vehicles. A particular problem of interest is the shape design of nozzles for advanced vehicles such as the Northrop Grumman UCAS X-47B, involving coupled aero-structural-thermal simu- lations for nozzle performance. In this paper, we explore a combination of multilevel and multifidelity forward and inverse UQ algorithms to reduce the overall computational cost of the analysis by leveraging hierarchies of model form (i.e., multifidelity hierarchies) and solution discretization (i.e., multilevel hierarchies) in order of exploit trade offs between solution accuracy and cost. In particular, we seek the most cost effective fusion of informa- tion across complex multi-dimensional modeling hierarchies. Results to date indicate the utility of multiple approaches, including methods that optimally allocate resources when estimator variance varies smoothly across levels, methods that allocate sufficient sampling density based on sparsity estimates, and methods that employ greedy multilevel refinement.}, keywords = {Multifidelity Methods, Polynomial Approximation, Surrogate models, Tensor decompositions}, pubstate = {published}, tppubtype = {inproceedings} } Within the SEQUOIA project, funded by the DARPA EQUiPS program, we pursue algorithmic approaches that enable comprehensive design under uncertainty, through in- clusion of aleatory/parametric and epistemic/model form uncertainties within scalable for- ward/inverse UQ approaches. These statistical methods are embedded within design pro- cesses that manage computational expense through active subspace, multilevel-multifidelity, and reduced-order modeling approximations. To demonstrate these methods, we focus on the design of devices that involve multi-physics interactions in advanced aerospace vehicles. A particular problem of interest is the shape design of nozzles for advanced vehicles such as the Northrop Grumman UCAS X-47B, involving coupled aero-structural-thermal simu- lations for nozzle performance. In this paper, we explore a combination of multilevel and multifidelity forward and inverse UQ algorithms to reduce the overall computational cost of the analysis by leveraging hierarchies of model form (i.e., multifidelity hierarchies) and solution discretization (i.e., multilevel hierarchies) in order of exploit trade offs between solution accuracy and cost. In particular, we seek the most cost effective fusion of informa- tion across complex multi-dimensional modeling hierarchies. Results to date indicate the utility of multiple approaches, including methods that optimally allocate resources when estimator variance varies smoothly across levels, methods that allocate sufficient sampling density based on sparsity estimates, and methods that employ greedy multilevel refinement. |

Gorodetsky, Alex; Jakeman, John Gradient-based Optimization for Regression in the Functional Tensor-Train Format Journal Article Journal of Computational Physics, 374 , pp. 1219–1238, 2018. Abstract | Links | BibTeX | Tags: Regression, Surrogate models, Tensor decompositions @article{Gorodetsky2018b, title = {Gradient-based Optimization for Regression in the Functional Tensor-Train Format}, author = {Alex Gorodetsky and John Jakeman}, url = {https://arxiv.org/abs/1801.00885v2 https://www.sciencedirect.com/science/article/pii/S0021999118305321}, doi = {10.1016/j.jcp.2018.08.010}, year = {2018}, date = {2018-01-01}, journal = {Journal of Computational Physics}, volume = {374}, pages = {1219--1238}, abstract = {We consider the task of low-multilinear-rank functional regression, i.e., learning a low-rank parametric representation of functions from scattered real-valued data. Our first contribution is the development and analysis of an efficient gradient computation that enables gradient-based optimization procedures, including stochastic gradient descent and quasi-Newton methods, for learning the parameters of a functional tensor-train (FT). The functional tensor-train uses the tensor-train (TT) representation of low-rank arrays as an ansatz for a class of low-multilinear-rank functions. The FT is represented by a set of matrix-valued functions that contain a set of univariate functions, and the regression task is to learn the parameters of these univariate functions. Our second contribution demonstrates that using nonlinearly parameterized univariate functions, e.g., symmetric kernels with moving centers, within each core can outperform the standard approach of using a linear expansion of basis functions. Our final contributions are new rank adaptation and group-sparsity regularization procedures to minimize overfitting. We use several benchmark problems to demonstrate at least an order of magnitude lower accuracy with gradient-based optimization methods than standard alternating least squares procedures in the low-sample number regime. We also demonstrate an order of magnitude reduction in accuracy on a test problem resulting from using nonlinear parameterizations over linear parameterizations. Finally we compare regression performance with 22 other nonparametric and parametric regression methods on 10 real-world data sets. We achieve top-five accuracy for seven of the data sets and best accuracy for two of the data sets. These rankings are the best amongst parametric models and competetive with the best non-parametric methods.}, keywords = {Regression, Surrogate models, Tensor decompositions}, pubstate = {published}, tppubtype = {article} } We consider the task of low-multilinear-rank functional regression, i.e., learning a low-rank parametric representation of functions from scattered real-valued data. Our first contribution is the development and analysis of an efficient gradient computation that enables gradient-based optimization procedures, including stochastic gradient descent and quasi-Newton methods, for learning the parameters of a functional tensor-train (FT). The functional tensor-train uses the tensor-train (TT) representation of low-rank arrays as an ansatz for a class of low-multilinear-rank functions. The FT is represented by a set of matrix-valued functions that contain a set of univariate functions, and the regression task is to learn the parameters of these univariate functions. Our second contribution demonstrates that using nonlinearly parameterized univariate functions, e.g., symmetric kernels with moving centers, within each core can outperform the standard approach of using a linear expansion of basis functions. Our final contributions are new rank adaptation and group-sparsity regularization procedures to minimize overfitting. We use several benchmark problems to demonstrate at least an order of magnitude lower accuracy with gradient-based optimization methods than standard alternating least squares procedures in the low-sample number regime. We also demonstrate an order of magnitude reduction in accuracy on a test problem resulting from using nonlinear parameterizations over linear parameterizations. Finally we compare regression performance with 22 other nonparametric and parametric regression methods on 10 real-world data sets. We achieve top-five accuracy for seven of the data sets and best accuracy for two of the data sets. These rankings are the best amongst parametric models and competetive with the best non-parametric methods. |

## 2017 |

Gorodetsky, Alex Massachusetts Institute of Technology, 2017. Abstract | Links | BibTeX | Tags: Dynamic Programming, Kalman Filtering, Stochastic Optimal Control, Surrogate models, Tensor decompositions @phdthesis{Gorodetsky2017b, title = {Continuous low-rank tensor decompositions, with applications to stochastic optimal control and data assimilation}, author = {Alex Gorodetsky}, url = {http://hdl.handle.net/1721.1/108918}, year = {2017}, date = {2017-02-02}, address = {Cambridge, MA}, school = {Massachusetts Institute of Technology}, abstract = {Optimal decision making under uncertainty is critical for control and optimization of complex systems. However, many techniques for solving problems such as stochastic optimal control and data assimilation encounter the curse of dimensionality when too many state variables are involved. In this thesis, we propose a framework for computing with high-dimensional functions that mitigates this exponential growth in complexity for problems with separable structure. Our framework tightly integrates two emerging areas: tensor decompositions and continuous computation. Tensor decompositions are able to effectively compress and operate with low-rank multidimensional arrays. Continuous computation is a paradigm for computing with functions instead of arrays, and it is best realized by Chebfun, a MATLAB package for computing with functions of up to three dimensions. Continuous computation provides a natural framework for building numerical algorithms that effectively, naturally, and automatically adapt to problem structure. The first part of this thesis describes a compressed continuous computation framework centered around a continuous analogue to the (discrete) tensor-train decomposition called the function-train decomposition. Computation with the function-train requires continuous matrix factorizations and continuous numerical linear algebra. Continuous analogues are presented for performing cross approximation; rounding; multilinear algebra operations such as addition, multiplication, integration, and differentiation; and continuous, rank-revealing, alternating least squares. Advantages of the function-train over the tensor-train include the ability to adaptively approximate functions and the ability to compute with functions that are parameterized differently. For example, while elementwise multiplication between tensors of different sizes is undefined, functions in FT format can be readily multiplied together. Next, we develop compressed versions of value iteration, policy iteration, and multilevel algorithms for solving dynamic programming problems arising in stochastic optimal control. These techniques enable computing global solutions to a broader set of problems, for example those with non-affine control inputs, than previously possible. Examples are presented for motion planning with robotic systems that have up to seven states. Finally, we use the FT to extend integration-based Gaussian filtering to larger state spaces than previously considered. Examples are presented for dynamical systems with up to twenty states.}, keywords = {Dynamic Programming, Kalman Filtering, Stochastic Optimal Control, Surrogate models, Tensor decompositions}, pubstate = {published}, tppubtype = {phdthesis} } Optimal decision making under uncertainty is critical for control and optimization of complex systems. However, many techniques for solving problems such as stochastic optimal control and data assimilation encounter the curse of dimensionality when too many state variables are involved. In this thesis, we propose a framework for computing with high-dimensional functions that mitigates this exponential growth in complexity for problems with separable structure. Our framework tightly integrates two emerging areas: tensor decompositions and continuous computation. Tensor decompositions are able to effectively compress and operate with low-rank multidimensional arrays. Continuous computation is a paradigm for computing with functions instead of arrays, and it is best realized by Chebfun, a MATLAB package for computing with functions of up to three dimensions. Continuous computation provides a natural framework for building numerical algorithms that effectively, naturally, and automatically adapt to problem structure. The first part of this thesis describes a compressed continuous computation framework centered around a continuous analogue to the (discrete) tensor-train decomposition called the function-train decomposition. Computation with the function-train requires continuous matrix factorizations and continuous numerical linear algebra. Continuous analogues are presented for performing cross approximation; rounding; multilinear algebra operations such as addition, multiplication, integration, and differentiation; and continuous, rank-revealing, alternating least squares. Advantages of the function-train over the tensor-train include the ability to adaptively approximate functions and the ability to compute with functions that are parameterized differently. For example, while elementwise multiplication between tensors of different sizes is undefined, functions in FT format can be readily multiplied together. Next, we develop compressed versions of value iteration, policy iteration, and multilevel algorithms for solving dynamic programming problems arising in stochastic optimal control. These techniques enable computing global solutions to a broader set of problems, for example those with non-affine control inputs, than previously possible. Examples are presented for motion planning with robotic systems that have up to seven states. Finally, we use the FT to extend integration-based Gaussian filtering to larger state spaces than previously considered. Examples are presented for dynamical systems with up to twenty states. |

## 2014 |

Gorodetsky, Alex; Marzouk, Youssef Efficient Localization of Discontinuities in Complex Computational Simulations Journal Article SIAM Journal on Scientific Computing, 36 (6), pp. A2584-A2610, 2014, ISSN: 1095-7197. Abstract | Links | BibTeX | Tags: Active Learning, Support Vector Machines, Surrogate models @article{Gorodetsky2014, title = {Efficient Localization of Discontinuities in Complex Computational Simulations }, author = {Alex Gorodetsky and Youssef Marzouk}, url = {https://alexgorodetsky.com/wp-content/uploads/2018/02/discontinuity_detection.pdf}, doi = {10.1137/140953137}, issn = {1095-7197}, year = {2014}, date = {2014-11-04}, journal = {SIAM Journal on Scientific Computing}, volume = {36}, number = {6}, pages = {A2584-A2610}, abstract = {Surrogate models for computational simulations are input-output approximations that allow computationally intensive analyses, such as uncertainty propagation and inference, to be performed efficiently. When a simulation output does not depend smoothly on its inputs, the error and convergence rate of many approximation methods deteriorate substantially. This paper details a method for efficiently localizing discontinuities in the input parameter domain, so that the model output can be approximated as a piecewise smooth function. The approach comprises an initialization phase, which uses polynomial annihilation to assign function values to different regions and thus seed an automated labeling procedure, followed by a refinement phase that adaptively updates a kernel support vector machine representation of the separating surface via active learning. The overall approach avoids structured grids and exploits any available simplicity in the geometry of the separating surface, thus reducing the number of model evaluations required to localize the discontinuity. The method is illustrated on examples of up to eleven dimensions, including algebraic models and ODE/PDE systems, and demonstrates improved scaling and efficiency over other discontinuity localization approaches.}, keywords = {Active Learning, Support Vector Machines, Surrogate models}, pubstate = {published}, tppubtype = {article} } Surrogate models for computational simulations are input-output approximations that allow computationally intensive analyses, such as uncertainty propagation and inference, to be performed efficiently. When a simulation output does not depend smoothly on its inputs, the error and convergence rate of many approximation methods deteriorate substantially. This paper details a method for efficiently localizing discontinuities in the input parameter domain, so that the model output can be approximated as a piecewise smooth function. The approach comprises an initialization phase, which uses polynomial annihilation to assign function values to different regions and thus seed an automated labeling procedure, followed by a refinement phase that adaptively updates a kernel support vector machine representation of the separating surface via active learning. The overall approach avoids structured grids and exploits any available simplicity in the geometry of the separating surface, thus reducing the number of model evaluations required to localize the discontinuity. The method is illustrated on examples of up to eleven dimensions, including algebraic models and ODE/PDE systems, and demonstrates improved scaling and efficiency over other discontinuity localization approaches. |