Fast Trainable Multilinear Bases for Image Compression

1 Introduction

• Fixed bases cannot adapt across datasets, while learned autoencoders usually compress better but carry far more parameters than one image.The DCT comes close to the optimal Karhunen–Loève transform for sources near the first-order autoregressive Gaussian regime; natural photographs are near that regime, but line drawings are not.Source: §1 · pp. 1–2
• A useful adaptive sparse basis should retain negligible parameter overhead, near-linear application and inverse costs, and exact invertibility before truncation.These are the properties the paper identifies as making the DCT and FFT effective.Source: §1 · p. 2
• The paper treats topology selection, training, and dataset dependence as empirical questions because finding optimal tensor decompositions and training fixed circuits are NP-hard.The paper's roadmap assigns these topics to Sections 2–5.Source: §1 · p. 2
• The proposed bases are trainable isometric tensor networks initialized from FFT, DCT-IV, or quantum-inspired variants and optimized with Riemannian methods.One shared basis is learned per dataset and reused unchanged on held-out images.Source: §1 · p. 2
• On Quick Draw, the best trained basis stores images in roughly 20% fewer bytes than the DCT at matched quality, while on DIV2K it leads only under aggressive truncation.The Quick Draw byte comparison uses a common codec and excludes one-off basis storage.Source: §1 · p. 2

2 Problem formulation

• The problem is to find unitary image bases that satisfy the transform-coding constraints.The formulation uses a family of candidate bases rather than a separate basis for each image.Source: §2 · p. 2
• For each training sample set and retained-coefficient budget, the objective minimizes mean reconstruction error after truncation.The selected basis is shared across the dataset.Source: §2 · p. 3
• After training, the learned basis is stored once and applied to every held-out image from that dataset.The inference example in Fig. 1 shows a trained basis applied after keeping a selected fraction of coefficients.Source: §2 · p. 3, Figure 1 · p. 3

3 Isometric tensor-network bases

• Each network is an ordered contraction of small isometric gates acting on one or two binary index legs, with fixed recursion determining contraction order.Where two-leg gates remain diagonal, fusing recursion levels gives a fast-transform schedule.Source: §3 · p. 4

3.1 Construction from fast transforms

• The QFT construction relaxes FFT gates within their matrix manifolds, while the DCT-IV construction similarly relaxes its gates and retains the exact DCT-IV as initialization.Every QFT-family parameter setting remains unitary, with the inverse given by the adjoint network applied in reverse order.Source: §3.1 · p. 5

3.2 Topology variants

• TEBD, MERA, and RichBasis use the same single- and two-qubit gate families but differ in wiring; Entangled QFT adds couplings between matched row–column pairs.MERA requires a power-of-two qubit count per axis.Source: §3.2 · p. 5
• Fixed-size gates keep the parameter overhead polylogarithmic in image size across the topology family.Dense relaxed gates can prevent fusion of recursion levels, retaining the stepped application cost.Source: §3.2 · p. 5

4 Riemannian training

• Training evaluates minibatch truncation loss, updates gates on their manifolds, and selects the parameters with lowest validation loss.The keep ratio is the retained fraction of all coefficients, and 15% of the training slice is held out for validation.Source: §4 · p. 5

4.1 Truncation loss

• The truncation loss is discarded coefficient energy, so training lowers it by rotating the basis to concentrate training-image energy in retained coefficients.For a fixed basis, the k largest-magnitude coefficients retain as much energy as any other choice of k coefficients.Source: §4.1 · p. 6
• Top-k selection is piecewise constant in the parameters, making the loss smooth between coefficient-ranking crossings and yielding an exact gradient there.The authors therefore do not use smoothed surrogates for discrete selections.Source: §4.1 · p. 6

4.2 Manifold-constrained update

• Riemannian Adam projects gradients onto each gate's tangent space, then uses Cayley retraction to return updated gates to the unitary manifold.Its adaptive moments and first-moment transport are applied gate by gate.Source: §4.2 · p. 6

