Sparse Recovery with Finite Alphabet Constraints

This direction is split into other directions: rationality constraint for lattice generation, discrete signal recovery. Its last version stays readable and citable here.

Version 1 of 124 papers42 conceptsfrozen 2026-10-04

Standard compressed sensing is built on the assumption that signals are sparse and continuous. We typically seek a vector $x$ where most entries are zero and the rest are arbitrary real numbers. However, in many real-world applications—from digital communications and DNA sequencing to text-based games—the signal is not just sparse; it is discrete.

When we know a signal's non-zero entries must come from a finite alphabet (like $\{0, 1\}$ or a set of integers), the geometry of the recovery problem changes fundamentally. Instead of searching for a point in a high-dimensional subspace, we are searching for a specific needle in a structured haystack of grid points.

The Geometry of Discrete Search Spaces

In traditional compressed sensing, we use $\ell_1$-minimization to find the sparsest solution to an underdetermined system $y = Ax$. Geometrically, this is like expanding an $\ell_1$ "diamond" until it touches the affine subspace defined by our measurements.

When the signal is discrete, such as a binary vector, the possible solutions are restricted to the vertices of a hypercube. T.S. Jayram and Vijay Arya demonstrate that by adding "box constraints"—simply enforcing that $0 \le x_i \le 1$—we can recover binary signals with far fewer measurements than the standard theory predicts. This works because the discrete points we seek often lie on the boundaries of the convex hull, effectively narrowing the search space.

Sandra Keiper and Götz E. Pfander take this further in Compressed sensing for finite-valued signals, showing that for certain alphabets, the number of measurements required for recovery is capped at a fixed fraction of the total dimension, regardless of how dense the signal becomes. The discreteness provides a "safety margin" that continuous signals lack.

Exploiting the Alphabet Prior

If we know the alphabet, we can bake that knowledge directly into our algorithms rather than treating it as a post-processing step.

  1. Discrete Message Passing: Andreas Müller and Robert J. Piechocki adapted the Approximate Message Passing (AMP) algorithm by using a prior distribution modeled as a sum of Dirac delta functions. This forces the iterative process to "gravitate" toward the known alphabet values, resulting in massive performance gains—up to 20dB better than standard AMP.
  2. Integer-Constrained Greedy Search: In Action Assembly, Chen Tessler and Shie Mannor tackle text-based games where actions are "assembled" from a dictionary. They use IK-OMP, a variation of Orthogonal Matching Pursuit that incorporates integer constraints and beam search to prevent the retrieval of fractional components, allowing agents to navigate combinatorial action spaces of millions of possibilities.
  3. Lattice-Based Recovery: Deanna Needell and Lenny Fukshansky explore the algebraic side, treating the recovery problem as a search within a lattice structure. By utilizing the Voronoi cell geometry of the lattice, they show that discrete signals are more distinguishable under noise than real-valued signals.

Closing the Statistical-Computational Gap

One of the most striking results in this area concerns the "statistical-computational gap"—the idea that some signals are theoretically recoverable but computationally impossible to find.

Arya Mazumdar and Neha Sangwan show in Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements that for binary signals, the recovery problem simplifies into a pure support identification task. Because we don't need to estimate varying magnitudes (the non-zero values are always 1), simple correlation-based algorithms can reach information-theoretic limits. This suggests that discrete constraints don't just make recovery more efficient; they can fundamentally change the complexity class of the problem.

Why It Matters

By moving away from "blind" compressed sensing and embracing the discrete nature of data, researchers are building systems that are more robust and efficient:

  • Wireless Communication: Robert J. Piechocki uses these techniques to allow multiple users to transmit on the same frequency by treating their unique channel signatures as a sparse, discrete code.
  • Tomography: Discrete Algebraic Reconstruction Techniques (DART) assume an object is made of a few known materials (discrete intensities), allowing for high-quality 3D imaging from very few X-ray projections.
  • Network Coding: Vincent Y. F. Tan and Stark C. Draper have extended these ideas to rank minimization over finite fields, optimizing how data is stored and moved across networks.

In short, when we stop pretending the world is continuous, we find that the discrete structure of our data is not a limitation, but a powerful tool for reconstruction.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sparse_recovery_with_finite_alphabet_con_4cec601e,
  title = {Sparse Recovery with Finite Alphabet Constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sparse-recovery-with-finite-alphabet-constraints/rdr_4cec601e919d4f1abf0487d8768b7aff},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_sparse_recovery_with_finite_alphabet_con_4cec601e_v1,
  title = {Sparse Recovery with Finite Alphabet Constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sparse-recovery-with-finite-alphabet-constraints/rdr_4cec601e919d4f1abf0487d8768b7aff/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}