Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1810.10065 · Journal of Statistical Mechanics Theory and Experiment

Statistical mechanics of low-rank tensor decomposition*

Jonathan Kadmon, Surya Ganguli

Published Dec 1, 2019• 14 citations
arXivHTMLPDF

Abstract

Abstract Often, large, high-dimensional datasets collected across multiple modalities can be organized as a higher-order tensor. Low-rank tensor decomposition then arises as a powerful and widely used tool to discover simple low-dimensional structures underlying such data. However, we currently lack a theoretical understanding of the algorithmic behavior of low-rank tensor decompositions. We derive Bayesian approximate message passing (AMP) algorithms for recovering arbitrarily shaped low-rank tensors buried within noise, and we employ dynamic mean field theory to precisely characterize their performance. Our theory reveals the existence of phase transitions between easy, hard and impossible inference regimes, and displays an excellent match with simulations. Moreover it reveals several qualitative surprises compared to the behavior of symmetric, cubic tensor decomposition. Finally, we compare our AMP algorithm to the most commonly used algorithm, alternating least squares (ALS), and demonstrate that AMP significantly outperforms ALS in the presence of noise.

DOI
10.1088/1742-5468/ab3216

Related papers

The Tensor-Train Format and Its Applications

Patrick Gelß

The simulation and analysis of high-dimensional problems is often infeasible due to the curse of dimensionality. In this thesis, we investigate the potential of tensor decompositions for mitigating this curse when considering systems from several application areas. Using tensor-based solvers, we directly compute numerical solutions of master equations associated with Markov processes on extremely large state spaces. Furthermore, we exploit the tensor-train format to approximate eigenvalues and corresponding eigentensors of linear tensor operators. In order to analyze the dominant dynamics of high- dimensional stochastic processes, we propose several decomposition techniques for highly diverse problems. These include tensor representations for operators based on nearest-neighbor interactions, construction of pseudoinverses for tensor-based reformulations of dimensionality reduction methods, and the approximation of transfer operators of dynamical systems. The results show that the tensor-train format enables us to compute low-rank approximations for various numerical problems as well as to reduce the memory consumption and the computational costs compared to classical approaches significantly. We demonstrate that tensor decompositions are a powerful tool for solving high-dimensional problems from various application areas.

•Jan 1, 2017•5 citations

Counting tensor rank decompositions

Dennis Obster, Naoki Sasakura

The tensor rank decomposition is a useful tool for the geometric interpretation of the tensors in the canonical tensor model (CTM) of quantum gravity. In order to understand the stability of this interpretation, it is important to be able to estimate how many tensor rank decompositions can approximate a given tensor. More precisely, finding an approximate symmetric tensor rank decomposition of a symmetric tensor $Q$ with an error allowance $Δ$ is to find vectors $ϕ^i$ satisfying $\|Q-\sum_{i=1}^R ϕ^i\otimes ϕ^i\cdots \otimes ϕ^i\|^2 \leq Δ$. The volume of all possible such $ϕ^i$ is an interesting quantity which measures the amount of possible decompositions for a tensor $Q$ within an allowance. While it would be difficult to evaluate this quantity for each $Q$, we find an explicit formula for a similar quantity by integrating over all $Q$ of unit norm. The expression as a function of $Δ$ is given by the product of a hypergeometric function and a power function. We also extend the formula to generic decompositions of non-symmetric tensors. The derivation depends on the existence (convergence) of the partition function of a matrix model which appeared in the context of the CTM.

arXiv:2107.10237•Jul 20, 2021•0 citations

Tensor Networks for Dimensionality Reduction and Large-scale Optimization: Part 1 Low-Rank Tensor Decompositions

Andrzej S Cichocki, Namgil Lee, Ivan Valer'evich Oseledets +3 more

Machine learning and data mining algorithms are becoming increasingly important in analyzing large volume, multi-relational and multi--modal datasets, which are often conveniently represented as multiway arrays or tensors. It is therefore timely and valuable for the multidisciplinary research community to review tensor decompositions and tensor networks as emerging tools for large-scale data analysis and data mining. We provide the mathematical and graphical representations and interpretation of tensor networks, with the main focus on the Tucker and Tensor Train (TT) decompositions and their extensions or generalizations. Keywords: Tensor networks, Function-related tensors, CP decomposition, Tucker models, tensor train (TT) decompositions, matrix product states (MPS), matrix product operators (MPO), basic tensor operations, multiway component analysis, multilinear blind source separation, tensor completion, linear/multilinear dimensionality reduction, large-scale optimization problems, symmetric eigenvalue decomposition (EVD), PCA/SVD, huge systems of linear equations, pseudo-inverse of very large matrices, Lasso and Canonical Correlation Analysis (CCA) (This is Part 1)

