Reproduce “Information-computation trade-offs in non-linear transforms” on OpenResearch

About this paper

Connor Ding, Abhiram Rao Gorle, Jiwon Jeong, Naomi Sagan, Tsachy Weissman

Researchers at Stanford University investigate information-computation trade-offs across various non-linear transforms for modern data processing tasks, including image compression, denoising, and sequential data modeling. The study demonstrates that carefully chosen non-linear methods can achieve competitive or superior performance with drastically reduced computational demands compared to state-of-the-art deep learning approaches, particularly in genomic classification and symbolic music generation.

Key insights

• INRs offer compact, resolution-flexible representations but are sensitive to aggressive pruning, whereas 2D Gaussian Splatting provides faster, parallelizable, and spatially interpretable encoding/decoding, with position parameters highly sensitive to quantization.
• The textual transform enables perceptually satisfying, ultra-low bitrate compression and universal denoising by leveraging semantic meaning and off-the-shelf generative AI, effectively overcoming the distortion-perception trade-off.
• The Lempel-Ziv (LZ78) transform, when applied to "good zero-order" SPAs, yields theoretically universal SPAs with significantly reduced computational complexity, offering a sustainable alternative to large deep learning models.

Summary by alphaXiv.