4.3 Initialization

• Initialization is topology-specific, and the non-convex objective means these choices do not guarantee a global optimum.QFT and DCT-IV begin at their defining fixed-transform values; other topologies use the specified QFT or seeded feasible initializations.Source: §4.3 · pp. 6–7

5 Experiments

• Both datasets use fixed 500-image training and 100-image test slices; bases train at ρ = 0.1 and are evaluated at five keep ratios, with quality measured by mean PSNR over test images.DIV2K images are grayscale, center-cropped and resampled to 256 × 256; Quick Draw bitmaps are zero-padded to 32 × 32.Source: §5 · p. 7

5.1 Topology comparison

• At DIV2K ρ = 0.01, DCT-IV reaches 21.92 dB versus RichBasis’s 14.54 dB; their top 1% coefficients retain 96% versus 84% of energy.This 1% keep ratio is a tenfold extrapolation beyond the ρ = 0.1 training budget; both bases retain over 99% in their top 10%.Source: §5.1 · pp. 7–8

5.2 Compression at matched quality

• At 35 dB, trained DCT-IV uses 37% of raw versus JPEG’s 8 × 8 block DCT’s 46% (20% fewer bytes); at 40% of raw, it reaches 36.9 dB versus 31.5 dB.Figure 4b reports both matched-quality and matched-size operating points.Source: Figure 4 · p. 8, §5.2 · p. 9

5.1 Topology comparison

• Dense-gate validation floors cluster within 6 of one another, while the diagonal pair sits roughly 45 above their mean; rewiring U(4) gates shifts DIV2K means by less than 0.9 dB above ρ = 0.01.The paper reports that gate manifold separates learned bases more than wiring does.Source: §5.1 · p. 8
• Every learned basis beats 8 × 8 DFT at every keep ratio on both datasets; on Quick Draw, dense-gate bases beat block DCT-II throughout, while DIV2K gains occur only under aggressive truncation.On Quick Draw, QFT and Entangled QFT lead the block DCT-II only at ρ = 0.01.Source: §5.1 · p. 8
• Reconstructions show dense-gate bases preserving sketch strokes blurred by the diagonal pair; on DIV2K, learned circuits generally avoid block artifacts under aggressive truncation, except RichBasis at ρ = 0.01.The examples supplement the table’s mean PSNR comparisons.Source: §5.1 · p. 8

5.2 Compression at matched quality

• The byte benchmark holds the codec fixed and excludes the one-per-dataset basis file from reported sizes; full-frame sketch strokes are offered only as a possible explanation for the savings.The comparison is between bases under a common lossy codec, not between complete codecs.Source: §5.2 · p. 9

6.1 Summary

• The proposed family contains the DFT and DCT-IV as exact points, applies in near-linear time, and adds only polylogarithmically many parameters while remaining invertible.Riemannian optimization keeps gates unitary during training.Source: §6.1 · pp. 9–10
• On Quick Draw, DCT-IV, TEBD, and RichBasis beat the block DCT at all five tested keep ratios, while on DIV2K the best learned basis leads only at the two lowest ratios.QFT and Entangled QFT lead the block DCT on Quick Draw only at ρ = 0.01.Source: §6.1 · p. 10
• The reported byte figure is at 35 dB and excludes one-off storage of its parameters.Source: §6.1 · p. 10

6.2 Outlook and limitations

• The authors propose exploring other training objectives and using trained bases for spectral analysis, Fourier neural operators, inpainting, or quantum kernel methods.The quantum-kernel use would compare states after measurement or truncation, since a unitary alone preserves their overlap.Source: §6.2 · pp. 10–11
• The training objective uses hard top-k truncation and does not account for coefficient ordering within the retained set, quantization, or entropy coding.The authors propose soft thresholding and rate–distortion losses on coded bytes as alternatives.Source: §6.2 · p. 10
• Each basis is trained offline for one dataset and has a fixed topology; comparisons with wavelets and learned dictionaries, and tests on other out-of-regime corpora, remain open.The authors name diagrams and drawn or animated video frames as untested targets.Source: §6.2 · p. 11

