Fast Trainable Multilinear Bases for Image Compression

arXiv:2608.00053 · eess.IV, cs.CV, cs.LG, math.OC, quant-ph · Submitted 2026-07-26 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Fast Trainable Multilinear Bases for Image Compression".

Jane: The paper was written by the authors from Institute of Science Tokyo and RIKEN and The Hong Kong University of Science and Technology (Guangzhou).

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back to the arXiv radio hour, and today we are looking at a paper that made me actually sit up straight when I read the title — "Fast Trainable Multilinear Bases for Image Compression". Jane, this one's right in your wheelhouse.

Jane: It really is, Tom. And the title is doing a lot of work there. "Multilinear" means the transform is built from many small linear steps, like a chain of simple operations. "Trainable" means we can adjust those steps to fit a specific kind of image. And "fast" — well, that's the kicker, because most learned compression methods are slow.

Tom: Right, and that's the tension, isn't it? For decades we've had fixed transforms like the Discrete Cosine Transform — that's the thing inside JPEG — which are fast and simple but completely blind to what you're compressing. Then deep learning came along and said, let's learn the whole encoder, and it compresses better but it's heavy and slow.

Jane: Exactly. And this paper says, what if we keep the speed and the simplicity, but add just a tiny bit of trainability? The authors take the structure of the Fast Fourier Transform, which is this beautiful recursive algorithm, and they turn it into a network of small unitary gates — like a quantum circuit, actually.

Tom: And that's the part that got me. They're borrowing from quantum computing. The image becomes a quantum state, and the transform becomes a sequence of gates. But you don't need a quantum computer to run it — it's just math on a classical machine.

Jane: Right, and because each gate is unitary — meaning it preserves energy and is exactly invertible — the whole transform is guaranteed to be lossless before you truncate anything. That's a huge deal for compression, because you never want a transform that introduces its own errors.

Tom: So the pitch is: near-linear speed, exact invertibility, and a parameter count that's polylogarithmic in the image size. That's the trifecta that the DCT had, and they've managed to keep all three while adding trainability.

Jane: And the results are genuinely exciting. On line drawings — like the Quick Draw dataset — they get roughly twenty percent fewer bytes at the same reconstruction quality compared to JPEG's eight times eight block cosine transform. That's not a tiny gain.

Tom: Twenty percent is huge. And on natural photos, they match the DCT, which is already near-optimal for that kind of data. So they're not losing anything on the easy case, and they're winning big on the hard case.

Jane: That's the story in the title, really. Fast, trainable, multilinear, for compression. Every word is doing something.

Tom: And I want to know how they actually build these circuits and train them without breaking unitarity. That's the meat of the paper, and I bet it's clever.

Jane: It is, and we'll get there. But first, let's talk about why this matters beyond just saving a few kilobytes on sketches.

Summary: Tom: So we've got the title unpacked — "Fast Trainable Multilinear Bases for Image Compression" — and now I want to dig into what the paper actually does. Jane, walk us through the core idea.

Jane: Sure. The starting point is the Fast Fourier Transform, the Cooley–Tukey algorithm. That algorithm recursively splits a big transform into smaller ones, and the paper shows you can redraw that recursion as a tensor network — a diagram of small connected operations. Each operation is a tiny unitary matrix.

Tom: And then they just... relax the fixed operations into trainable ones?

Jane: Exactly. The fixed Hadamard gates become arbitrary two times two unitary matrices. The fixed phase shifts become diagonal unitary matrices with learnable angles. The wiring stays the same, so the speed stays the same, but now you have parameters you can tune.

Tom: And tuning them is the tricky part, because you have to stay on the manifold of unitary matrices. You can't just do gradient descent and hope.

Jane: Right, and that's where the Riemannian optimization comes in. They project the gradient onto the tangent space of the unitary manifold, then use a retraction step — a Cayley transform — to land back exactly on the manifold. So every gate stays unitary after every update.

Tom: That's mathematically clean. And the loss function is interesting too — it's not the full reconstruction error. It's the error after you keep only the top-k coefficients and zero out the rest. That's exactly what transform coding does in practice.