arXiv:1609.00893•Foundations and Trends® in Machine Learning•Jan 1, 2016•456 citations

Randomized density matrix renormalization group algorithm for low-rank tensor train decomposition

Huilin Jiang, Zhongming Chen, Gaohang Yu

Tensor train decomposition is a powerful tool for processing high-dimensional data. Density matrix renormalization group (DMRG) is an alternating scheme for low-rank tensor train decomposition of large tensors. However, it may suffer from the curse of dimensionality due to the large scale of subproblems. In this paper, we proposed a novel randomized proximal DMRG algorithm for low-rank tensor train decomposition by using TensorSketch to alleviate the curse of dimensionality. Numerical experiments on synthetic and real-world data also demonstrate the effectiveness and efficiency of the proposed algorithm.

Statistics Optimization & Information Computing•May 14, 2024•1 citation

Approximate Message Passing for Quantum State Tomography

Noah Siekierski, Kausthubh Chandramouli, Christian Kümmerle +2 more

Quantum state tomography (QST) is an indispensable tool for characterizing many-body quantum systems. However, due to the exponential scaling of the cost of the protocol with system size, many approaches have been developed for quantum states with specific structure, such as low-rank states. In this paper, we show how approximate message passing (AMP), an algorithmic framework for sparse signal recovery, can be used to perform low-rank QST. AMP provides asymptotically optimal performance guarantees for large sparse recovery problems, which suggests its utility for QST. We discuss the design challenges that come with applying AMP to QST, and show that by properly designing the AMP algorithm, we can reduce the reconstruction error by over an order of magnitude compared to existing approaches to low-rank QST. We also performed tomographic experiments on IBM Kingston and considered the effect of device noise on the reliability of the predicted fidelity of state preparation. Our work advances the state of low-rank QST and may be applicable to other quantum tomography protocols.

quant-pharXiv:2511.12857•Nov 18, 2025•0 citations

Approximate Tensor Ring Decomposition

Ziang Chen, Ying‐Zhou Li, Jianfeng Lu

In this work, we study the tensor ring decomposition and its associated numerical algorithms. We establish a sharp transition of algorithmic difficulty of the optimization problem as the bond dimension increases: On one hand, we show the existence of spurious local minima for the optimization landscape even when the tensor ring format is much over-parameterized, i.e., with bond dimension much larger than that of the true target tensor. On the other hand, when the bond dimension is further increased, we establish one-loop convergence for alternating least square algorithm for tensor ring decomposition. The theoretical results are complemented by numerical experiments for both local minimum and one-loop convergence for the alternating least square algorithm.

