Linear algebra at exponential scale via tensor network dimension reduction

• URL: http://arxiv.org/abs/2606.15350v1
• Date: Sat, 13 Jun 2026 15:29:19 GMT
• Title: Linear algebra at exponential scale via tensor network dimension reduction
• Abstract summary: This paper develops and analyzes techniques for randomized dimension reduction of network data.<n>The paper includes several stylized illustrations from quantum many-body physics with ambient dimension up to $2200$.
• Score: 1.2226213907761816
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many problems in modern scientific computing are challenging because of a \emph{curse of dimension}, where their mathematical formulation involves objects whose dimension is \emph{exponential} in the nominal "size" of the problem. Tensor networks can provide a compact representation for exponentially large vectors and matrices that arise in applications, but these representations do not always lead to reliable algorithms. This paper develops and analyzes techniques for randomized dimension reduction of tensor network data. These techniques support a suite of efficient algorithms for provably solving exponential-scale linear algebra problems, including trace estimation and eigenvalue approximation. The paper includes several stylized illustrations from quantum many-body physics with ambient dimension up to $2^{200}$.

Related papers

• Tensor Cookbook: Mastering Tensors through Diagrams [7.352764365348196]
  This manuscript provides a self-contained guide to tensor networks and their use in tensor algebra.<n>TNs were originally introduced by Penrose and developed extensively in quantum physics.<n>TNs encode contractions as edges in a graph, reducing notational overhead and revealing structural properties obscured by index notation.
  arXiv  Detail & Related papers  (2026-05-15T20:21:14Z)
• Tailoring tensor network techniques to the quantics representation for highly inhomogeneous problems and few body problems [0.0]
  We show that by tailoring the tensor network algorithms to this particular case, in the spirit of the multigrid approach, we obtain faster and more robust convergence of the algorithms.<n>Our simulations involve up to $280$ grid points and would represent, we argue, a very strong challenge for conventional approaches.
  arXiv  Detail & Related papers  (2026-04-10T14:04:06Z)
• Theory on variational high-dimensional tensor networks [2.0307382542339485]
  We investigate the emergent statistical properties of random high-dimensional-network states and the trainability of tensoral networks. We prove that variational high-dimensional networks suffer from barren plateaus for global loss functions. Our results pave a way for their future theoretical studies and practical applications.
  arXiv  Detail & Related papers  (2023-03-30T15:26:30Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability. We quantify the relevant structure of the data in terms of a novel notion of mutual complexity.
  arXiv  Detail & Related papers  (2021-07-31T10:25:26Z)
• Solving PDEs on Unknown Manifolds with Machine Learning [8.220217498103315]
  This paper presents a mesh-free computational framework and machine learning theory for solving elliptic PDEs on unknown manifold. We show that the proposed NN solver can robustly generalize the PDE on new data points with errors that are almost identical to generalizations on new data points.
  arXiv  Detail & Related papers  (2021-06-12T03:55:15Z)
• Quantum Algorithms for Data Representation and Analysis [68.754953879193]
  We provide quantum procedures that speed-up the solution of eigenproblems for data representation in machine learning. The power and practical use of these subroutines is shown through new quantum algorithms, sublinear in the input matrix's size, for principal component analysis, correspondence analysis, and latent semantic analysis. Results show that the run-time parameters that do not depend on the input's size are reasonable and that the error on the computed model is small, allowing for competitive classification performances.
  arXiv  Detail & Related papers  (2021-04-19T00:41:43Z)
• Non-negative matrix and tensor factorisations with a smoothed Wasserstein loss [0.0]
  We introduce a general mathematical framework for computing non-negative factorisations of matrices and tensors with respect to an optimal transport loss. We demonstrate the applicability of this approach with several numerical examples.
  arXiv  Detail & Related papers  (2021-04-04T22:42:21Z)
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems [78.95866278697777]
  We propose two variants of the Truncated Orthogonal Iteration to compute multiple leading eigenvectors with sparsity constraints simultaneously. We then apply our algorithms to solve the sparse principle component analysis problem for a wide range of test datasets.
  arXiv  Detail & Related papers  (2021-03-24T23:11:32Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data. We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity. Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
  arXiv  Detail & Related papers  (2020-06-16T21:56:22Z)
• Eigendecomposition-Free Training of Deep Networks for Linear Least-Square Problems [107.3868459697569]
  We introduce an eigendecomposition-free approach to training a deep network. We show that our approach is much more robust than explicit differentiation of the eigendecomposition. Our method has better convergence properties and yields state-of-the-art results.
  arXiv  Detail & Related papers  (2020-04-15T04:29:34Z)
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees [106.91654068632882]
  We consider the bipartite graph and formalize its representation learning problem as a statistical estimation problem of parameters in a semiparametric exponential family distribution. We show that the proposed objective is strongly convex in a neighborhood around the ground truth, so that a gradient descent-based method achieves linear convergence rate. Our estimator is robust to any model misspecification within the exponential family, which is validated in extensive experiments.
  arXiv  Detail & Related papers  (2020-03-02T16:40:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.