## 2019 |

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. |

## 2015 |

Gorodetsky, Alex; Karaman, Sertac; Marzouk, Youssef Efficient High-Dimensional Stochastic Optimal Motion Control using Tensor-Train Decomposition Inproceedings Proceedings of Robotics: Science and Systems, Rome, Italy, 2015. Abstract | Links | BibTeX | Tags: Dynamic Programming, Motion Planning, Stochastic Optimal Control, Tensor-train decomposition @inproceedings{Gorodetsky2015, title = {Efficient High-Dimensional Stochastic Optimal Motion Control using Tensor-Train Decomposition}, author = {Alex Gorodetsky and Sertac Karaman and Youssef Marzouk}, url = {https://alexgorodetsky.com/wp-content/uploads/2018/02/p15.pdf}, doi = {10.15607/RSS.2015.XI.015}, year = {2015}, date = {2015-07-01}, booktitle = {Proceedings of Robotics: Science and Systems}, address = {Rome, Italy}, abstract = {Stochastic optimal control problems frequently arise as motion control problems in the context of robotics. Unfortunately, all existing approaches that guarantee arbitrary precision suffer from the curse of dimensionality: the computational effort invested by the algorithm grows exponentially fast with increasing dimensionality of the state space of the underlying dynamic system governing the robot. In this paper, we propose a novel algorithm that utilizes compressed representations to efficiently solve stochastic optimal control problems with arbitrary precision. The running time of the new algorithms scale linearly with increasing dimensionality of the state space! The running time also depends polynomially on the rank of the value function, a measure that quantifies the intrinsic geometric complexity of the value function, due to the geometry and physics embedded in the problem instance at hand. The new algorithms are based on the recent analysis and algorithms for tensor decomposition, generalizing matrix decomposition algorithms, e.g., the singular value decomposition, to three or more dimensions. In computational experiments, we show the computational effort of the new algorithm also scales linearly with the discretization resolution of the state space. We also demonstrate the new algorithm on a problem involving the perching of an aircraft, represented by a nonlinear non-holonomic longitudinal model with a seven-dimensional state space, the full numerical solution to which was not obtained before. In this example, we estimate that the proposed algorithm runs more than seven orders of magnitude faster, when compared to the naive value iteration}, keywords = {Dynamic Programming, Motion Planning, Stochastic Optimal Control, Tensor-train decomposition}, pubstate = {published}, tppubtype = {inproceedings} } Stochastic optimal control problems frequently arise as motion control problems in the context of robotics. Unfortunately, all existing approaches that guarantee arbitrary precision suffer from the curse of dimensionality: the computational effort invested by the algorithm grows exponentially fast with increasing dimensionality of the state space of the underlying dynamic system governing the robot. In this paper, we propose a novel algorithm that utilizes compressed representations to efficiently solve stochastic optimal control problems with arbitrary precision. The running time of the new algorithms scale linearly with increasing dimensionality of the state space! The running time also depends polynomially on the rank of the value function, a measure that quantifies the intrinsic geometric complexity of the value function, due to the geometry and physics embedded in the problem instance at hand. The new algorithms are based on the recent analysis and algorithms for tensor decomposition, generalizing matrix decomposition algorithms, e.g., the singular value decomposition, to three or more dimensions. In computational experiments, we show the computational effort of the new algorithm also scales linearly with the discretization resolution of the state space. We also demonstrate the new algorithm on a problem involving the perching of an aircraft, represented by a nonlinear non-holonomic longitudinal model with a seven-dimensional state space, the full numerical solution to which was not obtained before. In this example, we estimate that the proposed algorithm runs more than seven orders of magnitude faster, when compared to the naive value iteration |