Funding.

• The work reports support from China’s National Key R&D Program, the National Natural Science Foundation of China, and the JST SPRING program.The listed grant numbers are 2024YFB4504004, 12404568, and JPMJSP2180, respectively.Source: Funding · p. 11

Competing interests.

• The authors report no relevant financial or non-financial interests to disclose.Source: Competing interests · p. 11

Data availability.

• DIV2K and Quick Draw are publicly available, and the trained bases and per-image evaluation records are archived on Zenodo.The data archive is version 0.1.0 of the benchmark repository.Source: Data availability · p. 11

Code availability.

• The open-source pdft implementation is archived on Zenodo as version 0.3.0, with benchmark reproduction scripts archived alongside the data.Source: Code availability · p. 11

Use of AI tools.

• Claude and Codex assisted with language editing and consistency checks; the authors independently reviewed and approved scientific decisions and final content.Source: Use of AI tools · p. 11

Figure 7 caption

• Figure 7 depicts FFT-to-QFT construction, including binary re-indexing, a Cooley–Tukey level, local phase factors, and recursive unrolling with gate relaxation.The caption says panels (a)–(c) preserve the matrix, while panel (d) normalizes and relaxes gates within their manifolds.Source: Figure 7 · p. 12

A.1 FFT decomposition

• Recursively splitting the FFT into even and odd output frequencies yields two half-size DFTs plus O(N) twiddle multiplications per level, for total cost O(N log N).Perfect-shuffle interleavers restore output order at each level and accumulate into bit reversal across the recursion.Source: §A.1 · pp. 12–13

Matrix-to-network construction.

• Reinterpreting input indices as binary tensor legs exposes the FFT factors as local gates; relaxing those gates yields a unitary network containing the normalized DFT at its Fourier point.The construction turns controlled twiddles into two-leg phase gates, and the recursion’s fixed interleavers compose into output bit reversal.Source: Matrix-to-network construction · p. 13

A.2 DCT-IV decomposition

• The DCT-IV is exposed as a radix-2 tensor network using the recursive sparse factorization of Plonka and Tasche 2005 within the algebraic Cooley–Tukey framework of P¨uschel and Moura 2008.The construction places q0 on the recursion branch and the remaining binary wires on the child index.Source: §A.2 · p. 13

Two kernel identities.

• DCT-IV recursion pairs mirrored inputs, rotates each pair, sends both branches through the same half-size child, and applies a sign correction before merging outputs.Only the shared child recurses, so no second transform template or transform-type ancilla is needed.Source: Two kernel identities · pp. 13–15

A.3 Gate counts and manifolds

• For length N = 2^n, exact QFT and DCT-IV networks each use O((log N)^2) fixed-size gates; dense U(4) and O(4) bonds in RichBasis and trained DCT-IV prevent fused-level evaluation.Source: §A.3 · p. 15

Relaxation manifolds.

• Gate-wise relaxation replaces each fixed gate with a trainable element of its corresponding manifold while preserving wiring; QFT and RichBasis contain the exact QFT, and DCT-IV contains the bit-reversed exact transform.Updates keep gates unitary to machine precision, while gates assigned to O(2) and O(4) remain real only to about 10^-3.Source: Relaxation manifolds · pp. 15–16

A.4 DCT-IV versus DCT-II

• Unlike DCT-IV’s repeated identical child, the DCT-II radix-2 identity has two different children, requiring two templates or a transform-type ancilla for that recursion.DCT-II is described as a strong JPEG coding baseline with classical fast factorizations of its own.Source: §A.4 · p. 17

B.1 Riemannian Adam update

