Compressed Sensing

The foundational assumption of compressed sensing is that the signal of interest is sparse—meaning most of its coefficients are zero—when represented in an appropriate basis or dictionary (e.g., Fourier, Wavelet, DCT). This prior allows for recovery from far fewer measurements than the signal's length.

• Key Insight: Real-world signals like images, audio, and sensor data are often compressible; their information content is concentrated in a few non-zero coefficients.
• Example: A 1-megapixel image is sparse in the wavelet domain; its essential features can be represented with only 50,000 significant coefficients.

Compressed sensing requires that the sampling basis (how you measure) is incoherent with the sparsity basis (how the signal is represented). Incoherence ensures that each measurement captures a little bit of information about all sparse components.

• Mechanism: Random sampling matrices (e.g., Gaussian, Bernoulli) are maximally incoherent with most fixed sparsity bases.
• Benefit: This randomness spreads the signal's information across all measurements, preventing aliasing and making recovery possible from undersampled data.

Reconstructing the original signal from undersampled measurements is an ill-posed inverse problem. Compressed sensing solves it via convex optimization, seeking the sparsest signal consistent with the measurements.

• Primary Algorithm: Basis Pursuit (L1-minimization): min ||x||₁ subject to y = Ax. The L1-norm promotes sparsity.
• Alternative Methods: Greedy algorithms like Orthogonal Matching Pursuit (OMP) or iterative thresholding provide faster, approximate solutions.

The Restricted Isometry Property (RIP) is a key mathematical condition that guarantees stable signal recovery. A sensing matrix A satisfies RIP if it acts nearly like an orthonormal system when operating on sparse vectors.

• Formal Definition: Matrix A has RIP of order k if there exists a constant δₖ ∈ (0,1) such that (1-δₖ)||x||₂² ≤ ||Ax||₂² ≤ (1+δₖ)||x||₂² for all k-sparse vectors x.
• Implication: If A satisfies RIP, the L1-minimization solution will be unique and robust to noise.

In agentic memory and edge AI, compressed sensing principles reduce the storage and transmission footprint of high-dimensional data like sensor streams or neural activations.

• Memory Compression: Store sparse, random projections of agent experiences instead of full data, enabling efficient experience replay buffers.
• Edge Inference: Deploy compressed sensing layers in tiny ML models to acquire signals directly in a compressed form, saving power and bandwidth.
• Related Technique: It provides a theoretical foundation for sparse training and structured sparsity methods in neural networks.

Compressed sensing differs from traditional compression by moving complexity from the encoder to the decoder. It is related to several sibling topics in memory compression.

• vs. Dimensionality Reduction (PCA/Autoencoders): CS does not require learning a data-dependent basis; it uses random, universal measurements.
• vs. Quantization & Pruning: CS is a sensing/encoding strategy, while quantization and pruning are applied to already-acquired data or model weights.
• vs. Sparse Representations: CS is a method to acquire a sparse signal efficiently; sparse representation is the property it exploits.

A sparse representation is a data format or model state where the majority of elements are zero. This inherent structure is the foundational assumption of compressed sensing. Sparse data enables massive efficiency gains:

• Storage: Only non-zero values and their indices need to be stored.
• Computation: Algorithms can skip multiplications/additions with zero, accelerating inference.
• Examples: Pruned neural network weights, TF-IDF document vectors, and the wavelet coefficients of many natural signals are inherently sparse.

Dimensionality reduction transforms high-dimensional data into a lower-dimensional space while preserving its essential structure. Unlike compressed sensing, it typically requires the full high-dimensional signal as input. Key methods include:

• Principal Component Analysis (PCA): Finds orthogonal axes of maximum variance.
• t-SNE & UMAP: Non-linear techniques for visualization and clustering.
• Application: Used for feature extraction, data visualization, and as a precursor to other ML models to combat the curse of dimensionality.

Quantization reduces the numerical precision of a model's parameters and activations. It is a core model compression technique for deployment, especially on edge devices.

• Process: Converts 32-bit floating-point (FP32) values to lower precision formats like 16-bit (FP16), 8-bit integers (INT8), or even 4-bit (NF4).
• Impact: Can reduce model memory footprint by 4x (FP16) or 8x (INT8) with minimal accuracy loss when combined with techniques like quantization-aware training.
• Hardware Benefit: Lower precision arithmetic is faster and more energy-efficient on modern AI accelerators (GPUs, NPUs).

Pruning is a neural network compression technique that removes weights, neurons, or entire layers deemed less important to the model's output. It creates a sparse network.

• Types: Unstructured pruning removes individual weights (high sparsity, irregular). Structured pruning removes entire channels or filters (less sparsity, hardware-friendly).
• Process: Often involves training a large model, identifying low-magnitude weights, pruning them, and then fine-tuning the remaining network.
• Result: Smaller, faster models that are easier to deploy, with the sparse weight matrices being highly compressible.

Knowledge Distillation transfers knowledge from a large, accurate teacher model to a smaller, more efficient student model. The student is trained not just on data labels, but to mimic the teacher's softened probability distributions (logits) and/or internal representations.

• Objective: Achieve comparable performance with a fraction of the parameters and latency.
• Use Case: Critical for deploying capable models on resource-constrained devices (mobile phones, embedded systems).
• Relation to Compression: It's a form of functional compression, preserving the input-output mapping in a more compact architecture.

Embedding compression specifically targets the reduction of storage and retrieval cost for dense vector embeddings, which are central to agentic memory and RAG systems.

• Techniques: Includes scalar quantization (e.g., PQ - Product Quantization) of vectors, dimensionality reduction (e.g., PCA on embeddings), and binary hashing.
• Trade-off: Balances recall accuracy against memory footprint and query speed.
• Application: Enables billion-scale vector search on a single server by compressing embeddings from 768+ dimensions to just a few bytes each.