One-Bit Compressed Sensing

How much information is truly contained in a single "yes" or "no" answer? In the world of signal processing, traditional wisdom, dictated by the Nyquist-Shannon theorem, suggests we need to measure a signal at high fidelity to capture it fully. But what if we could reconstruct a rich, high-resolution image or a complex audio signal from a series of ridiculously simple, one-bit measurements? This is the revolutionary premise of one-bit compressed sensing, a framework that merges high-dimensional geometry, optimization, and information theory. It addresses the fundamental problem of acquiring complex data with extremely simple, fast, or inexpensive sensors, challenging our very notion of what it means to "measure" something. This article will guide you through this fascinating topic. First, in "Principles and Mechanisms," we will explore the core ideas, from carving up space with hyperplanes to the algorithmic magic of convex optimization that makes reconstruction possible. Then, in "Applications and Interdisciplinary Connections," we will see how these principles translate into real-world technologies and reveal a surprising and powerful unity with the field of machine learning.

Imagine you are in a completely dark room with a single, invisible object. You cannot see it or touch it directly. Your only tool is an infinitely large, perfectly flat sheet of paper. You can place this sheet anywhere in the room, oriented however you like. After you place it, a mysterious oracle tells you just one thing: whether the object is on the "left" or "right" side of the sheet. How many times must you consult the oracle to build a mental picture of the object's location?

This is the central game of one-bit compressed sensing. The "object" is an unknown signal, a vector $x$ in a high-dimensional space $\mathbb{R}^n$. The "sheet of paper" is a mathematical object called a ​​hyperplane​​, and the "left/right" information is a single bit of data—a sign. It is astonishing, and a testament to the beautiful unity of geometry and information, that from a handful of such ridiculously simple questions, we can reconstruct a rich, complex signal.

Let's make our game more precise. Each time we take a measurement, we choose a "sensing vector," let's call it $a$. This vector defines our hyperplane—the set of all points $x$ that are perpendicular to $a$, which is mathematically written as the equation $\langle a, x \rangle = 0$. The inner product $\langle a, x \rangle$ is a number that tells us how much of $x$ projects along the direction of $a$. If this number is positive, $x$ is on one side of the plane; if it's negative, it's on the other. Our one-bit measurement, $y$, is simply the sign of this inner product:

This single bit of information, $y \in \{-1, +1\}$, tells us which of the two vast, open ​​half-spaces​​ created by the hyperplane our signal $x$ resides in.

Now, suppose we take $m$ measurements. We use $m$ different sensing vectors $a_1, a_2, \dots, a_m$, and we get $m$ corresponding signs $y_1, y_2, \dots, y_m$. Each measurement slices the entire space in two and tells us which half to keep. After $m$ measurements, our signal $x$ is trapped in the intersection of $m$ half-spaces. This feasible region is a ​​convex polyhedral cone​​—a kind of high-dimensional pyramid with its tip at the origin.

This geometric picture immediately reveals a fundamental limitation. If a vector $x$ lies in this cone, then so does any positively scaled version of it, say $c x$ for any constant $c > 0$. Why? Because $\operatorname{sign}(\langle a_i, c x \rangle) = \operatorname{sign}(c \langle a_i, x \rangle) = \operatorname{sign}(\langle a_i, x \rangle)$ for any $c>0$. The sign measurements are completely blind to the signal's magnitude, or ​​scale​​. We have irretrievably lost this information. This means we can never hope to recover the exact vector $x$; we can only hope to find its ​​direction​​. Our goal is to find the ray pointing from the origin through $x$, which we can represent by the unit vector $x/\|x\|_2$.

Even with the direction-only goal, our problem is far from solved. The cone of feasible directions is still enormous. An infinite number of different vectors live inside it. How can we single out the one we are looking for? We need an "ace up our sleeve," a piece of prior knowledge about the signal itself.

This is where the magic of ​​sparsity​​ comes in. Most signals of interest in science and engineering are sparse, meaning they can be represented by just a few non-zero coefficients in the right basis. An audio signal might be a combination of only a few dominant frequencies. A photograph might have large regions of constant color, making its gradient (the change in color) sparse. A signal with dimension $n=1,000,000$ might have only $s=1,000$ significant components. This is the crucial assumption that makes the seemingly impossible task of reconstruction possible.

