Oct 2025· Numerical Linear Algebra with Applications· Vol 33· 0 citations· 102 references
Computer ScienceMathematics
TL;DR
A novel reformulation of the butterfly structure as a compact tensor network is proposed, 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.
Abstract
We address the problem of recovering highly oscillatory operators, represented as n×n$$ n\times n $$ matrices with a fixed set of observed entries. Given that these matrices can be well compressed by butterfly matrix decomposition of L=𝒪(logn) levels requiring only O(nlogn)$$ O\left(n\log n\right) $$ 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 2L+2$$ 2L+2 $$ dense tensor, and cast its butterfly decomposition as a tensor network consisting of order L+3$$ L+3 $$ 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 𝒪(nlogn) observed entries in the input matrix and demonstrate an 𝒪(nlog3n) 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.
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
BaKron is an efficient solver that combines anti-diagonal parallelism with a recursive divide-and-conquer construction that matches the cubic scaling of GPTQ while exploiting richer curvature information.
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.
Alberto Bucci, Gianfranco Verzella· Numerical Linear Algebra wit...· 3 citations
This work introduces Multivariate Polynomial Optimization based on Matrix Product Operators (MPO)$^2$, a framework that combines learned MPO feature embeddings with compact polynomial weight tensors that yields feature order independent polynomial representations that can incorporate structured operators such as projections, convolutions, and masks for weight tensor symmetries.
Niccolo' Ciolli, Anders Vestergaard Norskov, Michael J. Kastoryano et al.· 0 citations
We study recovery of a low-rank tensor $\mathcal{T}$ and a low-rank matrix $M$ from sparse, noisy observations. $\mathcal{T}$ and $M$ share one mode. We relax tensor rank using the nuclear norm of the mode-1 unfolding. This unfolding carries the coupling. It also has an exact proximal operator. We couple $\mathcal{T}$ and $M$ through a learned linear operator $G$. We prove a minimizer exists for the ridge-stabilized penalized objective. We prove that a proximal alternating linearized minimization (PALM) scheme converges to a critical point, for the algorithm as implemented, by verifying the hypotheses of a known nonconvex block-coordinate convergence theorem against our objective and identifying which conditions come from this problem's structure. For the matrix-only sub-problem, we state a proven sampling bound from matrix completion theory. For the coupled problem, we prove a sample-complexity result for a sequential sub-case: a separately-known coupling operator recovers $M$ from $\mathcal{T}$'s recovery accuracy alone, with no observations of $M$ needed. For the fully joint, alternately-estimated case, we state a conjecture and test it empirically, including a low-density regime where coupling does not help. We report multi-seed synthetic experiments with mean and standard deviation across sampling densities, an asymmetric-density experiment, and convergence curves, and we explain why recovery error stays high at low density. We apply the framework to workforce-skill and small-business-health estimation. Every application-specific choice is a proposed design, not a validated result; we have not run the framework on deployed data.