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.
We address the problem of recovering highly oscillatory operators, represented as matrices with a fixed set of observed entries. Given that these matrices can be well compressed by butterfly matrix decomposition of levels requiring only degrees of freedom, we propose a novel reformulation of the butterfly structure as a compact tensor network. Specifically, we reshape the input matrix as an order dense tensor, and cast its butterfly decomposition as a tensor network consisting of order dense tensors. This enables efficient utilization of the existing software infrastructure for dense and sparse tensor computations. Next, we propose several tensor completion algorithms based on the tensor reformulation of butterfly format, and compare them against algorithms using the quantized tensor train (QTT) format. These algorithms leverage popular completion methods such as alternating least squares, gradient‐based optimization, and alternating directions fitting. Moreover, we propose a novel strategy that uses low‐rank matrix completion to efficiently generate an initial guess for the proposed algorithms. To demonstrate the efficiency and applicability of our proposed algorithms, we perform three numerical experiments using simulated oscillatory operators in seismic applications. In these experiments, we use observed entries in the input matrix and demonstrate an computational cost of the proposed algorithms, leading to speedups of orders of magnitude and significant accuracy improvements for large matrices compared to state‐of‐the‐art low‐rank matrix and QTT tensor completion algorithms.
Navjot Singh, Edgar Solomonik, X. Li et al.· Numerical Linear Algebra wit...· 0 citations
Online TT-ALS (Alternating Least Squares) is introduced, an algorithm that sequentially enforces orthogonality constraints that allows for efficient and exact updates of the core tensor while maintaining high reconstruction accuracy and is suitable for low-latency real-time processing applications.
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 computations are an important class of operations widely used in domains such as computational chemistry, machine learning, and various types of physical simulations that demand distributed-memory clusters. Recent work has shown that generating efficient mappings for multi-operator Directed Acyclic Graphs of distributed-memory tensor computations is possible by leveraging non-linear formulations underpinned by Satisfiability Modulo Theories (SMT) solvers. However, this approach is sensitive to the problem size, grid shape, and count of Processing Elements (PEs) given. We introduce a new method for automatically generating parametric mappings agnostic of the input problem sizes for the class of DAGs of tensor computations. The approach relies on three building blocks: the insight that in parametric DAGs not all parameters are equally important, an offline algorithm to generate a small bounded number of mapping classes – forming a family of mappings – and a sampling space that enables the generation of sufficiently large and diverse family of mapping classes. We show the effectiveness of our parametric mappings on a cluster of multi-GPUs, comparing against NVIDIA cuTensorNet, the Cyclops Tensor Framework (CTF) and PyTorch. Our mappings achieve speedups up to 22.1 × and 2.35 × over NVIDIA cuTensorNet, on matrix-based and tensor-based DAGs, respectively. When benchmarked against PyTorch, we observe speedups of 3.41 ×.
Botao Wu, Martin Kong· International Conference on...· 0 citations
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.
Alberto Bucci, Gianfranco Verzella· Numerical Linear Algebra wit...· 0 citations
Developing nonlinear models that are both expressive and computationally efficient remains a challenge in machine learning and nonlinear system identification. Tensor network kernel machines (TNKM) address this challenge by combining nonlinear feature representations with compact low-rank tensor-network parameterizations. However, practical and extensible software frameworks for developing TNKM models remain limited. In this work, we introduce"tnkm", an open-source Python library for constructing and training TNKM models using JAX. The library provides a unified interface for combining different feature maps, tensor-network architectures, and optimization strategies, including alternating least squares and gradient-based methods. We demonstrate the capabilities of"tnkm"on nonlinear benchmark problems, showing that the implemented models achieve competitive prediction accuracy while retaining compact parameterizations and efficient training. The proposed framework facilitates reproducible development and application of tensor-network-based learning methods.
Known for his clear and elegant writing style, Bertsekas shaped fields from control and optimization to large-scale computation and artificial intelligence.