Jane: Yes, and because the transform is unitary, that loss is just the energy of the discarded coefficients. So training is literally trying to concentrate as much signal energy as possible into the few coefficients you keep.

Tom: And they compare six different circuit topologies — the QFT, a DCT-IV variant, a TEBD ring, a MERA hierarchy, a rich all-to-all basis, and an entangled QFT. The big finding is that the wiring matters less than the choice of local gate.

Jane: That's a really interesting result. The full four times four unitary tensors — the ones that can mix two pixels at once — consistently beat the diagonal phase gates, regardless of how you connect them. On Quick Draw, that difference is up to five point eight dB at a twenty percent keep ratio.

Tom: And the DCT-IV, which is the one that starts from the cosine transform and relaxes its gates, ends up being the strongest overall. It beats the classical eight times eight block DCT on sketches at every keep ratio.

Jane: But on natural photos, the learned bases only win under aggressive truncation — like keeping just one percent of coefficients — and then they trail off at higher ratios. That matches the theory: the DCT is already near-optimal for the autoregressive Gaussian sources that natural photos approximate.

Tom: So the method pays off exactly where the classical transform is weakest. That's the sign of a good contribution — it's not trying to beat the DCT at its own game, it's extending the playbook to new territory.

Jane: And the byte-level codec they build confirms it. At matched quality, the trained DCT-IV stores sketches in about twenty percent fewer bytes. At matched size, it gains about five point five dB in PSNR.

Tom: That's a concrete, measurable win. And I'm curious — how robust is the training? Because these unitary manifolds can be tricky to optimize.

Jane: They did extensive robustness studies — gate unfreezing orders, random seeds, perturbing the exact DCT-IV initialization. The endpoints are remarkably stable. Hundreds of runs converge to within a few tenths of a dB.

Tom: That's reassuring. So the method is not just clever in theory — it's actually reliable in practice.

Jane: And that reliability is what makes me think this could actually get deployed, not just cited.

Improvements: Tom: We're back with "Fast Trainable Multilinear Bases for Image Compression", and I want to push on something Jane just said — deployment. But first, what does the paper itself say about what's missing?

Jane: The authors are pretty honest about the limitations. The biggest one is that they train one basis per dataset, offline. It's a basis-design tool, not a deployable codec. You can't adapt it per image on the fly.

Tom: And they also flag the block structure issue. JPEG's eight times eight blocks are actually a feature — they confine quantization errors and keep the per-block budget small. This paper only does full-image transforms, which is great for global correlations but misses that local robustness.

Meng: That's the thing I'd want to fix first. If you could wrap these trained circuits in a block structure, you'd get the best of both worlds — the learned basis plus the error confinement. The paper mentions it as future work, and I think it's the obvious next step.

Jane: And there's a subtle optimization issue too. The loss function is blind to the ordering within the retained coefficients. That's why RichBasis collapses at one percent keep ratio on DIV2K — it packs energy into the top ten percent but doesn't care about the ordering within that set.

Lu: Right, and that's a classic problem in sparse coding. The top-k selection is a hard, non-smooth operation, so the gradient is only defined between crossings. The paper handles it fine with automatic differentiation, but a smooth surrogate or a rate–distortion loss evaluated on the actual coded bytes would train against the real metric.

Meng: And the training cost — they contract gates one at a time in circuit order. That's O(N log2N) per step. Fusing recursion levels would get you to O(N log N), which matters if you want to scale to video frames or higher resolutions.

Tom: So the improvements are clear: block structure, better loss functions, faster contraction. What about the bigger picture? Where does this go?

Lu: I think the exciting direction is video. The paper mentions drawn and animated video as a natural target. If you have a corpus of animation frames, you train one basis for that show, store it once, and then every frame compresses better. That's a real use case.

Meng: And it's not just animation. Think about medical imaging — X-rays, CT scans — where the statistics are very different from natural photos. You could train a basis for a specific imaging modality and get consistent gains.

Jane: And the quantum connection is fascinating. These are literally quantum circuits being used as classical transforms. The paper shows that the QFT — the quantum Fourier transform — is exactly the FFT when you contract it classically. That's a beautiful bridge between two fields.