• Riemannian Adam projects gradients onto each gate’s tangent space, uses transported first moments and elementwise second moments, then retracts updates to preserve the gate manifold.The stated settings are (β1, β2, ϵ) = (0.9, 0.999, 10^-8); first-moment transport uses re-projection rather than exact geodesic parallel transport.Source: §B.1 · p. 17
• The benchmark bases train for 112 epochs of 50-image minibatches (1008 steps), with η warmed up over the first 5% of steps to 3 × 10−3 and cosine-decayed to 3×10−4.Per-run schedule values are recorded in each released basis’s run-environment file.Source: §B.1 · p. 18

B.2 Constraint preservation

• Projection and factor-wise retraction keep each gate on its manifold, so the trained transform remains invertible without changing parameter count or contraction cost.The implementation carries O-assigned gates with a complex unitary kernel, maintaining the constraint at machine precision; their realness holds to about 10^-3 in released bases.Source: §B.2 · p. 18

B.3 Batched evaluation

• Each minibatch adds a batch leg, and the per-image loss is vectorized across that axis with gate tensors broadcast across images.The training objective is the batch mean.Source: §B.3 · p. 18
• Reverse-mode differentiation through the compiled contraction returns one accumulated ambient gradient per gate.Source: §B.3 · p. 18
• Keeping gates separate in the contraction preserves their independent manifold constraints; gates sharing a factor manifold are grouped for a stacked projection–retraction update.Source: §B.3 · p. 18

Appendix C Training robustness

• The robustness study varies gate-training order, initialization, and seed, and scores test PSNR on the original 50-image test set.The appendix includes a seed-robustness study varying both the initialization seed and the batch subsample.Source: Appendix C · p. 18
• The QFT network uses two registers that act on the rows and columns of the input image.Source: Figure 9 · p. 18
• The DIV2K runs use the QFT(8, 8) network, corresponding to the illustrated QFT(3, 3) network.Source: Figure 9 · p. 18

C.1 Gate unfreezing

• 297/300 Haar-random QFT runs beat the block DFT at ρ = 0.20, with the worst seed reaching 30.16 dB.Source: §C.1 · p. 19
• Each unfreezing stage thaws one gate and trains all unfrozen gates to a plateau; the study compares three thaw orders and identity or Haar-random initialization.Block-growth, left-to-right, and right-to-left are the three orders; in block-growth, H9 partners H1 and is among the earliest large loss drops.Source: §C.1 · p. 20
• All six gate-order and initialization combinations ended within 1.2 dB, although the two right-to-left runs trailed by ∼1 dB.Training-loss and held-out test-PSNR rankings differed because the loss used a top-10% training-batch proxy while PSNR used a 20%-keep test score.Source: §C.1 · p. 20

Appendix D Initialization noise

• The DCT-IV disturbance sweep retrains from ten on-manifold noise levels, from 0.1% to 100% of stored gate entries, and does not test larger-magnitude noise.The training uses 1010 steps on the DIV2K-8q pool and evaluates test PSNR at four keep ratios.Source: Appendix D · p. 20

On-manifold perturbation.

• The disturbance selects among 2200 stored real-valued entries, then reprojects each affected gate onto its manifold so the perturbed transform remains unitary.A gate moves if at least one of its entries is selected, so the disturbed gate fraction can exceed the selected-entry fraction.Source: On-manifold perturbation · pp. 20–21

Appendix D Initialization noise

• ∼0.2 dB: trained DCT-IV perturbation endpoints stayed within this distance of the undisturbed reference across tested keep ratios.The sweep used σjit = 0.1 and three seeds; initial PSNR fell as the disturbed fraction increased.Source: Appendix D · p. 20, Figure 11 · p. 21

• Across tested keep ratios, trained endpoints remained within ∼0.2 dB of the undisturbed exact-init endpoint despite perturbed-init PSNR losses of up to 8.6 dB.Source: Training recovers the tested… · p. 21
• The trained endpoint was insensitive to disturbance fraction f at the tested noise scale and seeds.Source: Training recovers the tested… · p. 21
• After 1010 steps, training loss at f = 100% returned to 121, near the exact-init value of 123, from an initial loss of 1080.Source: Training recovers the tested… · p. 21