Our problem now becomes: find the sparsest vector that is consistent with our sign measurements. That is, find the vector with the fewest non-zero entries that lies within the cone carved out by our hyperplanes.

Searching for the sparsest vector is, in general, a computationally nightmarish task, an NP-hard problem. Trying every possible combination of non-zero entries is simply not feasible. We need a more elegant approach, and this is where the power of ​​convex optimization​​ enters the stage.

Instead of minimizing the "number of non-zero entries" (the so-called $\ell_0$-norm), we minimize its closest convex cousin: the ​​$\ell_1$-norm​​, $\|x\|_1 = \sum_{j=1}^n |x_j|$. This simple change transforms an impossible problem into one that can be solved efficiently. The $\ell_1$-norm has the wonderful geometric property of preferring solutions that lie on the corners of its diamond-like level sets, and these corners correspond to sparse vectors.

So, our recovery strategy is this:

1. ​​Fix the Scale:​​ To handle the scale ambiguity, we constrain our search to vectors of a fixed norm, typically the unit sphere ($\|x\|_2 = 1$) or the unit ball ($\|x\|_2 \le 1$).

2. ​​Enforce Consistency:​​ We require our solution $x$ to be consistent with the observed signs. To make the reconstruction more robust to noise, we often demand that it lies on the correct side of each hyperplane not just by any amount, but by a certain ​​margin​​, $\tau > 0$. This gives us a set of linear inequalities: $y_i \langle a_i, x \rangle \ge \tau$ for all measurements $i$.

3. ​​Promote Sparsity:​​ We seek the vector that satisfies these constraints while having the smallest possible $\ell_1$-norm.

Putting it all together, we arrive at a beautiful convex program. A common formulation, using a margin-based loss function like the hinge loss, looks like this:

Here, the constraint $\|u\|_1 \le \sqrt{s}$ is a sophisticated way of encoding our belief in an $s$-sparse solution. This problem can be solved efficiently, turning an intractable theoretical idea into a practical algorithm.

This leads to the million-dollar question: how many measurements $m$ are needed? Classical signal processing, governed by the Nyquist-Shannon theorem, would suggest we need at least $m=n$ measurements to reconstruct a signal of dimension $n$. If this were true for one-bit sensing, the method would be no more than a curiosity.

The revolutionary result of compressed sensing is that if the signal is $s$-sparse, the number of random measurements needed is not proportional to the dimension $n$, but to the sparsity $s$. For one-bit compressed sensing, theory shows that to recover the direction of an $s$-sparse signal with high accuracy, we need a number of measurements $m$ that scales roughly as:

where $C$ is a constant. This is a spectacular result. For a signal in a million dimensions ($n=10^6$) that is only $1000$-sparse ($s=1000$), the number of measurements needed is on the order of thousands, not a million. We can reconstruct a signal from a number of measurements proportional to its intrinsic complexity ($s$), not its ambient size ($n$). This is why one-bit compressed sensing is so powerful, enabling high-resolution imaging from very simple, cheap, and fast sensors. It is crucial, however, that the sensing vectors $a_i$ are chosen randomly and incoherently; a poor choice of measurements can lead to ambiguities where signals with completely different sparse components produce the same one-bit data.

The basic one-bit model, $y_i = \operatorname{sign}(\langle a_i, x \rangle)$, has one final, subtle symmetry. Because the sign function is odd, the model cannot distinguish the signal $x$ from its negative, $-x$, if the sensor itself has an unknown global sign flip.

To break this symmetry and recover the true oriented direction (and even the lost scale!), we can introduce a technique called ​​dithering​​. Instead of comparing $\langle a_i, x \rangle$ to zero, we compare it to a small, known, random offset $\tau_i$:

This seemingly minor change has a profound effect. The measurement function is no longer centered at the origin. It is no longer odd. The response to $x$ is now statistically different from the response to $-x$. By breaking the origin symmetry, this dithered model allows the decoder to disambiguate the global sign and, remarkably, even allows for the recovery of the signal's norm, which was fundamentally lost in the undithered model.

From a simple game of "left or right," we have journeyed through high-dimensional geometry, convex optimization, and information theory to arrive at a powerful and practical framework for signal acquisition. One-bit compressed sensing shows us that even the simplest possible measurements, when combined with a belief in simplicity (sparsity) and the power of random projections, can unlock a world of hidden information.

Having journeyed through the principles of one-bit compressed sensing, you might be left with a sense of wonder, and perhaps a little skepticism. We have seen that it is mathematically possible to reconstruct a rich, complex signal from a series of simple "yes" or "no" questions. But is this just a mathematical curiosity, a beautiful but impractical idea? Where in the real world do we find such extreme measurements, and how can these principles possibly be useful?

The answer, it turns out, is that the world is brimming with thresholds, decisions, and binary events. One-bit sensing is not an artificial constraint we impose; it is often the natural language of measurement systems. By understanding this language, we unlock a treasure trove of applications and reveal profound connections between seemingly distant fields of science and engineering.

Let us begin with one of the most striking and intuitive applications: the single-pixel camera. Imagine trying to take a picture, but instead of a multi-megapixel sensor, all you have is a single, solitary photodetector—a "single pixel." This detector can't form an image; it can only tell you the total amount of light hitting it. How could you possibly create a detailed picture from this?

The trick is to not measure the scene directly, but to measure it through a series of structured light patterns. Using a device like a digital micromirror array, we can project a sequence of patterns—say, a checkerboard-like mosaic of bright and dark squares—onto the scene. For each pattern, our single pixel records the total reflected light. Now, here is the one-bit twist: instead of recording the precise brightness value, which might be expensive or slow, we simply ask if the measurement is brighter or dimmer than a pre-defined reference level. Each measurement is just a single bit: a +1 (brighter) or a -1 (dimmer). After collecting thousands of these binary "clicks," we are left with a long string of pluses and minuses.

The reconstruction problem is now a fascinating puzzle: find an image which, when projected against our sequence of patterns, would produce the exact same sequence of binary answers. Of course, many possible images might fit this description. Which one is correct? Here, we invoke the principle of sparsity. We seek the simplest possible image—the one that is most compressible or has the fewest non-zero elements in some basis (like a wavelet basis)—that is consistent with all our one-bit measurements.

This puzzle is not solved by hand, but by mathematics. We can formulate this search as a convex optimization problem. For instance, we can look for the image with the smallest possible norm that satisfies all the sign constraints imposed by our measurements. If an image x is a solution, any positively scaled version $c x$ (for $c > 0$) is also a solution, since the signs of the measurements do not change. The optimization framework elegantly handles this ambiguity by picking a unique representative, for example, the one with the smallest Euclidean norm that satisfies the sign constraints with a certain margin, much like a support vector machine in machine learning. What emerges from solving this program is a complete, high-resolution image, conjured from nothing more than a series of binary decisions made by a single point of light.

The connection to support vector machines is no accident. In fact, it hints at a much deeper unity. The one-bit measurement equation, $y_i = \mathrm{sign}(\langle a_i, x \rangle)$, is precisely the mathematical form of a linear classifier. Here, the vector of unknown signal values, $x$, acts as the weights of the classifier, the sensing vector $a_i$ is the feature vector of a data point, and the one-bit measurement $y_i$ is its class label (+1 or -1).

This means that recovering a signal from one-bit measurements is mathematically equivalent to training a linear classifier! The task of finding a sparse signal $x$ that explains the binary measurements $y$ is the same as finding a sparse linear model that correctly classifies a set of training data.

This insight is incredibly powerful. It allows us to borrow the entire, highly developed toolkit of machine learning to solve one-bit sensing problems. Instead of enforcing the sign constraints rigidly, we can use "surrogate losses" that penalize misclassifications in a smooth, differentiable way. For example, we can use the logistic loss or the hinge loss, adding a penalty term like the $\ell_1$-norm, $\|x\|_1$, to encourage the solution to be sparse. This leads to well-known and efficient algorithms like sparse logistic regression or the LASSO. This beautiful correspondence reveals that physicists trying to build a better camera and computer scientists training a better spam filter are, in a fundamental sense, climbing the same mountain from different sides.

Life is noisy, and our measurements are rarely perfect. The harsh, discontinuous nature of the sign function seems particularly vulnerable to noise—a tiny perturbation near the zero threshold can flip the bit entirely, potentially corrupting our reconstruction. The conventional wisdom is that noise is the enemy, something to be eliminated at all costs.