Lu: It also opens the door to using more sophisticated quantum circuit structures. The paper only scratches the surface with TEBD, MERA, and all-to-all topologies. There are entire families of tensor networks from quantum many-body physics that could be adapted.

Tom: So the improvements aren't just incremental — they point to a whole design space that hasn't been explored.

Jane: Exactly. And the fact that the gate choice matters more than the wiring tells us where to focus. The next generation of bases should invest in richer local gates, not fancier connectivity.

Conclusion: Tom: Alright, we've spent a good chunk of time with "Fast Trainable Multilinear Bases for Image Compression", and I think it's time to wrap up. Jane, give us the one-sentence version.

Jane: It's a way to take the classical fast transforms — the FFT, the DCT — and make them trainable while keeping everything that made them useful: speed, exact invertibility, and a tiny parameter footprint.

Tom: And the results back it up. Twenty percent fewer bytes on line drawings at matched quality. Matching the DCT on natural photos. Robust training across hundreds of runs.

Meng: And the practical path is clear. It's not a full codec yet, but it's a drop-in replacement for the transform stage. That's the part that actually matters for deployment.

Lu: And the quantum connection means this is just the beginning. The tensor network family is huge, and this paper shows how to navigate it systematically.

Lalam: If I may add — the cultural impact here is that compression isn't just about saving bandwidth. It's about who gets to store and share what. Cheaper compression for sketches, diagrams, and animation means smaller creators can archive and distribute their work without expensive infrastructure. That's a real democratizing effect.

Tom: That's a beautiful way to put it, Lalam. And with that, we're going to say goodbye to this paper. It's given us a lot to think about — from quantum circuits to sketch compression to the future of video codecs.

Jane: Thanks for listening, everyone. Next up, we've got a paper on tensor network contractions that I think will blow your mind. See you then.

Tom: See you soon.

Institute of Science Tokyo · RIKEN · The Hong Kong University of Science and Technology (Guangzhou)

eess.IV, cs.CV, cs.LG, math.OC, quant-ph

Submitted: 2026-07-26

Updated: 2026-08-29

Code: https://github.com/zazabap/pdft

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 64/100

Key concepts

Multilinear
This means the transform is built from many small linear steps, resembling a chain of simple operations. The authors turn the Fast Fourier Transform recursion into a network of small unitary gates to achieve this structure.
Unitary Gates
These are the tiny matrices used in the transform, borrowed from quantum computing. They are guaranteed to preserve energy and are exactly invertible, ensuring the transform introduces no errors before truncation.
Riemannian Optimization
This mathematical technique is used to train the gates on a manifold of unitary matrices. It projects gradients onto this manifold and uses a retraction step to ensure every gate remains unitary after every update.

Terminology

Summary

Summary

This paper introduces a continuous parametric family of unitary image bases for transform coding, obtained by reading classical fast transforms as isometric tensor networks and relaxing each gate within its matrix manifold. The work is motivated by the observation that fixed transforms like the Discrete Cosine Transform (DCT) and Discrete Fourier Transform (DFT) underpin most deployed codecs because they are fast, exactly invertible, and parameter-free, but they cannot adapt to datasets that depart from the first-order autoregressive Gaussian regime where the DCT is near-optimal.

The authors establish three constraints for a useful learned sparse basis: "1. Negligible parameter overhead: the basis is described by a number of parameters that is negligible compared with the image size. 2. Fast to apply: the transform and its inverse run in linear time, up to a factor polylogarithmic in the image size. 3. Exactly invertible: the inverse map is explicit, so the transform is lossless before truncation."

The core insight comes from quantum computing: "An image with N = 2n pixels, flattened into a length-N vector, has exactly the shape of an n-qubit state vector. A quantum circuit composes unitary gates into a reversible linear map, so from the image's point of view a circuit is simply a change of basis." The authors parameterize the image basis as an isometric tensor network, which is mathematically equivalent to a quantum circuit.

