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

## 2018 |

Kramer, Boris; Gorodetsky, Alex System identification via CUR-factored Hankel approximation Journal Article SIAM Journal on Scientific Computing, 40 (2), pp. A848–A866, 2018, ISSN: 1095-7197. Abstract | Links | BibTeX | Tags: Low-rank approximation, model reduction, System Identification @article{Kramer2018, title = {System identification via CUR-factored Hankel approximation}, author = {Boris Kramer and Alex Gorodetsky}, url = {http://www.alexgorodetsky.com/wp-content/uploads/2018/06/sisc_cur_sysid.pdf}, doi = {10.1137/17M1137632}, issn = {1095-7197}, year = {2018}, date = {2018-03-15}, journal = {SIAM Journal on Scientific Computing}, volume = {40}, number = {2}, pages = {A848–A866}, abstract = {Subspace-based system identification for dynamical systems is a sound, system-theoretic way to obtain linear, time-invariant system models from data. The interplay of data and systems theory is reflected in the Hankel matrix, a block-structured matrix whose factorization is used for system identification. For systems with many inputs, many outputs, or large time-series of system-response data, established methods based on the singular value decomposition (SVD)---such as the eigensystem realization algorithm (ERA)---are prohibitively expensive. In this paper, we propose an algorithm to reduce the complexity of the ERA from cubic to linear, with respect to Hankel matrix size. Furthermore, our memory requirements scale at the same rate because we never require loading the entire Hankel matrix into memory. These reductions are realized by replacing the SVD with a CUR decomposition that directly seeks a low-rank approximation of the Hankel matrix. The CUR decomposition is obtained using a maximum-volume based cross approximation scheme that selects a small number rows and columns to form the row and column space of the approximation. We present a worst-case error bound for our resulting system identification algorithm, and we demonstrate its computational advantages and accuracy on a numerical example. The example demonstrates that the resulting identification yields almost indistinguishable results compared with the SVD-based ERA, yet comes with significant computational savings.}, keywords = {Low-rank approximation, model reduction, System Identification}, pubstate = {published}, tppubtype = {article} } Subspace-based system identification for dynamical systems is a sound, system-theoretic way to obtain linear, time-invariant system models from data. The interplay of data and systems theory is reflected in the Hankel matrix, a block-structured matrix whose factorization is used for system identification. For systems with many inputs, many outputs, or large time-series of system-response data, established methods based on the singular value decomposition (SVD)---such as the eigensystem realization algorithm (ERA)---are prohibitively expensive. In this paper, we propose an algorithm to reduce the complexity of the ERA from cubic to linear, with respect to Hankel matrix size. Furthermore, our memory requirements scale at the same rate because we never require loading the entire Hankel matrix into memory. These reductions are realized by replacing the SVD with a CUR decomposition that directly seeks a low-rank approximation of the Hankel matrix. The CUR decomposition is obtained using a maximum-volume based cross approximation scheme that selects a small number rows and columns to form the row and column space of the approximation. We present a worst-case error bound for our resulting system identification algorithm, and we demonstrate its computational advantages and accuracy on a numerical example. The example demonstrates that the resulting identification yields almost indistinguishable results compared with the SVD-based ERA, yet comes with significant computational savings. |