Compressive Sensing with Side Information

36 concepts21 papers1 proposal

Standard Compressive Sensing (CS) operates on a simple but powerful premise: a high-dimensional signal can be recovered from remarkably few linear measurements, provided the signal is sparse in some domain. However, classical CS algorithms treat every reconstruction task as an independent event. They assume complete ignorance about the signal's structure beyond its overall sparsity.

In the real world, we rarely start from scratch. Whether processing consecutive frames in a video sequence, tracking dynamic wireless channels, or conducting sequential medical imaging, we almost always possess "side information"—such as a previous reconstruction, a correlated reference signal, or historical data.

By modifying the underlying optimization geometry to incorporate this prior knowledge, a growing body of research demonstrates that we can drastically lower the required number of measurements, breaking past traditional sample complexity bounds.

Changing the Geometry of Recovery

To understand why side information helps, we must look at the geometry of sparse recovery. In standard CS, recovering a sparse vector $x$ from measurements $y = Ax$ is typically framed as an $\ell_1$-minimization problem (Basis Pursuit). Geometrically, the algorithm expands an $\ell_1$-ball (a cross-polytope) until it intersects the affine subspace defined by the measurement constraints $y = Ax$. The fewer measurements we have, the lower the dimension of this subspace, and the harder it is for the $\ell_1$-ball to hit the true sparse signal at a sharp corner.

What happens if we already suspect that certain coordinates of the signal are non-zero? Suppose we have an estimate of the signal's support (the indices of its non-zero elements), denoted as $T$.

Instead of penalizing the entire vector, Vaswani et al. (Modified-CS: modifying compressive sensing for problems with partially known support) proposed minimizing the $\ell_1$-norm of only the unknown components:

$$\min_{x} \|x_{T^c}\|_1 \quad \text{subject to} \quad y = Ax$$

By removing the penalty on the suspected support $T$, the geometry changes completely. The isotropic $\ell_1$-ball stretches into a cylinder aligned with the dimensions of $T$. Because the objective function ignores the coordinates in $T$, the optimization problem effectively shrinks to finding the remaining unknown non-zero elements.

Mota et al. (Compressed sensing with side information: Geometrical interpretation and performance bounds) formalized this using high-dimensional geometry. They analyzed an $\ell_1-\ell_1$ minimization framework that penalizes both the signal's sparsity and its difference from a reference signal. Their geometric analysis proved that this approach drastically reduces the number of random measurements needed to guarantee exact recovery, whereas more intuitive approaches (like an $\ell_1-\ell_2$ penalty) yield far smaller theoretical gains.

Why Support Outweighs Value

Intuitively, one might assume that knowing the approximate values of a signal's coefficients would be the most useful piece of prior information. However, theoretical insights reveal a surprising truth: knowing where the information lies (its support) is mathematically far more powerful than knowing the values themselves.

Hu et al. (Performance analysis of joint-sparse recovery from multiple measurement vectors with prior information via convex optimization) and Herzet et al. (Exact Recovery Conditions for Sparse Representations with Partial Support Information) evaluated how different types of prior knowledge affect recovery bounds. They demonstrated that providing accurate support information significantly relaxes the mutual coherence thresholds required of the sensing matrix $A$.

When a portion of the support is known, the matrix columns corresponding to those known indices are effectively removed from the competitive search. As long as the number of correct support guesses outweighs the incorrect ones, the mathematical conditions for perfect reconstruction become substantially easier to satisfy. The structural constraint alone does the heavy lifting, even if the values within that support are completely unknown or quantitatively imprecise.

Managing Noisy Realities and Erroneous Priors

Prior knowledge is rarely perfect. If an algorithm blindly trusts an incorrect support estimate, its performance can degrade catastrophically. To make prior-informed recovery practical, algorithms must balance their trust between the measurement data and the side information.

To handle noise and imperfect priors simultaneously, Lu et al. (Regularized Modified BPDN for Noisy Sparse Reconstruction With Partial Erroneous Support and Signal Value Knowledge) introduced regularized variants of Basis Pursuit Denoising (BPDN). Their framework adds tunable penalty weights to different coordinate sets:

$$\min_{x} \|x_{T^c}\|_1 + \gamma \|x_T - \hat{x}_T\|_1 \quad \text{subject to} \quad \|y - Ax\|_2 \le \epsilon$$

Here, $\hat{x}_T$ represents the prior value estimates on the suspected support $T$. If the prior knowledge is highly reliable, $\gamma$ can be increased; if it is highly uncertain, the algorithm relaxes its reliance on the side information. This regularization ensures that the reconstruction degrades gracefully rather than failing completely when the prior contains errors.

Scaling Up via Message Passing

For massive, real-time datasets, solving large-scale convex optimization problems can be computationally prohibitive. To achieve the same measurement efficiency at scale, researchers have integrated side information into iterative, low-complexity frameworks like Approximate Message Passing (AMP).

Standard AMP uses an iterative thresholding loop where a "denoiser" function suppresses noise at each step based on the assumed sparsity distribution. Liang (Approximate message passing-based compressed sensing reconstruction with generalized elastic net prior) and Ma et al. (An Approximate Message Passing Framework for Side Information) demonstrated that side information can be modeled as a conditional prior directly inside this denoising step.

By conditioning the denoiser on an auxiliary, statistically related signal, the effective noise floor drops faster during each iteration. This statistical coupling allows AMP to converge to the true signal with significantly fewer physical measurements than standard iterative algorithms require.

Real-World Impact

The ability to substitute prior knowledge for physical measurements has immediate implications for hardware design and data acquisition rates across several domains:

  • Wireless Communications: In dynamic networks, channels change continuously but share underlying physical paths. Qin et al. (Sparse Representation for Wireless Communications: A Compressive Sensing Approach) showed that integrating historical channel state information or geolocation data via reweighted optimization drastically reduces the pilot overhead needed for channel estimation in 5G and IoT networks.
  • Medical Imaging: Consagra et al. (Optimized Diffusion Imaging for Brain Structural Connectome Analysis) leveraged historical brain diffusion patterns to construct a statistical prior model. This prior allows high-fidelity reconstruction of brain structural connectomes using a fraction of the usual magnetic resonance sampling directions, significantly shortening scan times.
  • Extreme Quantization: In ultra-fast hardware systems, measurements are often quantized to just a single bit of information (the sign). North et al. (One-bit Compressive Sensing with partial support) demonstrated that incorporating partial support estimates can compensate for this extreme binary information loss, allowing hardware-efficient systems to achieve high-fidelity reconstruction without increasing the sampling rate.

Key Foundational Work

Modified Basis Pursuit Denoising(modified-BPDN) for noisy compressive sensing with partially known support (2010) — contributed 5 concept elements to this direction.
Modified-CS: modifying compressive sensing for problems with partially known support (2010) — contributed 4 concept elements to this direction.
Compressive sampling strategies for integrated microspectrometers (2006) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_prior_informed_signal_recovery_da5f7b6b,
  title = {prior-informed signal recovery},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/prior-informed-signal-recovery/rdr_da5f7b6b0c7b4304be59e5250e96e04c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_prior_informed_signal_recovery_da5f7b6b_v1,
  title = {prior-informed signal recovery},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/prior-informed-signal-recovery/rdr_da5f7b6b0c7b4304be59e5250e96e04c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake