Dec 2024· Numerical Linear Algebra with Applications· Vol 33· 3 citations· 37 references
MathematicsComputer Science
TL;DR
This work presents the tree tensor network Nyström (TTNN), an algorithm that extends recent research on streamable tensor approximation to the more general tree tensor network format, enabling a unified treatment of various existing methods.
Abstract
In this work, we present the tree tensor network Nyström (TTNN), an algorithm that extends recent research on streamable tensor approximation, such as for Tucker and tensor‐train formats, to the more general tree tensor network format, enabling a unified treatment of various existing methods. Our method retains the key features of the generalized Nyström approximation for matrices, that is, randomized, single‐pass, streamable, and cost‐effective. Additionally, the structure of the sketches allows for parallel implementation. We provide a deterministic error bound for the algorithm and, in the specific case of Gaussian dimension reduction maps, also a probabilistic one. We also introduce a sequential variant of the algorithm, referred to as sequential tree tensor network Nyström (STTNN), which offers better performance for dense tensors. Furthermore, both algorithms are well‐suited for the recompression or rounding of tensors in the tree tensor network format. Numerical experiments highlight the efficiency and effectiveness of the proposed methods.
A new SVD-based tensor decomposition method for tensor networks with arbitrary graph topologies is introduced, and it is found that the graph-format representation attains comparable or better accuracy than the classical tensor train and hierarchical Tucker tensor formats, while using substantially fewer degrees of freedom at lower computational cost.
Tensor networks are powerful formats for compressing large-scale data. However, their application to general data processing has been limited by the difficulty of performing nonlinear operations. Here, we introduce iterative tensor network transformations (ITNTs), a general algorithmic framework for the element-wise evaluation of elementary and nonlinear filtering functions on data encoded as tensor trains (TTs), a class of tensor networks. Our approach operates entirely in the compressed domain, enabling efficient computation on exponentially large datasets while maintaining a controlled computational cost. We demonstrate its power in two key areas: (I) evaluating highly nonlinear elementary and filtering functions on a 3D reactive flow field, enabling high-fidelity reaction rate computation and region filtering, and (II) finding extrema in complex optimization problems, such as solving Max-SAT instances on spaces up to $2^{70}$ configurations. These results establish ITNT as a foundational tool that provides tensor network methods with the capability for general-purpose data science and large-scale optimization.
Xiao Wang, Tomohiro Hashizume, Pia Siegl et al.· 2 citations
An efficient numerical approach for compressing a high-dimensional discrete distribution function into a non-negative tensor train (NTT) format and observing that the proposed NTT fitting procedure exhibits drastically faster convergence than an alternative multiplicative update method that has been previously proposed is observed.
Xun Tang, R. Dwaraknath, Lexing Ying· SIAM Journal on Scientific C...· 0 citations
Traditional model reduction techniques for neural network compression usually leverage existing matrix/tensor decomposition methods to explore the redundancy among model parameters, which may overlook the local structures of the models. In this work, we propose a novel low-rank approximation algorithm, called Dimension-Augmented Tensor-Train (DATT) decomposition, which integrates dimension slicing with the Tensor-Train decomposition. DATT allows different partitions to be represented using distinct, non-shared spanning sets. This enables the decomposition to adapt more flexibly to localized structure, potentially achieving better compression. With the localized low-rank structures, DATT provides a more compact representation of neural network weights. We evaluated the performance of DATT with the other state-of-the-art low-rank approximation-based model compression algorithms, and demonstrated that DATT outperforms them in terms of parameter reduction and model accuracy. In particular, for compressing ResNet-20 on CIFAR-10, DATT achieves a 77.00% reduction in parameters with only a 0.37% drop in top-1 accuracy.
Yu-Chuan Tai, Cheng-Yu Sie, Che-Rung Lee· Annual International Compute...· 0 citations
Two randomized algorithms within the sketched GMRES framework that replace full Arnoldi orthogonalization with short recurrences are proposed, providing robustness across a wide range of problems and outperform standard low-rank Tucker solvers in symmetric and non-symmetric settings.
Alberto Bucci, Martina Iannacito, M. Pasha et al.· 0 citations
This paper proposes a novel Tensor Train (TT)-based tensor-on-tensor regression optimization framework for variable selection based on mode-1 hyperslice sparsity. The formulation incorporates an l2,0-regularized term on the first TT-core while imposing Stiefel manifold constraints on the remaining M−1 TT-cores. Leveraging the property that the group sparsity of the first core is equivalent to the hyperslice sparsity of the global structure, we establish theoretical guarantees for the uniform variable-selection consistency of the proposed model. To efficiently solve the proposed model, we design an alternating iterative algorithm equipped with a preconditioned metric and prove its convergence to a critical point. Extensive numerical experiments on both synthetic and real-world datasets demonstrate that the numerical solutions generated by our algorithm exhibit exact support recovery in practice, tightly aligning with our theoretical analysis.