The construction begins with the Cooley-Tukey FFT, which is decomposed into a quantum Fourier transform (QFT) circuit through a process of re-indexing, recursion, decomposition, and relaxation. The DCT-IV is similarly decomposed into a sparse real circuit. The paper then proposes several circuit topologies: QFT, Entangled QFT, TEBD, MERA, RichBasis, and DCT-IV. These differ in wiring and local gate manifolds. For example, QFT and Entangled QFT use U (2) and U (1)4; TEBD, MERA, and RichBasis use U (2) and U (4); DCT-IV uses O(4), O(2), and U (1)4.

The training objective is the post-truncation reconstruction loss: Lk (θ; x) = x − T (θ)† topk T (θ) x, k 2 F, where topk keeps the k largest-magnitude coefficients. The dataset-level sparse basis problem is formulated as minimizing the average of this loss over the training set. The authors note that Because T (θ) is unitary it preserves the Frobenius norm (Parseval’s relation), so moving T (θ) inside the norm rewrites the pixel-domain error as the energy of the discarded coefficients, meaning training has a single lever: rotating gates to concentrate signal energy on retained coefficients.

Training uses Riemannian optimization on the manifold of unitary matrices. The update involves projection, projG (∇L) = G skew G† ∇L with skew(A) = 21 (A − A†), and retraction via the Cayley map, G+ = I − 21 W −1 I + 21 W G with W = skew a G†. Riemannian Adam is used, applying these operations gate by gate.

Experiments are conducted on two datasets: DIV2K natural photographs (256×256) and Quick Draw line drawings (32×32), each with a 500-image training slice and 100 held-out test images. All learned bases are trained at ρ = 0.1 and evaluated at five keep ratios. The datasets sit at opposite ends of the AR(1)–Gaussian family, with DIV2K near the ρ̂AR → 1 limit where the DCT-II is asymptotically optimal, and Quick Draw well below it.

The results support three main conclusions. First, the strongest basis is the DCT-IV, which leads the learned family with the highest mean at two of five DIV2K keep ratios and four of five Quick Draw ones. Second, the local gate manifold separates the learned bases more than connectivity: "Wiring the same U (4) tensor as a ring, a hierarchy, or all-to-all moves DIV2K by at most 0.9 dB and Quick Draw by at most 0.3 dB at any ratio from 0.05 upward, whereas exchanging that tensor for the diagonal U (1)4 phase costs 2.5 dB on DIV2K and 5.8 dB on Quick Draw at ρ = 0.20. Third, source statistics decide the gain: the learned bases beat the classical references exactly where the source departs from the AR(1) regime."

Against classical references, every learned basis beats the 8 × 8 DFT at every keep ratio on both datasets. On Quick Draw, the three full-tensor bases (RichBasis, TEBD, DCT-IV) beat the 8 × 8 DCT-II at every ratio, by up to 5.6 dB. On DIV2K, the best learned basis leads only under aggressive truncation (21.92 against 14.32 at ρ = 0.01, 26.11 against 25.71 at ρ = 0.05) and trails from ρ = 0.10 upward.

The paper also reports a byte-level codec comparison. At matched quality on Quick Draw, reaching 35 dB costs the trained DCT-IV ∼377 bytes per image against the block DCT’s ∼472, 20% fewer, and the saving grows to ∼30% at lower-rate operating points. Read vertically at matched size, the trained basis gains +5.5 dB at 40% of raw, so the block DCT carries about 3.5× the mean-squared pixel error at equal storage.

Robustness studies are included. A gate-unfreezing study on QFT(8,8) with three thaw orderings and two initializations shows all converge to the same ≈ 31.7 dB endpoint. A seed robustness study with 100 Haar-random initializations per ordering shows trained endpoints sit in a narrow band: At ρ = 0.20 the per-ordering mean ± σ is 31.78 ± 0.15 (bg), 31.70 ± 0.10 (lr) and 31.28 ± 0.30 (rl), and 297/300 runs beat the 8 × 8 block DFT (30.79 dB). A parameter-disturbance sweep of the DCT-IV initialization shows that training recovers the tested perturbations, with the trained endpoint insensitive to the disturbed fraction over the entire range from 0.1% to 100% of entries jittered.

