19.2. Quantization

Sending measurement vectors over a communication channel necessarily involves some sort of quantization. The theory of quantized compressive sensing is quite rich. In this section, we discuss some of the key ideas from the field.

The measurement quantization process can be written as

(19.5)$$\mathbf{y}=Q(\mathrm{\Phi }\mathbf{x})$$

where $Q$ is the quantizer applied to the true real valued measurements. Often, the quantization process can be modeled simple as measurement noise:

(19.6)$$\mathbf{y}=\mathrm{\Phi }\mathbf{x}+\mathbf{n}$$

where $\mathbf{n}$ is the measurement noise vector introduced to model the quantization noise. Under this model, one can simply lean on the theory of sparse recovery under the presence of noise for stable recovery if the quantization noise is energy limited. Specifically, we can assume that

$$\Vert \mathbf{n}{\Vert }_2\le ϵ$$

for some $ϵ>0$ for a given quantization model. In particular, for a uniform linear quantizer with the step size $\delta$, one has

$$ϵ\le \sqrt{\frac{M{\delta }^2}{12}}.$$

Please revisit Recovery in Presence of Measurement Noise for some basic recovery guarantees.

19.2.1. 1-Bit Compressive Sensing

Our discussion below is limited to real valued signals and sensing matrices.

In [13], the authors proposed a very aggressive quantization strategy where each measurement is reduced to a single bit. In particular, we write the measurement as

$$\mathbf{y}=\mathrm{sgn}(\mathrm{\Phi }\mathbf{x})$$

where we are computing the sign of each measurement value and transmitting this over the channel. Since the signs of the measurements drop the amplitude information, hence $\mathbf{y}$ is independent of the scale of $\mathbf{x}$. In other words, for any $\alpha >0$, we have

$$\mathrm{sgn}(\mathrm{\Phi }(\alpha \mathbf{x}))=\mathrm{sgn}(\mathrm{\Phi }\mathbf{x}).$$

Thus, we can only recover the signal $\mathbf{x}$ up to a scale factor. We resolve the issue of scale factor by insisting that the recovery algorithm should construct a unit norm signal. As a result of this restriction, our search space is limited to the unit sphere. This vastly reduces the reconstruction search space. We can easily see that in this quantization method, the quantization noise cannot be modeled as an energy limited component.

Note

In this section, we assume that the value $0$ has a positive sign. Thus, there are only two possible values of $\mathrm{sgn}(x)$ namely $+1$ and $-1$. This can be encoded as a single bit over a communication channel.

19.2.1.1. Consistent Reconstruction

The authors describe the notion of consistent reconstruction. In [42], it is shown that consistent reconstruction significantly improves the reconstruction performance in quantized frame representations.

Definition 19.3 (Consistent reconstruction)

We say that the reconstructed signal is consistent with the quantized measurements, if the reconstructed leads to the same output if it is measured and quantized with the same system.

In other words, if $\mathrm{\Delta }$ is the reconstruction algorithm and $\hat{\mathbf{x}}=\mathrm{\Delta }(\mathrm{\Phi },\mathbf{y})$ is the reconstruction of $\mathbf{x}$, we say that $\hat{\mathbf{x}}$ is a consistent reconstruction of $\mathbf{x}$ if

$$\mathbf{y}=Q(\mathrm{\Phi }\mathbf{x})=Q(\mathrm{\Phi }\hat{\mathbf{x}}).$$

Recall that each measurement before the quantization step is an inner product between a row of the sensing matrix and the signal. Thus, for consistent reconstruction in the case of 1-bit compressive sensing, we require that the inner product between each row of $\mathrm{\Phi }$ and the signals $\mathbf{x}$ and $\hat{\mathbf{x}}$ should have the same sign. In the following, we explore how the reconstruction algorithm can take advantage of the consistent reconstruction principle to speed up the reconstruction process.

Note

Recall that we introduced the rows of the sensing matrix as sensing vectors in The Sensing Matrix. In literature, often people call the rows of $\mathrm{\Phi }$ as measurement vectors also. In that case the vector $\mathbf{y}$ is called the vector of measurements. Yes, indeed it can get confusing. In our terminology, the rows of $\mathrm{\Phi }$ are called sensing vectors and $\mathbf{y}$ is called the measurement vector.

Let ${\varphi }_i$ be the $i$-th row of $\mathrm{\Phi }$. It is clear that

$$y_i\mathrm{sgn}(⟨{\varphi }_i,\mathbf{x}⟩)\ge 0.$$

In the matrix notation, we can write this as

$$\mathbf{Y}\mathrm{\Phi }\mathbf{x}⪰\mathbf{0}$$

where $\mathbf{Y}=\mathrm{diag}(\mathbf{y})$ is a diagonal matrix comprising of the sign values in $\mathbf{y}$ on its main diagonal.