Characteristic functions of weighted sums of independent random variables exhibit low-rank structure in the quantized tensor train (QTT) representation, also known as matrix product states (MPS), enabling up to exponential compression of their fully non-Gaussian probability distributions. Under variable independence, the global characteristic function factorizes into local terms. Its low-rank QTT structure arises from intrinsic spectral smoothness in continuous models, or from spectral energy concentration as the number of components D grows in discrete models. We demonstrate this on weighted sums of Bernoulli and lognormal random variables. In the former, despite an adversarial, incompressible small-D regime, the characteristic function undergoes a sharp bond-dimension collapse for D≳300 components, enabling polylogarithmic time and memory scaling. In the latter, the approach reaches high-resolution discretizations of N=230 frequency modes on standard hardware, far beyond the N=224 ceiling of dense implementations. These compressed representations enable efficient computation of Value at Risk (VaR) and Expected Shortfall (ES), supporting applications in quantitative finance and beyond.
Figures & tables
Figure 1: QTT diagram with n rank-3 cores, carrying free indices sk of size ℓk and mutually contracted along virtual bonds αk of dimension χk .
Figure 2: Experimental setting used for the discrete experiments. (a) Beta B(2,10) distribution used to sample the weights. (b) Spectral filters considered, including the raised cosine filter σrc (blue, q=2 ), sharpened raised cosine filter σsrc (orange, q=8 ), and exponential (Gaussian) filter σexp (green).
Figure 3: Spectral reconstruction of the binomial distribution with D=3 Bernoulli variables and 256 frequency modes, using the filters shown in Fig. 2 b. (a) Exact PMF and spectral reconstructions. (b) Reconstructed CDF. (c) Pointwise error of the CDF, showing Gibbs oscillations surrounding the jump discontinuities.
Figure 4: Error analysis for a binomial model with D=3 components. (a) Decay of the median error (50% quantile of pointwise errors), reflecting the filter-dependent spectral convergence rates in smooth regions. (b) Decay of the global L1 error and the widths of the Gibbs bands.
Figure 5: Error analysis for WPB models of increasing size D . (a) Error in the global L1 norm, largely independent of D . (b) Error in the pointwise L∞ norm, showing an exponential decay of Gibbs oscillation amplitudes due to diminishing jump heights. (c) Median error, deteriorating with increasing D as the measure of the smooth region shrinks.
Figure 6: Performance comparison between spectral and Monte Carlo methods for the reconstruction of the WPB CDF (in L1 norm) and computation of 99% VaR and ES. Exact reference solutions are obtained via recursive convolution (see Appendix A.2 ). A convergence triangle is shown, illustrating the expected quadratic advantage of spectral methods.
Figure 7: Compressibility of the QTT characteristic function for discrete models. (a) Binomial model with n=20 cores, determined by the 2-adic valuation v2(D) . (b) WPB model averaged over 10 random instances, showing near-maximal rank growth at small D . (c) WPB model, showing a sharp bond-dimension collapse with increasing D and entering a compressible low-rank regime for D≳300 .
Figure 8: Compressibility of the WPB characteristic function ( 38 ) with n=18 and D=300 . (a) Heat map showing the maximum bond dimension at each virtual index sk after incorporating each variable Xd . (b) Slice of the previous heat map at s7 averaged over 10 independent random instances, showing an initial filter-dependent exponential barrier followed by strong compression.
Figure 9: Performance comparison between QTT and dense-vector spectral methods for the computation of the filtered characteristic function. Top row (fixed D=3000 , varying n ): (a) peak and truncated bond dimensions, well below the maximal 2n/2 exponential value; (b) memory usage in bytes; (c) wall-clock time. Bottom row [(d)-(f)] show the same metrics at fixed n=16 while varying D .
Figure 10: Performance comparison between QTT and dense-vector spectral methods for the computation of the CDF, VaR, and ES. (a) Wall-clock time required to reach a prescribed L1 tolerance for Monte Carlo, dense (black) and QTT (green) spectral methods. (b) Wall-clock time required to compute VaR and ES given a CDF in dense-vector or QTT format. (c) Maximum pointwise deviation ( L∞ ) between the dense-vector and QTT representations of the model’s CDF.
Figure 11: Spectral reconstruction of a single lognormal density in Eq. ( 45 ) with μ=0 , σ=1 , and tail tolerance δ=10−8 ( b≈273 ). (a) Density function, reconstructed using dense-vector and QTT spectral methods. (b) Reconstruction error for both representations.
Figure 12: Performance comparison between QTT and dense-vector spectral methods for the computation of a single lognormal density function. (a) L1 reconstruction error for several distinct variances shown in the legend. (b) Wall-clock time for increasing resolutions n=log2N . (c) Memory usage (in bytes).
Figure 13: Performance comparison between QTT and dense-vectors for the evaluation of a weighted sum of D=100 lognormal variables. The results are averaged across 10 random instances. (a) Self-error for the density fn (absolute L2 norm) and CDF Fn (relative) for increasing resolutions. Dense and QTT results match exactly, so the dense curves are omitted for clarity. The vertical dashed line indicates the largest dense resolution achieved ( n=24 ). (b) Wall-clock time versus CDF self-error, comparing dense (black, dashed) and QTT (blue, solid) implementations. (c) Maximum bond dimension of the QTT CDF, saturating at n≈20 and indicating strong compressibility.
We introduce the tubal tensor train (TTT) decomposition, a tensor-network model that combines the t-product algebra of the tensor singular value decomposition (T-SVD) with the low-order core structure of the tensor train (TT) format. For an order-(N+1) tensor with a distinguished tube mode, the proposed representation consists of two third-order boundary cores and N−2 fourth-order interior cores linked through the t-product. As a result, for bounded tubal ranks, the storage scales linearly with the number of modes, in contrast to direct high-order extensions of T-SVD. We present two computational strategies: a sequential fixed-rank construction, called TTT-SVD, and a Fourier-slice alternating scheme based on the alternating two-cores update (ATCU). We also state a TT-SVD-type error bound for TTT-SVD and illustrate the practical performance of the proposed model on image compression, video compression, tensor completion, and hyperspectral imaging.
Lab of Machine Learning and Knowledge Representation, Innopolis University, Innopolis, Russia · Innopolis University, Innopolis, Russia · Skolkovo Institute of Science and Technology, Center for Artificial Intelligence Technology, Moscow, Russia +1
TensorSketch by~\cite{pham2013fast,kar2012random} provides efficient sketching algorithms for high-dimensional polynomial kernels x⊗p∈Rdp. \cite{kar2012random} uses dense Johnson-Lindenstrauss (JL)-type projections with computational cost O(pDd), where D denotes the sketch dimension, whereas~\cite{pham2013fast} extends the sparse CountSketch\citep{count_sketch} algorithm, yielding a faster algorithm for high-dimensional sparse inputs with running time O(p(\nnzx+DlogD)). However, the variance of both estimators grows exponentially with the polynomial degree p, scaling as 3p/D. Recent work by\cite{pmlr-v206-wacker23a} showed that using complex-valued distribution reduces this dependence to 2p/D for the approach of~\cite{kar2012random}. However, their method relies on dense JL-type projections with computational cost O(pDd) and does not extend to the algorithm of~\cite{pham2013fast}. In this work, we introduce a simple variant of TensorSketch\citep{pham2013fast} that achieves the same variance bound as\cite{pmlr-v206-wacker23a}, while retaining its advantage of the input-sparsity running time. We validate our results with supporting experiments on synthetic and real-world datasets.
Amit Sharma, Mohammad Azhar Khan, Rameshwar Pratap +1
Department of Computer Science and Engineering, IIT Hyderabad, India · Department of Mathematics and Statistics, Bucknell University, USA
The key-value (KV) cache of autoregressive transformers can be viewed as a fourth-order tensor spanning attention heads, tokens, features, and grouped layers. We measure the singular-value spectra of all four mode unfoldings on Mistral-7B-v0.3 and LLaMA-2-13B and compare four standard tensor decompositions: Tucker, CP, tensor train, and t-SVD, at matched storage. The spectra partition the four axes into two classes. The token and feature modes carry low-rank structure, particularly for keys. The head and layer modes are nearly full-rank and resist compression at any practical error level. Among the four decompositions, Tucker achieves the lowest reconstruction error at every compression ratio from 2× to 5×, because it can leave the full-rank modes untouched. Comparisons with two-dimensional unfolding baselines show that the preferred representation differs between keys and values: 2D methods achieve lower key error, while four-way Tucker achieves lower value error at matched storage. A mode-pinning theorem certifies the full-rank preservation from the measured spectra alone. Two further spectral properties affect the compressible modes without touching the full-rank ones: values reach a higher error floor than keys at every ratio, and post-RoPE keys lose 41% - 64% of their pre-RoPE compressibility on both models.
Rahul Krishnan, Volker Schulz
Universität Trier · Fachbereich IV, Mathematik, Universität Trier