arXiv:1905.07101•May 17, 2019•0 citations
Abstract Often, large, high-dimensional datasets collected across multiple modalities can be organized as a higher-order tensor. Low-rank tensor decomposition then arises as a powerful and widely used tool to discover simple low-dimensional structures underlying such data. However, we currently lack a theoretical understanding of the algorithmic behavior of low-rank tensor decompositions. We derive Bayesian approximate message passing (AMP) algorithms for recovering arbitrarily shaped low-rank tensors buried within noise, and we employ dynamic mean field theory to precisely characterize their performance. Our theory reveals the existence of phase transitions between easy, hard and impossible inference regimes, and displays an excellent match with simulations. Moreover it reveals several qualitative surprises compared to the behavior of symmetric, cubic tensor decomposition. Finally, we compare our AMP algorithm to the most commonly used algorithm, alternating least squares (ALS), and demonstrate that AMP significantly outperforms ALS in the presence of noise.
The simulation and analysis of high-dimensional problems is often infeasible due to the curse of dimensionality. In this thesis, we investigate the potential of tensor decompositions for mitigating this curse when considering systems from several application areas. Using tensor-based solvers, we directly compute numerical solutions of master equations associated with Markov processes on extremely large state spaces. Furthermore, we exploit the tensor-train format to approximate eigenvalues and corresponding eigentensors of linear tensor operators. In order to analyze the dominant dynamics of high- dimensional stochastic processes, we propose several decomposition techniques for highly diverse problems. These include tensor representations for operators based on nearest-neighbor interactions, construction of pseudoinverses for tensor-based reformulations of dimensionality reduction methods, and the approximation of transfer operators of dynamical systems. The results show that the tensor-train format enables us to compute low-rank approximations for various numerical problems as well as to reduce the memory consumption and the computational costs compared to classical approaches significantly. We demonstrate that tensor decompositions are a powerful tool for solving high-dimensional problems from various application areas.
The tensor rank decomposition is a useful tool for the geometric interpretation of the tensors in the canonical tensor model (CTM) of quantum gravity. In order to understand the stability of this interpretation, it is important to be able to estimate how many tensor rank decompositions can approximate a given tensor. More precisely, finding an approximate symmetric tensor rank decomposition of a symmetric tensor QQQ with an error allowance ΔΔΔ is to find vectors ϕiϕ^iϕi satisfying ∥Q−∑i=1Rϕi⊗ϕi⋯⊗ϕi∥2≤Δ\|Q-\sum_{i=1}^R ϕ^i\otimes ϕ^i\cdots \otimes ϕ^i\|^2 \leq Δ∥Q−∑i=1R​ϕi⊗ϕi⋯⊗ϕi∥2≤Δ. The volume of all possible such ϕiϕ^iϕi is an interesting quantity which measures the amount of possible decompositions for a tensor QQQ within an allowance. While it would be difficult to evaluate this quantity for each QQQ, we find an explicit formula for a similar quantity by integrating over all QQQ of unit norm. The expression as a function of ΔΔΔ is given by the product of a hypergeometric function and a power function. We also extend the formula to generic decompositions of non-symmetric tensors. The derivation depends on the existence (convergence) of the partition function of a matrix model which appeared in the context of the CTM.
Machine learning and data mining algorithms are becoming increasingly important in analyzing large volume, multi-relational and multi--modal datasets, which are often conveniently represented as multiway arrays or tensors. It is therefore timely and valuable for the multidisciplinary research community to review tensor decompositions and tensor networks as emerging tools for large-scale data analysis and data mining. We provide the mathematical and graphical representations and interpretation of tensor networks, with the main focus on the Tucker and Tensor Train (TT) decompositions and their extensions or generalizations. Keywords: Tensor networks, Function-related tensors, CP decomposition, Tucker models, tensor train (TT) decompositions, matrix product states (MPS), matrix product operators (MPO), basic tensor operations, multiway component analysis, multilinear blind source separation, tensor completion, linear/multilinear dimensionality reduction, large-scale optimization problems, symmetric eigenvalue decomposition (EVD), PCA/SVD, huge systems of linear equations, pseudo-inverse of very large matrices, Lasso and Canonical Correlation Analysis (CCA) (This is Part 1)
Tensor train decomposition is a powerful tool for processing high-dimensional data. Density matrix renormalization group (DMRG) is an alternating scheme for low-rank tensor train decomposition of large tensors. However, it may suffer from the curse of dimensionality due to the large scale of subproblems. In this paper, we proposed a novel randomized proximal DMRG algorithm for low-rank tensor train decomposition by using TensorSketch to alleviate the curse of dimensionality. Numerical experiments on synthetic and real-world data also demonstrate the effectiveness and efficiency of the proposed algorithm.
Quantum state tomography (QST) is an indispensable tool for characterizing many-body quantum systems. However, due to the exponential scaling of the cost of the protocol with system size, many approaches have been developed for quantum states with specific structure, such as low-rank states. In this paper, we show how approximate message passing (AMP), an algorithmic framework for sparse signal recovery, can be used to perform low-rank QST. AMP provides asymptotically optimal performance guarantees for large sparse recovery problems, which suggests its utility for QST. We discuss the design challenges that come with applying AMP to QST, and show that by properly designing the AMP algorithm, we can reduce the reconstruction error by over an order of magnitude compared to existing approaches to low-rank QST. We also performed tomographic experiments on IBM Kingston and considered the effect of device noise on the reliability of the predicted fidelity of state preparation. Our work advances the state of low-rank QST and may be applicable to other quantum tomography protocols.
In this work, we study the tensor ring decomposition and its associated numerical algorithms. We establish a sharp transition of algorithmic difficulty of the optimization problem as the bond dimension increases: On one hand, we show the existence of spurious local minima for the optimization landscape even when the tensor ring format is much over-parameterized, i.e., with bond dimension much larger than that of the true target tensor. On the other hand, when the bond dimension is further increased, we establish one-loop convergence for alternating least square algorithm for tensor ring decomposition. The theoretical results are complemented by numerical experiments for both local minimum and one-loop convergence for the alternating least square algorithm.