The paper concludes: "We introduced a continuous parametric family of unitary image bases, obtained by reading the classical fast transforms as isometric tensor networks and relaxing each gate within its matrix manifold. Every member is unitary by construction, applies in O(N log N) time, and carries a parameter count polylogarithmic in the image size, and the family contains the FFT and the DCT-IV as exact points." The discussion notes that connectivity is close to saturated and suggests future work on explicit block structure priors and objectives that move beyond hard top-k truncation, such as rate–distortion losses evaluated on the coded byte stream.

Improvements for AI systems

Based on this paper, I can improve AI systems in the following specific ways:

1. Adaptive Compression for Non-Photographic Data

  • Improvement: Replace fixed DCT/FFT transforms in image/video codecs with the trainable isometric tensor-network bases (QFT, DCT-IV, TEBD, MERA, RichBasis) described in the paper.

  • What the improved system can do: For line drawings, sketches, diagrams, or animated content (e.g., Quick Draw), it achieves 20–30% byte reduction at matched quality (35 dB) and up to +5.5 dB PSNR at matched bitrate, compared to JPEG's 8×8 block DCT. It does this with only a polylogarithmic parameter overhead (e.g., 64 KB for a 32×32 dataset) and near-linear O(N log N) runtime.

2. Fast, Exactly Invertible Learned Transforms

  • Improvement: Integrate the Riemannian-optimized unitary gates (using Cayley retraction and projection) into any transform-coding pipeline, ensuring the transform remains exactly invertible at every training step.

  • What the improved system can do: It provides a lossless-before-truncation transform that is guaranteed unitary, avoiding the instability or non-invertibility issues common in learned autoencoder-based codecs. This is critical for applications requiring reversible preprocessing (e.g., medical imaging, scientific data storage).

3. Dataset-Specific Basis Selection via Gate Manifold Analysis

  • Improvement: Use the paper's finding that the local gate manifold (U(4) full-tensor vs. diagonal U(1)4 phase) matters more than network wiring (ring, hierarchical, all-to-all). Automatically select the best topology per dataset by measuring the empirical lag-1 autocorrelation (as in Fig. 3).

  • What the improved system can do: For AR(1)-like sources (natural photos), it defaults to DCT-IV or RichBasis; for non-AR(1) sources (sketches), it switches to full-tensor bases, yielding up to 5.8 dB improvement at ρ=0.20 on Quick Draw. This avoids manual tuning and ensures near-optimal compression across diverse data types.

4. Robust Training with Progressive Gate Unfreezing

  • Improvement: Implement the block-growth unfreezing schedule (Section C.1) to train large tensor networks (e.g., 72 gates on 256×256 images) reliably, avoiding barren-plateau-like failures.

  • What the improved system can do: It converges to within 0.15 dB of the best endpoint across 300 random seeds and three orderings, even from Haar-random initialization, with 297/300 runs beating the 8×8 block DFT. This makes training stable and reproducible for production deployment.

5. Disturbance-Resilient Initialization Recovery

  • Improvement: Use the DCT-IV exact initialization with on-manifold perturbation robustness (Section D): even with 100% of 2200 gate entries jittered (σ=0.1), training recovers to within 0.2 dB of the undisturbed endpoint.

  • What the improved system can do: It can be safely fine-tuned from a corrupted or partially transmitted basis (e.g., after network errors), recovering full performance without re-downloading the entire parameter set. This is valuable for distributed or edge-deployed codecs.

6. Polylogarithmic-Parameter Compression for Tiny Datasets

  • Improvement: Apply the framework to small or niche datasets (e.g., 32×32 icons, UI elements, scientific plots) where deep autoencoders are impractical due to parameter overhead.

  • What the improved system can do: It stores a single shared basis (e.g., 64 KB) that compresses an entire corpus, achieving better rate-distortion than JPEG while requiring negligible storage for the transform itself. This enables efficient on-device compression for embedded systems with limited memory.

7. Rate-Distortion-Aware Training (Future Extension)

  • Improvement: Modify the loss function to include quantizer and entropy-coder effects (as suggested in Section 6.2), rather than only top-k truncation.

  • What the improved system can do: It would directly optimize the byte-level rate-distortion trade-off, potentially closing the remaining gap to end-to-end learned codecs while retaining the fast, invertible, low-parameter properties. This is a clear next step for production codecs.

Sources

Related papers