Randomized Algorithms for Rounding in the Tensor-Train Format

dc.contributor.authorAl Daas, Hussamen
dc.contributor.authorBallard, Greyen
dc.contributor.authorCazeaux, Paulen
dc.contributor.authorHallman, Ericen
dc.contributor.authorMiedlar, Agnieszkaen
dc.contributor.authorPasha, Mirjetaen
dc.contributor.authorReid, Tim W.en
dc.contributor.authorSaibaba, Arvind K.en
dc.date.accessioned2024-02-12T16:08:50Zen
dc.date.available2024-02-12T16:08:50Zen
dc.date.issued2023-01-27en
dc.description.abstractThe tensor-train (TT) format is a highly compact low-rank representation for high-dimensional tensors. TT is particularly useful when representing approximations to the solutions of certain types of parametrized partial differential equations. For many of these problems, computing the solution explicitly would require an infeasible amount of memory and computational time. While the TT format makes these problems tractable, iterative techniques for solving the PDEs must be adapted to perform arithmetic while maintaining the implicit structure. The fundamental operation used to maintain feasible memory and computational time is called rounding, which truncates the internal ranks of a tensor already in TT format. We propose several randomized algorithms for this task that are generalizations of randomized low-rank matrix approximation algorithms and provide significant reduction in computation compared to deterministic TT-rounding algorithms. Randomization is particularly effective in the case of rounding a sum of TT-tensors (where we observe 20\times speedup), which is the bottleneck computation in the adaptation of GMRES to vectors in TT format. We present the randomized algorithms and compare their empirical accuracy and computational time with deterministic alternatives.en
dc.description.versionPublished versionen
dc.format.extentPages A74-A95en
dc.format.extent22 page(s)en
dc.format.mimetypeapplication/pdfen
dc.identifier.doihttps://doi.org/10.1137/21M1451191en
dc.identifier.eissn1095-7197en
dc.identifier.issn1064-8275en
dc.identifier.issue1en
dc.identifier.urihttps://hdl.handle.net/10919/117944en
dc.identifier.volume45en
dc.language.isoenen
dc.publisherSiam Publicationsen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjecthigh-dimensional problemsen
dc.subjectrandomized algorithmsen
dc.subjecttensor decompositionsen
dc.subjecttensortrain formaten
dc.titleRandomized Algorithms for Rounding in the Tensor-Train Formaten
dc.title.serialSIAM Journal on Scientific Computingen
dc.typeArticle - Refereeden
dc.type.dcmitypeTexten
dc.type.otherArticleen
dc.type.otherJournalen
pubs.organisational-group/Virginia Techen
pubs.organisational-group/Virginia Tech/Scienceen
pubs.organisational-group/Virginia Tech/Science/Mathematicsen
pubs.organisational-group/Virginia Tech/All T&R Facultyen
pubs.organisational-group/Virginia Tech/Science/COS T&R Facultyen
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
SAMSI_Rand_Tensors.pdf
Size:
599.29 KB
Format:
Adobe Portable Document Format
Description:
Accepted version
License bundle
Now showing 1 - 1 of 1
Name:
license.txt
Size:
1.5 KB
Format:
Plain Text
Description: