Binary Measurement Matrices for Hardware Efficient Compressed Sensing

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 113 papers20 conceptsfrozen 2026-10-04

Compressed sensing (CS) offers a compelling promise: we can capture high-resolution signals using far fewer measurements than the Nyquist rate suggests. However, the "mathematical tax" for this efficiency is often paid in hardware. Traditional CS relies on dense, random Gaussian matrices filled with floating-point numbers. For a power-constrained wearable or a high-speed radar system, performing millions of floating-point multiplications is a non-starter.

To bridge this gap, researchers have moved toward binary and structured measurement matrices. By constraining the sensing process to binary values and deterministic patterns, we can replace expensive multipliers with simple logic gates, turning a theoretical advantage into a physical one.

From Multiplications to Additions and XORs

The fundamental operation in compressed sensing is the projection $y = \Phi x$, where $\Phi$ is the measurement matrix. When $\Phi$ consists of floating-point numbers, every measurement requires a series of high-precision multiplications.

As Ayesha Siddique and colleagues demonstrate in ApproxCS: Near-Sensor Approximate Compressed Sensing for IoT-Healthcare Systems, switching to Bernoulli-based (binary) matrices transforms these operations. If the elements of $\Phi$ are restricted to $\{0, 1\}$, the matrix-vector multiplication becomes a series of simple additions. In hardware, this eliminates the need for complex floating-point units (FPUs), drastically reducing energy consumption in devices like cardiac monitors.

Taking this further, Mike Davies and Laurent Jacques explore the extreme limit in One Bit to Rule Them All : Binarizing the Reconstruction in 1-bit Compressive Sensing. By binarizing both the measurements and the sensing matrix during reconstruction, they show that signal recovery can be performed using nothing more than XOR logic gates and bit-counting. This allows sophisticated signal processing to run on the simplest possible digital logic.

Eliminating Storage with Deterministic Structures

A second hurdle for hardware is memory. Storing a large, truly random matrix requires significant on-chip storage. Researchers solve this by using deterministic constructions—matrices that aren't stored, but generated on-the-fly.

Shu-Tao Xia and Xinji Liu have developed methods to build these matrices using finite geometry and number theory. In Sparks and Deterministic Constructions of Binary Measurement Matrices from Finite Geometry, they describe matrices with cyclic or quasi-cyclic structures. These can be implemented using Linear Feedback Shift Registers (LFSRs). Instead of a massive memory bank, the hardware only needs a small circuit that "shifts" the matrix into existence as needed.

Similarly, Xinji Liu and Shutao Xia propose using sequences of shifted identity blocks in Deterministic Construction of Binary Measurement Matrices with Flexible Sizes. This allows the sensing process to be handled by simple shift registers, minimizing the silicon area required for the sensor.

Learning the Optimal Binary Mask

While binary matrices are efficient, they must still be effective at capturing information. Rather than using fixed mathematical patterns, recent work focuses on learning the best binary matrix for a specific task.

In the C2SP-Net framework, Di Wu and Ziyu Wang jointly optimize a binary sensing matrix alongside a neural network classifier. For applications like epilepsy seizure prediction, the matrix acts as a "plug-and-play" filter that selects the most informative EEG components. Because the matrix is learned, it can maintain high classification accuracy even at 1/16th compression, all while remaining hardware-friendly.

This "learned" approach also extends to optics. Hao Fu and Liheng Bian apply this to Non-imaging single-pixel sensing with optimized binary modulation. By constraining optical modulation patterns to binary values, they can use standard Digital Micromirror Devices (DMDs) to sense at rates up to 22kHz, enabling real-time computer vision without traditional image reconstruction.

Real-World Impact: Radar and Beyond

The shift toward binary logic is particularly transformative for high-bandwidth applications like autonomous driving. Madhumitha Sakthi and Marius Arvinte demonstrate in Automotive Radar Sub-Sampling via Object Detection Networks: Leveraging Prior Signal Information that Binary Permuted Diagonal (BPD) matrices can replace Gaussian operators.

These BPD matrices use simple switching logic instead of multiplications. When combined with object detection networks that identify "regions of interest," they allow radar systems to slash data requirements by 90%. This ensures that the massive data throughput of a gigapixel camera or a high-resolution radar doesn't overwhelm the vehicle's central processing unit.

By moving the complexity of compressed sensing from floating-point arithmetic into structured binary logic, these researchers have turned a mathematical curiosity into a practical toolkit for the next generation of efficient, "always-on" sensors.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_binary_measurement_matrices_for_hardware_98c38887,
  title = {Binary Measurement Matrices for Hardware Efficient Compressed Sensing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/binary-measurement-matrices-for-hardware-efficient-compressed-sensing/rdr_98c388877b0b4e21a6112862e4b78131},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-17},
}

This exact version (version 1, frozen text):

@misc{lacuna_binary_measurement_matrices_for_hardware_98c38887_v1,
  title = {Binary Measurement Matrices for Hardware Efficient Compressed Sensing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/binary-measurement-matrices-for-hardware-efficient-compressed-sensing/rdr_98c388877b0b4e21a6112862e4b78131/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-17},
}