Provable error bounds for randomized higher-order tensor renormalization group methods (R-HOTRG, MDTRG, Triad-MDTRG)

The randomized higher-order tensor renormalization group methods introduced by Nakayama (arXiv:2307.14191) replace the exact singular value decompositions of the higher-order tensor renormalization group (HOTRG) by randomized singular value decompositions, reducing the coarse-graining cost from $O(D^{4d-1})$ to $O(rD^{3d})$ for the randomized HOTRG (R-HOTRG), $O(r^2D^{2d+1})$ for the minimally-decomposed TRG (MDTRG), and $O(r^3D^{d+3})$ for its triad representation (Triad-MDTRG) in $d$ dimensions, where $D$ is the truncated bond dimension, $r$ the oversampling factor, and $q$ the number of power-iteration QR repetitions. Their accuracy is supported only by free-energy benchmarks on the three-dimensional Ising model at $D\le10$ with fixed $r=6$, $q=2$. The open problem is to place these randomized coarse-graining schemes on a controlled footing: derive rigorous, quantitative accuracy guarantees as functions of $D$, $r$, $q$, and the number of renormalization steps. Two closely related questions arise from the same gap: how $r$ must scale with $D$ to guarantee a target accuracy, and whether the randomized schemes preserve the accuracy of observables beyond the free energy at the same $D$.

Background

Classical lattice partition functions can be rewritten exactly as contractions of local tensors, and the tensor renormalization group (TRG) of Levin and Nave computes such contractions by iteratively coarse-graining the tensors, truncating singular values to keep a fixed bond dimension $D$ that controls both accuracy and cost. The higher-order tensor renormalization group (HOTRG) extends this to dimensions $d>2$: at each renormalization step an isometry (a matrix with orthonormal columns) is obtained from the singular value decomposition (SVD) of a unit-cell tensor $\Gamma$ (the effective tensor obtained by contracting all local tensors inside one unit cell of the coarse-grained lattice), projecting a pair of indices of range $D^2$ onto a single index of range $D$. HOTRG costs $O(D^{4d-1})$ — already $O(D^{11})$ in three dimensions — which severely limits the reachable $D$. Deterministic cost-reduced variants trade accuracy for speed by introducing additional tensor decompositions: the anisotropic TRG (ATRG) with $O(D^{2d+1})$ and the triad TRG based on a triad (three-leg) decomposition of the local tensor with $O(D^{d+3})$. The randomized singular value decomposition (R-SVD) of Halko, Martinsson, and Tropp approximates the rank-$D$ truncated SVD of a large matrix $A$ by sketching: one multiplies $A$ by a random matrix $\Omega$ of size $n\times rD$ ($r$ is the oversampling factor), orthonormalizes the result by a QR decomposition, and optionally repeats $q$ power-iteration QR rounds ($A(A^tA)^q\Omega$ with re-orthonormalization) to improve accuracy for slowly decaying spectra. For a single fixed matrix, this method provably returns an approximation nearly as accurate as the optimal truncated SVD, in expectation or with controlled failure probability.

Morita, Igarashi, Zhao, and Kawashima used R-SVD to build a two-dimensional randomized TRG with cost $O(D^5)$ and observed empirically that an oversampling of the order of $D$ reproduces full-SVD results even at the critical point of the two-dimensional Ising model, but gave no analysis. Nakayama (2023) then established the randomized method in higher dimensions: R-HOTRG with cost $O(D^{3d})$ (pre-factor $r$, i.e. $O(rD^{3d})$); MDTRG, the minimally-decomposed TRG obtained by applying R-HOTRG to the order-$(d+1)$ tensor that arises after a single decomposition, with $O(r^2D^{2d+1})$; and Triad-MDTRG, a triad representation of MDTRG, with $O(r^3D^{d+3})$ ($D^9$, $D^7$, $D^6$ in three dimensions). Two construction ideas matter: internal-line oversampling, which keeps the intermediate internal legs of the decompositions at rank $rD$ rather than $D$ (this is what makes MDTRG converge to the HOTRG result), and the isometry of the unit-cell tensor, which builds the projector from the full unit-cell network rather than a simpler local SVD. The numerics cover only the three-dimensional Ising model at criticality ($T_c=4.5115$), $D\le10$, $r=6$, $q=2$, lattice volumes up to $2^{45}$, and the free energy: the observed exponential convergence in the oversampling parameter and the claim that the systematic error originates only from the isometry truncation step (as in HOTRG) are empirical findings without any derivation. The gap is conceptual: the known R-SVD guarantees bound the error of one low-rank approximation of a fixed matrix, whereas in the renormalization iteration each step consumes the randomized output of the previous step and the final free energy aggregates exponentially many randomized contractions, so the per-step analysis does not obviously compose into a bound in terms of $D$, $r$, $q$, and the number of steps.

