Fast Trainable Multilinear Bases for Image Compression

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.