But what if we could fight fire with fire? What if we could make our system more robust to unknown noise by adding a little bit of known noise ourselves? This is the wonderfully counter-intuitive idea of ​​dithering​​.

Imagine adding a small, known random number (the "dither") to each linear measurement just before it hits the one-bit quantizer. For a single measurement, this seems mad; it just adds more randomness. But averaged over many measurements, it performs a small miracle. The brutal, information-destroying cliff of the sign function is smoothed out into a gentle, continuous slope. The probability of the output bit being +1 now changes gradually as the signal strength changes, rather than jumping abruptly.

This "smoothing" makes the problem much better behaved for our algorithms. It allows us to build a probabilistic model of the measurement process and, with a certain level of confidence, translate the noise statistics into a "safety margin" in our reconstruction. Instead of demanding that a measurement $\langle a_i, x \rangle$ has the correct sign, we demand that it has the correct sign by a specific amount, an amount determined by the statistics of the noise we expect. This transforms a brittle system into a resilient one, capable of achieving stable, accurate reconstructions even in the presence of significant unknown noise. Dithering is a testament to the ingenuity of the field, showing that sometimes, the best way to handle chaos is to embrace it.

The applications of one-bit sensing are not limited to sparse signals or simple cameras. The framework is remarkably flexible and sits at the confluence of several cutting-edge research areas.

• ​​Generalized Sparsity and Structure:​​ The idea that a signal is "simple" does not have to mean it has few non-zero entries. Many signals in nature, like natural images, are not sparse in themselves, but their gradient is sparse (consisting of sharp edges). This is an example of an "analysis sparsity" model. The one-bit sensing framework can be readily adapted to handle such signals by changing the objective of our optimization problem from minimizing $\|x\|_1$ to minimizing $\|\Omega x\|_1$, where $\Omega$ is an operator (like a gradient) that makes the signal sparse.

• ​​From Bits to Bins: The World of Quantization:​​ One-bit sensing is the most extreme form of quantization. More generally, we can consider quantizing a signal into a few bits ($b=2, 4, 8$, etc.). The same principles apply, but now the "noise" introduced by quantization is smaller. We can derive precise guarantees for recovery algorithms like Orthogonal Matching Pursuit (OMP) that depend explicitly on the number of bits, gracefully connecting the one-bit world to the traditional, high-precision world.

• ​​The Algorithmic Frontier: Plug-and-Play Priors:​​ Perhaps the most exciting modern development is the fusion of model-based optimization with data-driven machine learning. Instead of enforcing sparsity with a simple $\ell_1$-norm, we can use a powerful, pre-trained neural network as a "denoiser." The reconstruction algorithm then alternates, or "plays," between two steps: a step that pushes the solution to be consistent with the one-bit data, and a step that projects the solution onto the set of "natural-looking" signals as defined by the denoiser. This "Plug-and-Play" (PnP) approach allows us to incorporate incredibly complex structural priors learned from vast datasets, pushing the boundaries of what can be recovered from minimal information. An algorithm might use a denoiser trained on millions of faces to reconstruct a face from one-bit measurements, implicitly constraining the solution to lie on the low-dimensional "manifold of faces."

For all its practical utility, the field of one-bit compressed sensing rests on a beautiful and rigorous mathematical foundation. We are not just throwing algorithms at problems and hoping for the best. We can prove, with mathematical certainty, when and why these methods work.

Theoretical analyses provide us with fundamental scaling laws. For instance, we can determine the minimum number of measurements, $m$, required for a successful reconstruction. This number depends on the signal's sparsity $k$, its ambient dimension $n$, and the noise level $\sigma$. A typical result shows that we need $m \gtrsim C(1+\sigma^2)k \log(n)$ measurements, a fantastically efficient scaling that requires only a few measurements per degree of freedom in the signal. Furthermore, we can derive explicit, deterministic bounds on the worst-case error of our reconstruction, quantifying how the final angular error depends on the signal strength, noise levels, and the quality of our measurement matrix.

This theoretical bedrock gives us the confidence to design and deploy these systems in the real world. It transforms one-bit sensing from a collection of clever tricks into a mature and predictable branch of engineering science, one that continues to find new applications and inspire new theoretical questions every day. The journey from a simple binary question leads us, in the end, to a rich and unified understanding of information, structure, and measurement.