Problem Statement

Establish rigorous error control for the randomized higher-order tensor renormalization group algorithms R-HOTRG, MDTRG, and Triad-MDTRG of Nakayama (arXiv:2307.14191), with one overarching objective: to place randomized coarse-graining on the same controlled footing as deterministic HOTRG. The core requirement is quantitative bounds: derive explicit guarantees — deterministic, in expectation, or with stated failure probability — on the error that the randomized approximations introduce in the computed free energy (or partition function) and in the coarse-grained tensors, as functions of the truncated bond dimension $D$, the oversampling factor $r$, the number $q$ of power-iteration QR repetitions, and the number of renormalization steps. The bounds may target either the exact model or the comparison the source paper's claims require, namely the difference between the randomized schemes and deterministic HOTRG at the same $D$ (the claim that the systematic error originates only from the isometry truncation). Two closely related questions arise from the same gap left by the source paper and would naturally be informed by such bounds; they remain open directions rather than additional completion requirements: how the oversampling $r$ must scale with $D$ (and depth) to guarantee a prescribed target accuracy, and the resulting cost-accuracy trade-off given the algorithmic costs $O(rD^{3d})$, $O(r^2D^{2d+1})$, and $O(r^3D^{d+3})$; and whether the randomized schemes preserve fine-grained physical information at equal $D$ — correlation functions, critical exponents, and the convergence of the renormalization-group flow — beyond the original single free-energy benchmark. Pure performance profiling (wall-clock and parallelization engineering at very large $D$) belongs to the same follow-up agenda and is partially addressed by later work, but does not by itself resolve this problem.

References

1. Katsumasa Nakayama, 'Randomized higher-order tensor renormalization group', arXiv:2307.14191 (2023), DOI 10.48550/arXiv.2307.14191, https://arxiv.org/abs/2307.14191 (source paper)
2. Michael Levin and Cody P. Nave, 'Tensor renormalization group approach to two-dimensional classical lattice models', Physical Review Letters 99, 120601 (2007), DOI 10.1103/PhysRevLett.99.120601, https://doi.org/10.1103/PhysRevLett.99.120601
3. Z. Y. Xie, J. Chen, M. P. Qin, J. W. Zhu, L. P. Yang, and T. Xiang, 'Coarse-graining renormalization by higher-order singular value decomposition', Physical Review B 86, 045139 (2012), DOI 10.1103/PhysRevB.86.045139, https://arxiv.org/abs/1201.1144
4. Satoshi Morita, Ryo Igarashi, Hui-Hai Zhao, and Naoki Kawashima, 'Tensor renormalization group with randomized singular value decomposition', Physical Review E 97, 033310 (2018), DOI 10.1103/PhysRevE.97.033310, https://arxiv.org/abs/1712.01458
5. N. Halko, P.-G. Martinsson, and J. A. Tropp, 'Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions', SIAM Review 53(2), 217-288 (2011), DOI 10.1137/090771806, https://arxiv.org/abs/0909.4061
6. Daisuke Kadoh and Katsumasa Nakayama, 'Renormalization group on a triad network', arXiv:1912.02414 (2019), https://arxiv.org/abs/1912.02414
7. Daiki Adachi, Tsuyoshi Okubo, and Synge Todo, 'Anisotropic tensor renormalization group', Physical Review B 102, 054432 (2020), DOI 10.1103/PhysRevB.102.054432, https://arxiv.org/abs/1906.02007
8. Katsumasa Nakayama, 'Application of the projective truncation and randomized singular value decomposition to a higher dimension', Proceedings of Science PoS(LATTICE2023) 029 (2024), DOI 10.22323/1.453.0029, https://arxiv.org/abs/2401.06389
9. Yuto Sugimoto and Shoichi Sasaki, 'Applying the Triad network representation to four-dimensional ATRG method', Proceedings of Science PoS(LATTICE2024) 038 (2025), DOI 10.22323/1.466.0038, https://arxiv.org/abs/2412.14104
10. Yuto Sugimoto and Shoichi Sasaki, 'Triad representation for the anisotropic tensor renormalization group in four dimensions', Physical Review D 112, 094514 (2025), DOI 10.1103/c3qc-tn48, https://arxiv.org/abs/2507.21909
11. Jacques Bloch, Robert Lohmayer, Maximilian Meister, and Michael Nunhofer, 'Improved local truncation schemes for the higher-order tensor renormalization group method', Nuclear Physics B 987, 116107 (2023), DOI 10.1016/j.nuclphysb.2023.116107, https://arxiv.org/abs/2210.02266
12. Yuto Sugimoto, 'Forward-mode automatic differentiation for the tensor renormalization group and its relation to the impurity method', Physical Review D 113, 094502 (2026), DOI 10.1103/9wb1-rrcn, https://arxiv.org/abs/2602.08987