# On the (Generative) Linear Sketching Problem

arXiv: https://arxiv.org/abs/2603.14474 · HTML: https://mlsanity.com/paper/2603.14474/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 118 references that are in the map.
- First posted on arXiv 15 Mar 2026.

## Builds on (most cited first, 24 of 24)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [Variational Inference with Normalizing Flows](https://mlsanity.com/paper/1505.05770/) (2015)
- [Density estimation using Real NVP](https://mlsanity.com/paper/1605.08803/) (2016)
- [Glow: Generative Flow with Invertible 1x1 Convolutions](https://mlsanity.com/paper/1807.03039/) (2018)
- [Diffusion Posterior Sampling for General Noisy Inverse Problems](https://mlsanity.com/paper/2209.14687/) (2022)
- [NICE: Non-linear Independent Components Estimation](https://mlsanity.com/paper/1410.8516/) (2014)
- [Wasserstein GAN](https://mlsanity.com/paper/1701.07875/) (2017)
- [Zero-Shot Image Restoration Using Denoising Diffusion Null-Space Model](https://mlsanity.com/paper/2212.00490/) (2022)
- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [Analyzing Inverse Problems with Invertible Neural Networks](https://mlsanity.com/paper/1808.04730/) (2018)
- [AlphaEdit: Null-Space Constrained Knowledge Editing for Language Models](https://mlsanity.com/paper/2410.02355/) (2024)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Diffusion-TS: Interpretable Diffusion for General Time Series Generation](https://mlsanity.com/paper/2403.01742/) (2024)
- [Guided Image Generation with Conditional Invertible Neural Networks](https://mlsanity.com/paper/1907.02392/) (2019)
- [Heavy hitters via cluster-preserving clustering](https://mlsanity.com/paper/1604.01357/) (2016)
- [Improved Frequency Estimation Algorithms with and without Predictions](https://mlsanity.com/paper/2312.07535/) (2023)
- [Estimating Traffic and Anomaly Maps via Network Tomography](https://mlsanity.com/paper/1407.1660/) (2014)
- [LLM-Sketch: Enhancing Network Sketches with LLM](https://mlsanity.com/paper/2502.07495/) (2025)
- [Diffusion Models Meet Network Management: Improving Traffic Matrix Analysis with Diffusion-based Approach](https://mlsanity.com/paper/2411.19493/) (2024)
- [Count-Min Sketch with Conservative Updates: Worst-Case Analysis](https://mlsanity.com/paper/2405.12034/) (2024)
- [Traffic Matrix Estimation based on Denoising Diffusion Probabilistic Model](https://mlsanity.com/paper/2410.15716/) (2024)
- [Learning-based Sketches for Frequency Estimation in Data Streams without Ground Truth](https://mlsanity.com/paper/2412.03611/) (2024)
- [Lego Sketch: A Scalable Memory-augmented Neural Network for Sketching Data Streams](https://mlsanity.com/paper/2505.19561/) (2025)

## Abstract (arXiv)

Sketch techniques have been extensively studied in recent years and are especially well-suited to data streaming scenarios, where the sketch summary is updated quickly and compactly. However, it is challenging to recover the current state from these summaries in a way that is accurate, fast, and real. In this paper, we seek a solution that reconciles this tension, aiming for near-perfect recovery with lightweight computational procedures. Focusing on linear sketching problems of the form boldsymbolPhif rightarrow f, our study proceeds in three stages. First, we dissect existing techniques and show the root cause of the sketching dilemma: an orthogonal information loss. Second, we examine how generative priors can be leveraged to bridge the information gap. Third, we propose FLORE, a novel generative sketching framework that embraces these analyses to achieve the best of all worlds. More importantly, FLORE can be trained without access to ground-truth data. Comprehensive evaluations demonstrate FLORE's ability to provide high-quality recovery, and support summary with low computing overhead, outperforming previous methods by up to 1000 times in error reduction and 100 times in processing speed compared to learning-based solutions.