Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors

Introduction

for all $\bm{x}\in\mathcal{X}$ and $\bm{s}\in\mathcal{S}$. The RIP requires that (2) hold for all $\bm{x},\bm{s}\in\Sigma_{K}$; that is, it is a stable embedding of sparse vectors. A key result in the CS literature is that, if the coefficients of $\Phi$ are randomly drawn from a sub-Gaussian distribution, then $\Phi$ will satisfy the RIP with high probability as long as $M\geq C_{\delta}K\log(N/K)$, for some constant $C_{\delta}$ . Several hardware inspired designs with only a few randomized components have also been shown to satisfy this property .

In practice, CS measurements must be quantized, i.e., each measurement is mapped from a real value (over a potentially infinite range) to a discrete value over some finite range. For example, in uniform quantization, a measurement is mapped to one of $2^{B}$ distinct values, where $B$ denotes the number of bits per measurement. Quantization is an irreversible process that introduces error in the measurements. One way to account for quantization error is to treat it as bounded noise and employ robust reconstruction algorithms. Alternatively, we might try to reduce the error by choosing the most efficient quantizer for the distribution of the measurements. Several reconstruction techniques that specifically address CS quantization have also been proposed .

While quantization error is a minor inconvenience, fine quantization invokes a more burdensome, yet often overlooked source of adversity: in hardware systems, it is the primary bottleneck limiting sample rates . In other words, the analog-to-digital converter (ADC) is beholden to the quantizer. First, quantization significantly limits the maximum speed of the ADC, forcing an exponential decrease in sampling rate as the number of bits is increased linearly . Second, the quantizer is the primary power consumer in an ADC. Thus, more bits per measurement directly translates to slower sampling rates and increased ADC costs. Third, fine quantization is more susceptible to non-linear distortion in the ADC electronics, requiring explicit treatment in the reconstruction . As we have seen, the CS framework provides one mechanism to alleviate the quantization bottleneck by reducing the ADC sampling rate. Is it possible to extend the CS framework to mitigate this problem directly in the quantization domain by reducing the number of bits per measurement (bit-depth) instead?

In this paper we concretely answer this question in the affirmative. We consider an extreme quantization; just one bit per CS measurement, representing its sign. The quantizer is thus reduced to a simple comparator that tests for values above or below zero, enabling extremely simple, efficient, and fast quantization. A $1$-bit quantizer is also more robust to a number of commonly encountered non-linear distortions in the input electronics, as long as they preserve the signs of the measurements.

It is not obvious that the signs of the CS measurements retain enough information for signal reconstruction; for example, it is immediately clear that the scale (absolute amplitude) of the signal is lost. Nonetheless, there is strong empirical evidence that signal reconstruction is possible . In this paper we develop strong theoretical reconstruction and robustness guarantees, in the same spirit as classical guarantees provided in CS by the RIP.

sparse, i.e., satisfies $\|\bm{x}^{*}\|_{0}\leq K=\|\bm{x}\|_{0}$,

consistent, i.e., satisfies $A(\bm{x}^{*})=\bar{\bm{y}}=A(\bm{x})$.

With (RCS) from CS as a guide, one candidate program for reconstruction that respects these two conditions is

Although the parameter $K$ is not explicit in (R1BCS), the solution will be $K^{\prime}$-sparse with $K^{\prime}\leq K$ because $\bm{x}$ is a feasible point of the constraints.

The primary contribution of this paper is a rigorous analysis of the $1$-bit CS framework. Specifically, we examine how the reconstruction error behaves as we increase the number of measurement bits $M$ given the signal dimension $N$ and sparsity $K$. We provide two flavors of results. First, we determine a lower bound on reconstruction performance from all possible mappings $A$ with the reconstruction decoder $\Delta^{\rm 1bit}$, i.e., the best achievable performance of this $1$-bit CS framework. We further demonstrate that if the elements of $\Phi$ are drawn randomly from Gaussian distribution or its rows are drawn uniformly from the unit sphere, then the worst-case reconstruction error using $\Delta^{\rm 1bit}$ will decay at a rate almost optimal with the number of measurements, up to a log factor in the oversampling rate $M/K$ and the signal dimension $N$. Second, we provide conditions on $A$ that enable us to characterize the reconstruction performance even when some of the measurement signs have changed (e.g., due to noise in the measurements). In other words, we derive the conditions under which robust reconstruction from $1$-bit measurements can be achieved. We do so by demonstrating that $A$ is a stable embedding of sparse signals, similar to the RIP. We apply these stable embedding results to the cases where we have noisy measurements and signals that are not strictly sparse. Our guarantees demonstrate that the $1$-bit CS framework is on sound footing and provide a first step toward analysis of the relaxed $1$-bit techniques used in practice.

To develop robust reconstruction guarantees, we propose a new tool, the binary $\epsilon$-stable embedding (B$\epsilon$SE), to characterize $1$-bit CS systems. The B$\epsilon$SE implies that the normalized angle between any sparse vectors in $S^{N-1}$ is close to the normalized Hamming distance between their $1$-bit measurements. We demonstrate that the same class of random $A$ as above exhibit this property when $M\geq C_{\epsilon}K\log N$ (where $C_{\epsilon}$ is some constant). Thus remarkably, there exist $A$ such that the B$\epsilon$SE holds when both the number of measurements $M$ is smaller than the dimension of the signal $N$ and the measurement bit-depth is at minimum.

As a complement to our theoretical analysis, we introduce a new $1$-bit CS reconstruction algorithm, Binary Iterative Hard Thresholding (BIHT). Via simulations, we demonstrate that BIHT yields a significant improvement in both reconstruction error as well as consistency, as compared with previous algorithms. To gain intuition about the behavior of BIHT, we explore the way that this algorithm enforces consistency and compare and contrast it with previous approaches. Perhaps more important than the algorithm itself is the discovery that the BIHT consistency formulation provides a significantly better feasible solution in noiseless settings, as compared with previous algorithms. Finally, we provide a brief explanation regarding why this new formulation achieves better solutions, and its connection with results in the machine learning literature.

Since the first appearance of this work, Plan and Vershynin have developed additional theoretical results and bounds on the performance of 1-bit CS, as well as two convex algorithms with theoretical guarantees . The results in generalize the B$\epsilon$SE guarantees for more general classes of signals, including compressible signals in addition to simply sparse ones. However, the guarantees provided in that work exhibit worse decay rates in the error performance and the tightness of the B$\epsilon$SE property. Furthermore, the results of are intimately tied to reconstruction algorithms, in contrast to our analysis. We point out similarities and differences with our results when appropriate in the subsequent development.

In addition to benchmarking the performance of BIHT, our simulations demonstrate that many of the theoretical predictions that arise from our analysis (such as the error rate as a function of the number of measurements or the error rate as a function of measurement Hamming distance), are actually exhibited in practice. This suggests that our theoretical analysis is accurately explaining the true behavior of the framework.

The remainder of this paper is organized as follows. In Section 2, we develop performance results for $1$-bit CS in the noiseless setting. Specifically we develop a lower bound on reconstruction performance as well as provide the guarantee that Gaussian matrices enable this performance. In Section 3 we introduce the notion of a B$\epsilon$SE for the mapping $A$ and demonstrate that Gaussian matrices facilitate this property. We also expand reconstruction guarantees for measurements with Gaussian noise (prior to quantization) and non-sparse signals. To make use of these results in practice, in Section 4 we present the BIHT algorithm for practical $1$-bit reconstruction. In Section 5 we provide simulations of BIHT to verify our claims. In Section 6 we conclude with a discussion about implications and future extensions. To facilitate the flow of the paper and clear descriptions of the results, most of our proofs are provided in the appendices.

Noiseless Reconstruction Performance

In this section, we seek to provide guarantees on the reconstruction error from $1$-bit CS measurements. Before analyzing this performance from a specific mapping $A$ with the consistent sparse reconstruction decoder $\Delta^{\rm 1bit}(\bar{\bm{y}},\Phi,K)$, it is instructive to determine the best achievable performance from measurements acquired using any mapping. Thus, in this section we seek a lower bound on the reconstruction error.

We develop the lower bound on the reconstruction error based on how well the quantizer exploits the available measurement bits. A distinction we make in this section is that of measurement bits, which is the number of bits acquired by the measurement system, versus information bits, which represent the true amount of information carried in the measurement bits. Our analysis follows similar ideas to that in , adapted to sign measurements.

While there are generally $2^{M}$ orthants in the measurement space, the space formed by measuring all sparse signals occupies a small subset of the available orthants. We determine the number of available orthants that can be intersected by the measurements in the following lemma:

The set of signals of interest to be encoded is the set of unit-norm $K$-sparse signals $\Sigma^{*}_{K}$. Since unit-norm signals of a $K$-dimensional subspace form a $K$-dimensional unit sphere in that subspace, $\Sigma^{*}_{K}$ is a union of $\binom{N}{K}$ such unit spheres. The $Q:=2^{K}\binom{N}{K}\binom{M}{K}$ available quantization points partition $\Sigma^{*}_{K}$ into $Q$ smaller sets, each of which contains all the signals that quantize to the same point.

To develop the lower bound on the reconstruction error we examine how $\Sigma^{*}_{K}$ can be optimally partitioned with respect to the worst-case error, given the number of quantization points used. The measurement and reconstruction process maps each signal in $\Sigma^{*}_{K}$ to a finite set of quantized signals $\mathcal{Q}\subset\Sigma^{*}_{K},|\mathcal{Q}|=Q$. At best this map ensures that the worst case reconstruction error is minimized, i.e.,

Thus, when $M$ is high compared to $K^{3/2}$, the worst-case error cannot decay at a rate faster than $\Omega(1/M)$ as a function of the number measurements, no matter what reconstruction algorithm is used.

This result assumes noiseless acquisition and provides no guarantees of robustness and noise resiliency. This is in line with existing results on scalar quantization in oversampled representations and CS that state that the distortion due to scalar quantization of noiseless measurements cannot decrease faster than the inverse of the measurement rate .

To improve the rate vs. distortion trade-off, alternative quantization methods must be used, such as Sigma-Delta ($\Sigma\Delta$) quantization or non-monotonic scalar quantization . Specifically, $\Sigma\Delta$ approaches to CS can achieve error decay rate of $O((K/M)^{p-1/2})$, where $p$ is the order of the quantizer . However, $\Sigma\Delta$ quantization requires feedback during the quantization process, which is not necessary in scalar quantization. Furthermore, the result in only holds for multibit quantizers, not 1-bit ones. While efficient 1-bit $\Sigma\Delta$ quantization has been shown for classical sampling , to the best of our knowledge, similar results are not currently known for 1-bit $\Sigma\Delta$ in CS applications. Alternatively, non-monotonic scalar quantization can achieve error decay exponential in the number of measurements $M$, even in CS applications . However, such a scheme requires a significantly more complex scalar quantizer and reconstruction approach .

Theorem 1 bounds the best possible performance of a consistent reconstruction over all possible mappings $A$. However, not all mappings $A$ will behave as the lower bound suggests. In the next section we identify two classes of matrices such that the mapping $A$ admits an upper bound on the reconstruction error from a general decoder $\Delta^{\rm 1bit}$ that decays almost optimally.

2 Achievable performance via random projections

then for all $\bm{x},\bm{s}\in\Sigma^{*}_{K}$ we have that

Theorem 2 is a uniform reconstruction result, meaning that with high probability all vectors $\bm{x},\bm{s}\in\Sigma^{*}_{K}$ can be reconstructed as opposed to a non-uniform result where each vector could be reconstructed with high probability.

As derived in Appendix G, Theorem 2 demonstrates that if we use Gaussian matrices in the mapping $A$, then, given a fixed probability level $\eta$, the reconstruction decoder $\Delta^{\rm 1bit}(\bar{\bm{y}},\Phi,K)$ will recover signals with error order

which decays almost optimally compared to the lower bound given in Theorem 1 up to a log factor in $MN/K$. Whether the gap can be closed, with tighter lower or upper bounds is still an open question. Notice that the hidden proportionality factor in this last relation depends linearly on $\log 1/\eta$ which is assumed fixed.

3 Related Work

We can also view the binary measurements as a hash or a sketch of the signal. With this interpretation of the result we guarantee with high probability that no sparse vectors with Euclidean distance greater than $\epsilon_{o}$ will “hash” to the same binary measurements. In fact, similar results play a key role in locality sensitive hashing (LSH), a technique that aims to efficiently perform approximate nearest neighbors searches from quantized projections . Most LSH results examine the performance on point-clouds of a discrete number of signals instead of the infinite subspaces that we explore in this paper. Furthermore, the primary goal of the LSH is to preserve the structure of the nearest neighbors with high probability. Instead, in this paper we are concerned with the ability to reconstruct the signal from the hash, as well as the robustness of this reconstruction to measurement noise and signal model mismatch. To enable these properties, we require a property of the mapping $A$ that preserves the structure (geometry) of the entire signal set. Thus, in the next section we seek an embedding property of $A$ that preserves geometry for the set of sparse signals and thus ensures robust reconstruction.

Acquisition and Reconstruction Robustness

The Hamming distance is the natural distance for counting the number of unequal bits between two measurement vectors. Specifically, for $\bar{\bm{a}},\bar{\bm{b}}\in\mathcal{B}^{M}$ we define the normalized Hamming distance as

where $\bar{a}\oplus\bar{b}$ is the XOR operation between $\bar{a},\bar{b}\in\mathcal{B}$ such that $\bar{a}\oplus\bar{b}$ equals 0 if $\bar{a}=\bar{b}$ and 1 otherwise. The distance is normalized such that $d_{H}\in$. In the signal space we only consider unit-norm vectors, thus, a natural distance is the angle formed by any two of these vectors. Specifically, for $\bm{x},\bm{s}\in S^{N-1}$, we consider

Using these distance metrics we define the binary stable embedding.

for all $\bm{x},\bm{s}\in S^{N-1}$ with $|\,{\rm supp}\,(\bm{x})\cup{\rm supp}\,(\bm{s})\,|\leq K$.

Our definition describes a specific quasi-isometry between the two metric spaces $(S^{N-1},d_{S})$ and $(\mathcal{B}^{M},d_{H})$, restricted to sparse vectors. While this mirrors the form of the $\delta$-stable embedding for sparse vectors, one important difference is that the sensitivity term $\epsilon$ is additive, rather than multiplicative, and thus the B$\epsilon$SE is not bi-Lipschitz. This is a necessary side-effect of the loss of information due to quantization.

Any B$\epsilon$SE $A(\cdot)$ of order $2K$ enables robustness guarantees on any reconstruction algorithm extracting a unit sparse signal estimate $\bm{x}^{*}$ of $\bm{x}\in\Sigma^{*}_{K}$. In this case, the angular error is immediately bounded by

Thus, if an algorithm returns a unit norm sparse solution with measurements that are not consistent (i.e., $d_{H}(A(\bm{x}),A(\bm{x}^{*}))>0$), as is the case with several algorithms , then the worst-case angular reconstruction error is close to Hamming distance between the estimate’s measurements’ signs and the original measurements’ signs. Section 5 verifies this behavior with simulation results. Furthermore, in Section 3.3 we use the B$\epsilon$SE property to guarantee that if measurements are corrupted by noise or if signals are not exactly sparse, then the reconstruction error is bounded.

Note that, in the best case, for a B$\epsilon$SE $A(\cdot)$, the angular error of any sparse and consistent $\Delta^{\rm 1bit}(\bar{\bm{y}},\Phi,K)$ decoder is bounded by $\epsilon$ since then d_{H}\big{(}A(\bm{x}),A(\bm{x}^{*})\big{)}=0. As we have seen earlier this is to be expected because, unlike conventional noiseless CS, quantization fundamentally introduces uncertainty and exact recovery cannot be guaranteed. This is an obvious consequence of the mapping of the infinite set $\Sigma_{K}^{*}$ to a discrete set of quantized values.

We next identify a class of matrices $\Phi$ for which $A$ is a B$\epsilon$SE.

2 Binary ϵitalic-ϵ\epsilon-stable embeddings via random projections

As is the case for conventional CS systems with RIP, designing a $\Phi$ for $1$-bit CS such that $A$ has the B$\epsilon$SE property is possibly a computationally intractable task (and no such algorithm is yet known). Fortunately, an overwhelming number of “good” matrices do exist. Specifically we again focus our analysis on Gaussian matrices $\Phi\sim\mathcal{N}^{M\times N}(0,1)$ as in as in Section 2.2. As motivation that this choice of $\Phi$ will indeed enable robustness, we begin with a classical concentration of measure result for binary measurements from a Gaussian matrix.

where the probability is with respect to the generation of $\Phi$.

In words, Lemma 2 implies that the Hamming distance between two binary measurement vectors $A(\bm{x}),A(\bm{s})$ tends to the angle between the signals $\bm{x}$ and $\bm{s}$ as the number of measurements $M$ increases. In this fact is used in the context of randomized rounding for max-cut problems; however, this property has also been used in similar contexts as ours with regards to preservation of inner products from binary measurements .

The expression (8) indeed looks similar to the definition of the B$\epsilon$SE, however, it only holds for a fixed pair of arbitrary (not necessarily sparse) signals, chosen prior to drawing $\Phi$. Our goal is to extend (8) to cover the entire set of sparse signals. Indeed, concentration results similar to Lemma 2, although expressed in terms of norms, have been used to demonstrate the RIP . These techniques usually demonstrate that the cardinality of the space of all sparse signals is sufficiently small, such that the concentration result can be applied to demonstrate that distances are preserved with relatively few measurements.

Unfortunately, due to the non-linearity of $A$ we cannot immediately apply Lemma 2 using the same procedure as in . To briefly summarize, proceeds by covering the set of all $K$-sparse signals $\Sigma_{K}$ with a finite set of points (with covering radius $\delta>0$). A concentration inequality is then applied to this set of points. Since any sparse signal lies in a $\delta$-neighborhood of at least one such point, the concentration property can be extended from the finite set to $\Sigma_{K}$ by bounding the distance between the measurements of the points within the $\delta$-neighborhood. Such an approach cannot be used to extend (8) to $\Sigma_{K}$, because the severe discontinuity of our mapping does not permit us to characterize the measurements $A(\bm{x}+\bm{s})$ using $A(\bm{x})$ and $A(\bm{s})$ and obtain a bound on the distance between measurements of signals in a $\delta$-neighborhood.

To resolve this issue, we extend Lemma 2 to include all points within Euclidean balls around the vectors $\bm{x}$ and $\bm{s}$ inside the (sub) sphere $\Sigma^{*}(T):=\{\bm{u}\in S^{N-1}:{\rm supp}\,\bm{u}\subset T\}$ for some fixed support set $T\subset[N]:=\{1,\,\cdots,N\}$ of size $|T|=D$. Define the $\delta$-ball $B_{\delta}(\bm{x}):=\{\bm{a}\in S^{N-1}:\|\bm{x}-\bm{a}\|_{2}<\delta\}$ to be the ball of Euclidean distance $\delta$ around $\bm{x}$, and let $B_{\delta}^{*}(\bm{x}):=B_{\delta}(\bm{x})\cap\Sigma^{*}(T)$.

In words, if the width $\delta$ is sufficiently small, then the Hamming distance between the $1$-bit measurements $A(\bm{u})$, $A(\bm{v})$ of any points $\bm{u}$, $\bm{v}$ within the balls $B_{\delta}^{*}(\bm{x})$, $B_{\delta}^{*}(\bm{s})$, respectively, will be close to the angle between the centers of the balls.

Lemma 3 is key for providing a similar argument to that in . We now simply need to count the number of pairs of $K$-sparse signals that are euclidean distance $\delta$ apart. The Lemma can then be invoked to demonstrate that the angles between all of these pairs will be approximately preserved by our mapping. We note that the covering argument in the proof of Theorem 2 also employs $\delta$-balls in similar fashion but only considers the probability that $d_{H}=0$, rather than the concentration inequality. Thus, with Lemma 3 under our belt, we demonstrate in Appendix E the following result.

then with probability exceeding $1-\eta$, the mapping $A$ is a B$\epsilon$SE of order $K$ for sparse vectors.

By choosing $\Phi\sim\mathcal{N}^{M\times N}(0,1)$ with $M=O(K\log N)$, with high probability we ensure that the mapping $A$ is a B$\epsilon$SE. Additionally, using (9) with a fixed $\eta$ and the development in Appendix G, we find that the error decreases as

Unfortunately, this decay rate is slower, roughly by a factor of $\sqrt{K/M}$, than the lower bound in Section 2.1. This error rate results from an application of the Chernoff-Hoeffding inequality in the proof of Theorem 3. An open question is whether it is possible to obtain a tighter bound (with optimal error rate) for this robustness property.

We have now established a random construction providing robust B$\epsilon$SEs with high probability: $1$-bit quantized Gaussian projections. We now make use of this robustness by considering an example where the measurements are corrupted by Gaussian noise.

3 Noisy measurements and compressible signals

In practice, hardware systems may be inaccurate when taking measurements; this is often modeled by additive noise. The mapping $A$ is robust to noise in an unusual way. After quantization, the measurements can only take the values $-1$ or $1$. Thus, we can analyze the reconstruction performance from corrupted measurements by considering how many measurements flip their signs. For example, we analyze the specific case of Gaussian noise on the measurements prior to quantization, i.e.,

where $e(\sigma,\|\bm{x}\|_{2}):={\textstyle\frac{1}{2}}\frac{\sigma}{\sqrt{\|\bm{x}\|_{2}^{2}+\sigma^{2}}}\leq{\textstyle\frac{1}{2}}\tfrac{\sigma}{\|\bm{x}\|_{2}}$.

If $\bm{x}_{n}^{*}$ is the estimate from a sparse consistent reconstruction decoder $\Delta^{\rm 1bit}(A_{n}(\bm{x}),\Phi,K)$ from the measurements $A_{n}(\bm{x})$ with $\Phi\sim\mathcal{N}^{M\times N}(0,1)$ and if $M$ satisfies (9), then it immediately follows from Lemma 4 and Theorem 3 that

with a probability higher than $1-e^{-2M\gamma^{2}}-\eta$. Given alternative noise distributions, e.g., Poisson noise, a similar analysis can be carried out to determine the likely number of sign flips and thus provide a bound on the error due to noise.

In similar fashion to (11), if $M$ satisfies (9), this result and Theorem 3 imply that, given $\bm{x}\in S^{N-1}$ (not necessarily sparse) and for $\Phi\sim\mathcal{N}^{M\times N}(0,1)$ the angular reconstruction error of $\bm{x}^{*}=\Delta^{\rm 1bit}(A(\bm{x}),\Phi,K)$ is such that $d_{S}(\bm{x}^{*},\bm{x}_{K})\leq d_{H}(A(\bm{x}^{*}),A(\bm{x}_{K}))+\epsilon=d_{H}(A(\bm{x}),A(\bm{x}_{K}))+\epsilon\leq\ d_{S}(\bm{x},\bm{x}_{K})+\gamma+\epsilon$, with probability higher than $1-e^{-2M\gamma^{2}}-\eta$. Therefore, from the triangular inequality on $d_{S}$, this provides the bound

with the same probability. Much like conventional CS results, the reconstruction error depends on the magnitude of the best $K$-term approximation error of the signal, here expressed angularly by $d_{S}(\bm{x},\bm{x}_{K})$.

Thus far we have demonstrated a lower bound on the reconstruction error from $1$-bit measurements (Theorem 2) and introduced a condition on the mapping $A$ that enables stable reconstruction in noiseless, noisy, and compressible settings (Definition 1). We have furthermore demonstrated that a large class of random matrices—specifically matrices with coefficients drawn from a Gaussian distribution and matrices with rows drawn uniformly from the unit sphere—provide good mappings (Theorem 3).

Using these results we can characterize the error performance of any algorithm that reconstructs a $K$-sparse signal. If the reconstructed signal quantizes to the same quantization point as the original data, then the error is characterized by Theorem 2. If the algorithm terminates unable to reconstruct a signal consistent with the quantized data, then Theorem 3 describes how far the solution is from the original signal. Since (R1BCS) is a combinatorially complex problem, in the next section we describe a new greedy reconstruction algorithm that attempts to find a solution as consistent with the measurements as possible, while guaranteeing this solution is $K$-sparse.

BIHT: A Simple First-Order Reconstruction Algorithm

We now introduce a simple algorithm for the reconstruction of sparse signals from $1$-bit compressive measurements. Our algorithm, Binary Iterative Hard Thresholding (BIHT), is a simple modification of IHT, the real-valued algorithm from which is takes its name . Demonstrating theoretical convergence guarantees for BIHT is a subject of future work (and thus not shown in this paper), however the algorithm is of significant value since it i) has a simple and intuitive formulation and ii) outperforms previous algorithms empirically, demonstrated in Section 5. We further note that the IHT algorithm has recently been extended to handle measurement non-linearities ; however, these results do not apply to quantized measurements since quantization does not satisfy the requirements in .

The BIHT algorithm simply modifies the first step of IHT to instead minimize a consistency-enforcing objective. Specifically, given an initial estimate $\bm{x}^{0}=\bm{0}$ and $1$-bit measurements $\bar{\bm{y}}$, at iteration $l$ BIHT computes

where $A$ is defined as in (3), $\tau$ is a scalar that controls gradient descent step-size, and the function $\eta_{K}(\bm{v})$ computes the best $K$-term approximation of $\bm{v}$ by thresholding. Once the algorithm has terminated (either consistency is achieved or a maximum number of iterations have been reached), we then normalize the final estimate to project it onto the unit sphere. Section 4.2 discusses several variations of this algorithm, each with different properties.

The key to understanding BIHT lies in the formulation of the objective. The following Lemma shows that the term \Phi^{T}\big{(}\bar{\bm{y}}-A(\bm{x}^{l})\big{)} in (13) is in fact the negative subgradient of a convex objective $\mathcal{J}$. Let $[\cdot]_{-}$ denote the negative function, i.e., $([\bm{u}]_{-})_{i}=[u_{i}]_{-}$ with $[u_{i}]_{-}=u_{i}$ if $u_{i}<0$ and 0 else, and $\bm{u}\odot\bm{v}$ denote the Hadamard product, i.e., $(\bm{u}\odot\bm{v})_{i}=u_{i}v_{i}$ for two vectors $\bm{u}$ and $\bm{v}$.

Thus, BIHT aims to decrease $\mathcal{J}$ at each step (13).

We first note that $\mathcal{J}$ is convex. We can write $\mathcal{J}(\bm{x})=\sum_{i}\mathcal{J}_{i}(\bm{x})$ with each convex function $\mathcal{J}_{i}$ given by

where $\bm{\varphi}_{i}$ denotes a row of $\Phi$ and $A_{i}(\bm{x})={\rm sign}\,\langle\bm{\varphi}_{i},\bm{x}\rangle$. Moreover, if $\langle\bm{\varphi}_{i},\bm{x}\rangle\neq 0$, then the gradient of $\mathcal{J}_{i}$ is

while if $\langle\bm{\varphi}_{i},\bm{x}\rangle=0$, then the gradient is replaced by the subdifferential set

Thus, by summing over $i$ we conclude that \frac{1}{2}\,\Phi^{T}\big{(}A(\bm{x})-\bar{\bm{y}}\big{)}\in\bm{\nabla}J(\bm{x};\bar{\bm{y}},\Phi). $\Box$

Consequently, the BIHT algorithm can be thought of as trying to solve the problem:

that, when satisfied, implies consistency.

2 BIHT shifts

Several modifications can be made to the BIHT algorithm that may improve certain performance aspects, such as consistency, reconstruction error, or convergence speed. While a comprehensive comparison is beyond the scope of this paper, we believe that such variations exhibit interesting and useful properties that should be mentioned.

If we choose to impose the projection, $\Phi$ must be appropriately normalized or, equivalently, the step size of the gradient descent must be carefully chosen. Otherwise, the algorithm will not converge. Empirically, we have found that for a Gaussian matrix, an appropriate scaling is $1/(\sqrt{M}\|\Phi\|_{2})$, where the $1/\|\Phi\|_{2}$ controls the amplification of the estimate from $\Phi^{T}$ in the gradient descent step (13) and the $1/\sqrt{M}$ ensures that $\|\bar{\bm{y}}-A(\bm{x}^{l})\|_{2}\leq 2$. Similar gradient step scaling requirements have been imposed in the conventional IHT algorithm and other sparse recovery algorithms as well (e.g., ).

where $\Theta=(\bar{\bm{y}}\odot\Phi)$ scales the rows of $\Phi$ by the signs of $\bar{\bm{y}}$. Again, the step size must be chosen appropriately, this time as $C_{\kappa}/\|\Phi\|_{2}$, where $C_{\kappa}$ is a parameter that depends on $\kappa$.

Experiments

In this section we explore the performance of the BIHT algorithm and compare it to the performance of previous $1$-bit CS algorithms. To make the comparison as straightforward as possible, we reproduced the experiments of with the BIHT algorithm.

The experimental setup is as follows. For each data point, we draw a length-$N$, $K$-sparse signal with the non-zero entries drawn uniformly at random on the unit sphere, and we draw a new $M\times N$ matrix $\Phi$ with each entry $\phi_{ij}\sim\mathcal{N}(0,1)$. We then compute the binary measurements $\bar{\bm{y}}$ according to (3). Reconstruction of $\bm{x}^{*}$ is performed from $\bar{\bm{y}}$ with three algorithms: matching sign pursuit (MSP) , restricted-step shrinkage (RSS) , and BIHT (this paper); the algorithms will be depicted by dashed, dotted, and triangle lines, respectively. Each reconstruction in this setup is repeated for 1000 trials and with a fixed $N=1000$ and $K=10$ unless otherwise noted. Furthermore, we perform the trials for $M/N$ within the range $$. Note that when$M/N>1$, we are acquiring more measurements than the ambient dimension of the signal. While the$M/N>1$regime is not interesting in conventional CS, it may be very practical in$1$-bit systems that can acquire sign measurements at extremely high, super-Nyquist rates.

We begin by comparing the performance of the algorithms. While we can observe that the angular error of each algorithm follows the same trend, BIHT obtains smaller error (or higher SNR) than the others, significantly so when $M/N$ is greater than $0.35$. The discrepancy in performance could be due to difference in the algorithms themselves, or perhaps, differences in their formulations for enforcing consistency. This is explored later in this section.

We can infer an interesting performance trend from Figures 3(b) and (c), where the B$\epsilon$SE property may hold. Since the RSS and MSP algorithms often do not return a consistent solution, we can visualize the relationship between angular error and hamming error. Specifically, on average the angular reconstruction error is a linear function of hamming error, $\epsilon_{H}=d_{H}(A(\bm{x}),A(\bm{x}^{*}))$, as similarly expressed by the reconstruction error bound provided by B$\epsilon$SE. Furthermore, if we let $\epsilon_{1000}$ be the largest angular error (with consistent measurements) over $1000$ trials, then we can suggest an empirical upper bound for BIHT of $\epsilon_{1000}+\epsilon_{H}$. This upper bound is denoted by the dashed line in Figures 3(b) and (c).

Thus, the results of this simulation suggest that the one-sided term plays a significant role in the quality of the solution obtained.

Performance with a fixed bit-budget. In some applications we are interested in reducing the total number of bits acquired due to storage or communication costs. Thus, given a fixed total number of bits, an interesting question is how well $1$-bit CS performs in comparison to conventional CS quantization schemes and algorithms. For the sake of brevity, we give a simple comparison here between the $1$-bit techniques and uniform quantization with Basis Pursuit DeNoising (BPDN) reconstruction. While BPDN is not the optimal reconstruction technique for quantized measurements, it (and its variants such as the LASSO ) is considered a benchmark technique for reconstruction from measurements with noise and furthermore, is widely used in practice.

The results of this experiment are depicted in Figure 6. We see a common trend in each line: lackluster performance until “sufficient” measurements are acquired, then a slow but steady increase in performance as additional measurement are added, until a performance plateau is reached. Thus, since lower bit-depth implies that a larger number of measurements will be used, $1$-bit CS reaches the performance plateau earlier than in the multi-bit case (indeed, the transition point is achieved at a higher number of total bits as the bit-depth is increased). This enables significantly improved performance when the rate is severely constrained and higher bit-rates per measurements would significantly reduce the number of available measurements. For higher bit-rates, as expected from the analysis in , using fewer measurements with refined quantization achieves better performance.

It is also important to note that, regardless of trend, the BIHT algorithm performs strictly better than BPDN with $4$ bits per measurement and uniform quantization for the parameters tested here. This gain is consistent with similar gains observed in . A more thorough comparison of additional CS quantization techniques with $1$-bit CS is a subject for future study.

Comparison to quantized Nyquist samples. In our final experiment, we compare the performance of the $1$-bit CS technique to the performance of a conventional uniform quantizer applied to uniform Nyquist-rate samples. Specifically, in each trial we draw a new Nyquist-sampled signal in the same way as in our previous experiments and with fixed $N=2000$ and $K=20$; however, now the signals are sparse in the discrete cosine transform (DCT) domain. We consider four reconstruction experiments. First, we quantize the Nyquist-rate signal with a bit-depth of $\beta$ bits per time-domain sample (and optimal quantizer scale) and perform linear reconstruction (i.e., we just use the quantized samples as sample values). Second, we apply BPDN to the quantized Nyquist-rate samples with optimal choice of noise parameter, thus denoising the signal using a sparsity model. Third, we draw a new Gaussian matrix with $M=N$, quantize the measurements to $\beta$ bits, again at optimal quantizer scale, and reconstruct using BPDN. Fourth, we draw a new Gaussian matrix with $M=\beta N$ and compute measurements, quantize to one bit per measurement by maintaining their sign, and perform reconstruction with BIHT. Note that the same total number of bits is used in each experiment.

Figure 7 depicts the average SNR obtained by performing $100$ of the above trials. The linear, BPDN, Gaussian measurements with BPDN, and BIHT reconstructions are depicted by solid, dashed, dash-circled, and dash-dotted lines, respectively. The linear reconstruction has a slope of $6.02$dB/bit-depth, exhibiting a well-known trade-off for conventional uniform quantization. The BPDN reconstruction (without projections) follows the same trend, but obtains an SNR that is at least $10$dB higher than the linear reconstruction. This is because BPDN imposes the sparse signal model to denoise the signal. We see about the same performance with the Gaussian projections at $M=N$, although it performs slightly worse than without projections since the Gaussian measurements require a slightly larger quantizer range. Similarly to the results in Fig. 6, in low Nyquist bit-depth regimes ($\beta<6$), $1$-bit CS achieves a significantly higher SNR than the other two techniques. When $6<\beta<8$, $1$-bit CS is competitive with the BPDN scenario. Thus, for a fixed number of bits, $1$-bit CS is competitive to conventional sampling with uniform quantization, especially in low bit-depth regimes.

Discussion

In this paper we have developed a rigorous mathematical foundation for $1$-bit CS. Specifically, we have demonstrated a lower bound on reconstruction error as a function of the number of measurements and the sparsity of the signal. We have demonstrated that Gaussian random projections almost reach this lower bound (up to a log factor) in the noiseless case. This behavior is consistent with and extends existing results in the literature on multibit scalar quantization and 1-bit quantization of non-sparse signals.

Using the B$\epsilon$SE, we have proven that $1$-bit CS systems are robust to measurement noise added before quantization as well as to signals that are not exactly sparse but compressible.

We have introduced a new $1$-bit CS algorithm, BIHT, that achieves better performance over previous algorithms in the noiseless case. This improvement is due to the enforcement of consistency using a one-sided linear objective, as opposed to a quadratic one. The linear objective is similar to the hinge loss from the machine learning literature.

We remind the reader that the central goal of this paper has been signal acquisition with quantization. As explained previously, one motivation for our work is the development of very high speed samplers. In this case, we are interested in building fast samplers by relaxing the requirements on the primary hardware burden, the quantizer. Such devices are susceptible to noise. Thus, while our noiseless results extend previous $1$-bit quantization results (e.g., see and ) to the sparse signal model setting and are of theoretical interest, a major contribution has been the further development of the robust guarantees, even if they produce error rates that seem suboptimal when compared to the noiseless case.

Acknowledgments

Thanks to Rachel Ward for pointing us to the right reference with regards to the lower bound (17) used in Appendix A and recommending several useful articles as well as Vivek Goyal for pointing us to additional prior work in this area. Thanks to Zaiwen Wen and Wotao Yin for sharing some of the data from for our algorithm comparisons, as well as engaging in numerous conversations on this topic. Thanks also to Nathan Srebro for his advice and discussion related to the one-sided penalty comparison and connections to binary classification, and thanks to Amirafshar Moshtaghpour for his correction of a small error in the bounds of Appendix G. Finally, thanks to Yaniv Plan and anomynous reviewers for their useful advices and remarks for improving this paper, and in particular the proof of Theorem 1 with respect to the optimality of the $\Sigma^{*}_{K}$ covering.

Appendix A Lemma 1: Intersections of Orthants by Subspaces

While there are $2^{M}$ available quantization points provided by $1$-bit measurements, a $K$-sparse signal will not use all of them. To understand how effectively the quantization bits are used, we first investigate how the $K$-dimensional subspaces projected from the $N$-dimensional $K$-sparse signal spaces intersect orthants in the $M$-dimensional measurement space, as shown in Fig 1 for $K=2$ and $M=3$.

We use $I(M,K)$ to denote the maximum number of orthants in $M$ dimensions intersected by a $K$-dimensional subspaces. A bound of for $I(M,K)$ is developed in :

For $K\leq M/2$, this simplifies to $I(M,K)\leq 2K{M-1\choose K-1}$.

Using ${p\choose q-1}+{p\choose q}={p+1\choose q}$ we can also derive a simple bound on (17) for $K\leq M$. We observe that

Repeating the same argument, we find $\sum_{l=1}^{K-1}\binom{M}{l}\leq\sum_{l=2}^{K-1}\binom{M+1}{l}\leq\cdots\leq\binom{M+K-2}{K-1}$ and finally

using the bound $\binom{M}{K}\leq\left(\tfrac{eM}{K}\right)^{K}$.

While the bound in (17) is tight and holds for subspaces in a general configuration, the closed form simplified bound in (18) can be improved by a factor of $(M-K+1)$ (which asymptotically makes no difference in the subsequent development) using the proof we develop in the remainder of this appendix. In addition to the improvement, the proof also provides significant geometrical intuition to the problem.

First we define two new elements in the geometry of the problem: orthant boundaries and their faces. Each orthant has $M$ boundaries of dimension $M-1$, defined as the subspace with a coordinate set to 0:

We split each boundary into $2^{M-1}$ faces, defined as the set

Next, we upper bound $I(M,K)$ using an inductive argument that relies on the following two lemmas:

For $K>1$, a $K$-dimensional subspace that intersects an orthant also non-trivially intersects at least $K$ faces bordering that orthant.

Consider a $K$-subspace $\mathcal{S}$, a point $\bm{p}\in\mathcal{S}$ interior to the orthant $\mathcal{O}_{{\rm sign}\,{\bm{p}}}$, and a vector $\bm{x}_{1}\in\mathcal{S}$ non-parallel to $\bm{p}$. The following iterative procedure can be used to prove the result:

Starting from 0, grow $a$ until the set $\bm{p}\pm a\bm{x}_{l}$ intersects a boundary $\mathfrak{B}_{i}$, say at $a=a_{l}$. It is straightforward to show that as $a$ grows, a boundary will be intersected. The point of intersection is in the face $\mathcal{F}_{i,{\rm sign}\,{\bm{p}}}$. The set $\{\bm{p}\pm a\bm{x}_{l}|a\in(0,a_{l})\}$ is in the orthant $\mathcal{O}_{{\rm sign}\,{\bm{p}}}$.

Determine a vector $\bm{x}_{l+1}\in\mathcal{S}$ parallel to all the boundaries already intersected and not parallel to $\bm{p}$, set $l=l+1$ and iterate from step 1.

A vector can always be found in step 2 for the first $K$ iterations since $\mathcal{S}$ is $K$-dimensional. The vector is parallel to all the boundaries intersected in the previous iterations and therefore $\bm{p}\pm a\bm{x}_{l}$ always intersects a boundary not intersected before. Therefore, at least $K$ distinct faces are intersected. $\Box$

Lemmas 6 and 7 lead to the main result in this Appendix. Lemma 1 in Section 2.1 follows trivially.

The number of orthants intersected by a $K$-dimensional subspace $\mathcal{S}$ in an $M$-dimensional space $\mathcal{V}$ is upper bounded by

The main intuition is that since the faces on each boundary are equivalent to orthants in the lower dimensional subspace of the boundary, the maximum number of faces intersected at each boundary is a problem of dimension $I(M-1,K-1)$.

If $\mathcal{S}$ is contained in one of the boundaries in $\mathcal{V}$, the number of orthants of $\mathcal{V}$ intersected is at most $I(M-1,K)$. Since $I(M,K)$ is non-decreasing in $M$ and $K$, we can ignore this case in determining the upper bound.

If $\mathcal{S}$ is not contained in one of the boundaries then Lemma 6 shows that the intersection of $\mathcal{S}$ with any boundary $\mathfrak{B}_{i}$ is a $(K-1)$-dimensional subspace in $\mathfrak{B}_{i}$. To count the faces of $\mathfrak{B}_{i}$ intersected by $\mathcal{S}$ we use the observation in the definition of faces above, that each face is also an orthant of $\mathfrak{B}_{i}$. Therefore, the maximum number of faces of $\mathfrak{B}_{i}$ intersected is a recursion of the same problem in lower dimensions, i.e., is upper bounded by $I(M-1,K-1)$. Since there are $M$ boundaries in $\mathcal{V}$, it follows that the number of faces in $\mathcal{V}$ intersected by $\mathcal{S}$ is upper bounded by $M\cdot I(M-1,K-1)$.

Using Lemma 7 we know that for an orthant to be intersected, at least $K$ faces adjacent to it should be intersected. Since each face is adjacent to two orthants, the total number of orthants intersected cannot be greater than twice the number of faces intersected divided by $K$:

To complete the induction we use $I(M,1)=2$ for all $M$; for $K=1$ the subspace is a line through the origin, which can intersect only two orthantsWe recall that, from the definition (4), two different orthants have an empty intersection.. This leads to:

Appendix B Theorem 1: Distributing Signals to Quantization Points

Thus, instead of determining the optimal cover of $\Sigma^{*}_{K}$, we establish a lower bound on $r$ required to cover a subset $\widetilde{\Sigma}^{*}_{K}$ of $\Sigma^{*}_{K}$ using the same number of points. A cover of $\Sigma^{*}_{K}$ with a smaller $r$ would not be possible, since that would also cover $\widetilde{\Sigma}^{*}_{K}$ with the same or smaller $r$. Therefore, this $r$ establishes a lower bound for the cover of $\Sigma^{*}_{K}$. To establish the bound, we pick $\widetilde{\Sigma}^{*}_{K}$ such that the neighborhood around the intersection of the balls is not included. Specifically, we pick

With this choice of $\widetilde{\Sigma}_{K}^{*}$, an optimal covering can be obtained by merging the optimal coverings of each $\widetilde{S}_{i}$ for $i\in[L]$. For an optimal covering of distance $r$, each of the elements in $\widetilde{S}_{i}$ should belong to some ball of radius $r$ centered at the quantization point. Thus, each quantization point and its corresponding $r$-ball should cover as large an area of $\widetilde{S}_{i}$ as possible. This is achieved when the quantization point is on $\widetilde{S}_{i}$, and the intersection of the ball with $\widetilde{S}_{i}$ is a spherical cap of radius $r$ . Thus, for the spherical caps to cover $\widetilde{S}_{i}$, the total area of all spherical caps in the cover should be greater than the area of $\widetilde{S}_{i}$. Furthermore, since the overall cover of $\widetilde{\Sigma}^{*}_{K}$ is composed of separate cover of each $\widetilde{S}_{i}$, the total area of all spherical caps used for the cover should be greater than the area of $\widetilde{\Sigma}^{*}_{K}$.

Therefore, since $2^{K}L\binom{M}{K}$ quantization points and corresponding spherical caps are available, according to Lemma 1 and Corollary 1, to cover $L$ subsets of $K$-spheres, as described above, the cover should satisfy

where $\sigma(\cdot)$ denotes the rotationally invariant area measure the $K$-sphere $S_{i}$ and $\kappa(r)$ denotes the surface of a spherical cap of radius $r$.

To determine the smallest $r$ satisfying (20), we thus need to measure the set $\widetilde{\Sigma}^{*}_{K}$. Choosing one $i\in[L]$ we have $\sigma(\widetilde{\Sigma}^{*}_{K})=L\sigma(\widetilde{S}_{i})$ since the sets $\widetilde{S}_{k}$ ($k\in[L]$) are disjoint with identical area. We first show that

also shown in the figure, which is non-empty for $2r\leq 1/\sqrt{K}$. Since $\mathcal{C}_{r}(\widetilde{S}^{+}_{i})\cap S_{i}=\widetilde{S}_{i}^{+}$ and $2r\bm{1}\in\mathcal{C}(\widetilde{S}^{+}_{i})$, it is straightforward to show that $\mathcal{C}_{r}(\widetilde{S}^{+}_{i})\subset\mathcal{C}(\widetilde{S}^{+}_{i})$, and therefore the measure of $\mathcal{C}_{r}(\widetilde{S}^{+}_{i})$ is a lower bound to the measure of $C(\widetilde{S}^{+}_{i})$. Furthermore, by the translation invariance of $\mu$,

which, using (22), implies that ${\sigma(\widetilde{S}^{+}_{i})}/{\sigma(S^{K-1})}\geq\alpha^{-K}2^{-K}$ and $\sigma(\widetilde{\Sigma}^{*}_{K})=L\sigma(\widetilde{S}_{i})\geq(1-2r\sqrt{K})^{K}L\sigma(S^{K-1})$.

where $\kappa(r)\leq r^{K}\sigma(S^{K-1})$ . From $\binom{M}{K}\leq(eM/K)^{K}$, the result follows:

Appendix C Theorem 2: Optimal Performance via Gaussian Projections

Let us fix a radius $\delta>0$ to be precised later. The sphere $\Sigma^{*}(T)$ can be covered with a finite set $Q_{\delta}\subset\Sigma^{*}(T)$ of no more than $(3/\delta)^{D}$ points such that, for any $\bm{w}\in\Sigma^{*}(T)$, there exists a $\bm{q}\in Q_{\delta}$ with $\bm{w}\in B^{*}_{\delta}(\bm{q})$ .

Using the notation $d_{S}$ defined in Sec. 3.1, given a vector $\bm{\varphi}\sim\mathcal{N}^{N\times 1}(0,1)$ and two distinct points $\bm{p}$ and $\bm{q}$ in $Q_{\delta}$, we have that

from Lemma 9 (given in Appendix D). Since for all $\bm{u}\in B_{\delta}^{*}(\bm{p})$ and $\bm{v}\in B_{\delta}^{*}(\bm{q})$

By setting $\delta=\pi\epsilon_{o}/(4+\pi\sqrt{2\pi D})$ (and reversing the inequality), we obtain

Thus, for $M$ different random vectors $\bm{\varphi}_{i}$ arranged in $\Phi=(\bm{\varphi}_{1},\,\cdots,\bm{\varphi}_{M})^{T}\sim\mathcal{N}^{M\times N}(0,1)$, and for the associated mapping $A$ defined in (3), we get

In other words, we have found a bound on the probability that two vectors’ measurements are consistent, even if their Euclidean distance is greater than $\epsilon_{o}$, but only for vectors in the restricted (sub) sphere $\Sigma^{*}(T)$. Now we seek to cover the rest of the space $\Sigma_{K}^{*}$ (unit norm $K$-sparse signals).

Since there are no more than ${|Q_{\delta}|\choose 2}\leq(|Q_{\delta}|)^{2}\leq(3/\delta)^{2D}$ pairs of distinct points in $Q_{\delta}$, we find

To obtain the final bound, we observe that any pair of unit $K$-sparse vectors $\bm{x}$ and $\bm{s}$ in $\Sigma_{K}^{*}$ belongs to some $\Sigma^{*}(T)$ with $T={\rm supp}\,\bm{x}\cup{\rm supp}\,\bm{s}$ and $|T|\leq 2K$. There are no more than ${N\choose 2K}\leq(eN/2K)^{2K}$ of such sets $T$, and thus setting $D=2K$ above yields

where the second inequality follows from $1-\frac{\epsilon_{o}}{2}\leq\exp\frac{\epsilon_{o}}{2}$. By upper bounding this probability by $\eta$ and solving for $M$, we obtain

Since $K\geq 1$, we have that $\frac{1}{\pi}(12+6\pi\sqrt{\pi K})<17\sqrt{\tfrac{2K}{e}}$, and thus the previous relation is then satisfied when

Appendix D Lemma 3: Concentration of Measure for δ𝛿\delta-Balls

Given $\bm{u}^{\prime}\in B^{*}_{\delta}(\bm{x})$ and $\bm{v}^{\prime}\in B^{*}_{\delta}(\bm{s})$, the quantity Md_{H}\big{(}A(\bm{u}^{\prime}),A(\bm{v}^{\prime})\big{)} is the sum $\sum_{i}A_{i}(\bm{u}^{\prime})\oplus A_{i}(\bm{v}^{\prime})$, where $A_{i}(\bm{u}^{\prime})$ stands for the $i^{\rm th}$ component of $A(\bm{u}^{\prime})$. For one index $1\leq i\leq M$

This indicates that with a probability higher than $1-2e^{-2M\epsilon^{2}}$, we have

The final result follows by lower bounding $p_{0}$ and $p_{1}$ as in Lemma 9.

Given $0\leq\delta<1$ and two unit vectors $\bm{x},\bm{s}\in S^{D-1}$, we have

We now seek a lower bound on $p_{1}$. Computing this probability amounts to estimating

where $\mathcal{W}_{\delta}:=\{\bm{\varphi}:\langle\bm{\varphi},\bm{u}\rangle\langle\bm{\varphi},\bm{v}\rangle\leq 0,\ \forall\bm{u}\in B^{*}_{\delta}(\bm{x}),\ \forall\bm{v}\in B^{*}_{\delta}(\bm{s})\}$ is the set of all vectors $\bm{\varphi}$ such that its inner product with $\bm{u}$ and $\bm{v}$ result in different signs.

The remainder of the proof is devoted to finding an appropriate way to integrate the set $\mathcal{W}_{\delta}$. To this end, we begin by demonstrating that estimating $p_{1}$ can be simplified with the following equivalence (proved just after the completion of the proof of Lemma 9).

Using the hyper spherical coordinate system developed earlier and denoting the angle $\pi\,d_{S}(\bm{x},\bm{s})$ by $\theta$, membership in $\mathcal{V}^{-}_{\delta}$ can be expressed as

Indeed, requirement (R1) enforces $\langle\bm{\varphi},\bm{x}\rangle\langle\bm{\varphi},\bm{s}\rangle\leq 0$, while (R2) and (R3) are direct translations of the requirements that $\|\bm{x}\,-\,\mathcal{P}_{\Pi(\varphi)}\,\bm{x}\|=|\langle\widehat{\bm{\varphi}},\bm{x}=\bm{e}_{D}\rangle|\geq\delta$ and $\|\bm{s}\,-\,\mathcal{P}_{\Pi(\varphi)}\,\bm{s}\|=|\langle\widehat{\bm{\varphi}},\bm{s}=-\sin\theta\,\bm{e}_{D}+\cos\theta\,\bm{e}_{D-1}\rangle|\geq\delta$, with $\widehat{\bm{\varphi}}=\tfrac{1}{\|\bm{\varphi}\|}\bm{\varphi}$.

We are now ready to integrate to find $p_{1}$:

with $\chi_{\lambda}(\phi)=1$ if $|\sin\phi\,|\geq\lambda$ and 0 else, for some $\lambda\in$, and $g(\delta,\bm{\varphi})=\delta/(\sin\phi_{1}\,\cdots\,\sin\phi_{D-2})$.

and $\max(2\theta-4\arcsin\lambda,0)\geq 2\theta-2\pi\lambda$, since $\lambda\leq\arcsin\lambda\leq\tfrac{\pi}{2}\lambda$ for any $\lambda\in$. Consequently,

Using the fact that $I_{n}=\sqrt{\pi}\,\Gamma(\tfrac{n+1}{2})/\Gamma(\tfrac{n}{2}+1)\geq{\sqrt{\pi}}/{\sqrt{\frac{n}{2}+\frac{1}{4}}}$, we obtain $I_{D-2}\geq\tfrac{\sqrt{\pi}}{\sqrt{\frac{D}{2}-\frac{3}{4}}}\geq\sqrt{\tfrac{2\pi}{D}}$, and thus

If we want a meaningful bound for $p_{1}\geq 0$, then we must have $d_{S}({\bm{x},\bm{s}})\geq\sqrt{\tfrac{\pi}{2}D}\,\delta\geq\delta$. Therefore, as soon as the lower bound is positive, the aforementioned condition $d_{S}({\bm{x},\bm{s}})\geq\delta$ always holds.

The lower bound for $p_{0}$ is obtained similarly. It is straightforward to show that $p_{0}=\mu(\mathcal{V}^{+}_{\delta})$, with $\mathcal{V}^{+}_{\delta}=\{\bm{\varphi}:\langle\bm{\varphi},\bm{x}\rangle\langle\bm{\varphi},\bm{s}\rangle>0,\|\bm{x}\,-\,\mathcal{P}_{\Pi(\varphi)}\,\bm{x}\|\geq\delta,\|\bm{y}\,-\,\mathcal{P}_{\Pi(\varphi)}\,\bm{s}\|\geq\delta\}$. Lower bounding $\mu(\mathcal{V}^{+}_{\delta})$ as for $\mu(\mathcal{V}^{+}_{\delta})$, the only difference occurring with the integral on $\phi_{D-2}$ given by

Therefore, the lower bound of $p_{0}$ amounts to change $\theta\to\pi-\theta$ in the one of $p_{1}$, which provides the result. $\Box$

If $\delta=0$, there is nothing to prove. Therefore $\delta>0$ and if $\bm{\varphi}^{*}$ belongs to either $\mathcal{V}_{\delta}$ or $\mathcal{W}_{\delta}$, we must have $\langle\bm{\varphi},\bm{x}\rangle\langle\bm{\varphi},\bm{s}\rangle<0$. It is also sufficient to work on the restriction of $\mathcal{V}_{\delta}$ and $\mathcal{W}_{\delta}$ to unit vectors.

(i) $\mathcal{V}_{\delta}\subset\mathcal{W}_{\delta}$: By contradiction, let us assume that $\bm{\varphi}^{*}\in\mathcal{V}_{\delta}$ but $\bm{\varphi}^{*}\notin\mathcal{W}_{\delta}$. Without any loss of generality, $\langle\bm{\varphi}^{*},\bm{x}\rangle>0$ and $\langle\bm{\varphi}^{*},\bm{s}\rangle<0$. Since $\bm{\varphi}^{*}\notin\mathcal{W}_{\delta}$, there exist two vectors $\bm{u}^{*}\in B^{*}_{\delta}(\bm{x})$ and $\bm{v}^{*}\in B^{*}_{\delta}(\bm{s})$ such that $\langle\bm{\varphi}^{*},\bm{u}^{*}\rangle\langle\bm{\varphi}^{*},\bm{v}^{*}\rangle>0$. If $\langle\bm{\varphi}^{*},\bm{u}^{*}\rangle>0$ and $\langle\bm{\varphi}^{*},\bm{v}^{*}\rangle>0$, then, since $\langle\bm{\varphi}^{*},\bm{s}\rangle<0$ and by continuity of the inner product, there exist a $\lambda\in(0,1)$ such that $\langle\bm{\varphi}^{*},\bm{s}(\lambda)\rangle=0$ with $\bm{s}(\lambda)=\bm{s}+\lambda(\bm{v}^{*}-\bm{s})$. Therefore, $\bm{s}(\lambda)\in\Pi(\bm{\varphi})$ and, by definition of the orthogonal projection, $\|\bm{s}-\mathcal{P}_{\Pi(\bm{\varphi})}\,\bm{s}\|\leq\|\bm{s}-\bm{s}(\lambda)\|\leq\lambda\delta<\delta$ which is a contradiction. If $\langle\bm{\varphi}^{*},\bm{u}^{*}\rangle<0$ and $\langle\bm{\varphi}^{*},\bm{v}^{*}\rangle<0$, we apply the same reasoning on $\bm{x}$ and $\bm{u}^{*}$. Therefore, $\mathcal{V}_{\delta}\subset\mathcal{W}_{\delta}$.

(ii) $\mathcal{W}_{\delta}\subset\mathcal{V}_{\delta}$: If $\bm{\varphi}^{*}\in\mathcal{W}_{\delta}$ with $\bm{\varphi}^{*}\notin\mathcal{V}_{\delta}$, we have either $\|\bm{x}\,-\,\mathcal{P}_{\Pi(\varphi^{*})}\,\bm{x}\|<\delta$ or $\|\bm{s}\,-\,\mathcal{P}_{\Pi(\varphi^{*})}\,\bm{s}\|<\delta$. Let us say that $\|\bm{x}\,-\,\mathcal{P}_{\Pi(\varphi^{*})}\,\bm{x}\|<\delta$. Then, for $\bm{w}=\bm{x}\,+\,\delta\,(\mathcal{P}_{\Pi(\varphi^{*})}\,\bm{x}-\bm{x})/\|\mathcal{P}_{\Pi(\varphi^{*})}\,\bm{x}-\bm{x}\|\in B^{*}_{\delta}(\bm{x})$, \langle\bm{\varphi}^{*},\bm{x}\rangle\langle\bm{\varphi}^{*},\bm{w}\rangle=(\langle\bm{\varphi}^{*},\bm{x}\rangle)^{2}\big{(}1-\delta/\|\mathcal{P}_{\Pi(\varphi^{*})}\,\bm{x}-\bm{x}\|\big{)}+\delta\,\langle\bm{\varphi}^{*},\mathcal{P}_{\Pi(\varphi^{*})}\,\bm{x}\rangle<0. However, $\bm{\varphi}^{*}\in\mathcal{W}_{\delta}$ and $\langle\bm{\varphi}^{*},\bm{x}\rangle\langle\bm{\varphi}^{*},\bm{s}\rangle<0$, leading to $\langle\bm{\varphi}^{*},\bm{w}\rangle\langle\bm{\varphi}^{*},\bm{s}\rangle>0$, which is a contradiction. $\Box$

Appendix E Theorem 3: Gaussian Matrices Provide Bϵitalic-ϵ\epsilonSEs

The strategy for proving Theorem 3 will be to count the number of pairs of $K$-sparse signals that are Euclidean distance $\delta$ apart. We will then apply the concentration results of Lemma 3 to demonstrate that the angles between these pairs are approximately preserved. We specifically proceed by focusing on a single $K$-dimensional subspace (intersected with the unit sphere) and then by applying a union bound to account for all possible subspaces.

Let $\Phi_{T}$ be the matrix formed by the columns of $\Phi$ indexed by $T$ and note that $\Phi_{T}\bm{w}=\Phi\bm{w}$. Given $\epsilon^{\prime}\geq 0$, for all pairs of points $\bm{p},\bm{q}\in Q_{T,\delta}$, we have

This follows from Lemma 3 with $D=K$, since $\Phi_{T}$ is a Gaussian matrix and by invoking the union bound, since there are ${C_{\delta}\choose 2}\leq C^{2}_{\delta}=(3/\delta)^{2K}$ such pairs $\bm{x},\bm{s}$.

The bound (25) can be extended to all possible index sets $T$ of size $K$ via the union bound. Specifically, for all $T\subset[N]$ and all pairs of points $\bm{p},\bm{q}\in Q_{T,\delta}$, we have now jointly

since there are no more than ${N\choose K}\leq(eN/K)^{K}$ possible $T$.

We can reformulate this last result as follows. Let us take any pair of points on the sphere $\bm{x},\bm{s}\in S^{N-1}$ such that their joint support $T={\rm supp}\,(\bm{x})\,\cup\,{\rm supp}\,(\bm{s})$ has a size $|T|\leq K$. We have obviously $\bm{x},\bm{s}\in\Sigma^{*}(T)$. Taking the covering set $Q_{T,\delta}$ defined for $\Sigma^{*}(T)$, there exist two points $\bm{p},\bm{q}\in Q_{T,\delta}$ such that $\bm{x}\in B^{*}_{\delta}(\bm{p})$ and $\bm{s}\in B^{*}_{\delta}(\bm{q})$. From (26), with a probability exceeding $1-2\,(\tfrac{eN}{K})^{K}\,(\tfrac{3}{\delta})^{2K}\,e^{-2\epsilon^{\prime 2}M}$, we have

To obtain our final bound, consider that $\bm{x}\in B^{*}_{\delta}(\bm{p})$ implies that $\pi\,d_{S}({\bm{x},\bm{p}})\leq 2\arcsin\delta/2\leq\pi\delta/2$, and $d_{S}({\bm{s},\bm{q}})$ can be similarly bounded. Thus, $d_{S}({\bm{x},\bm{s}})\geq d_{S}({\bm{p},\bm{q}})-\delta$ and $d_{S}({\bm{x},\bm{s}})\leq d_{S}({\bm{p},\bm{q}})+\delta$, and (27) becomes

Let us define the probability of failure as $2\,(\tfrac{eN}{K})^{K}\,(\tfrac{3}{\delta})^{2K}\,e^{-2\epsilon^{\prime 2}M}=\eta,$ where $0<\eta<1$, and set $\epsilon^{\prime}=(1+\sqrt{\tfrac{\pi}{2}K})\,\delta$ and $2\epsilon^{\prime}=\epsilon$. Solving for $M$, we finally get that $|d_{H}(A(\bm{x}),A(\bm{s}))-d_{S}({\bm{x},\bm{s}})\,|\leq\epsilon$ with a probability bigger than $1-\eta$ if

Since $K\geq 1$, we have that $2(1+\sqrt{2\pi K})\leq 2(1+\sqrt{2\pi})\sqrt{K}<35\sqrt{K}/\sqrt{9e}$, and thus the previous relation is satisfied if

Appendix F Lemma 4: Stability with Measurement Noise

In Lemma 4, since $\Phi\sim\mathcal{N}^{M\times N}(0,1)$, each $y_{i}=(\Phi\bm{x})_{i}$ follows a Gaussian distribution $\mathcal{N}(0,\|\bm{x}\|_{2}^{2})$, and furthermore, since we have independent additive noise, $z_{i}=y_{i}+n_{i}=(\Phi\bm{x})_{i}+n_{i}$ follows the Gaussian distriubtion $\mathcal{N}(0,\|\bm{x}\|_{2}^{2}+\sigma^{2})$.

with the pdf $f_{y_{i}}(t)=g(t;\sigma^{\prime})=\frac{1}{\sqrt{2\pi}t}\exp(-t^{2}/2\sigma^{\prime 2})$. This leads to

Appendix G Asymptotic bound on ϵitalic-ϵ\epsilon in Theorems 2 and 3

Both Theorem 2 and Theorem 3 provide guarantees on the worst-case error $\epsilon$ of the form

for some exponent $n\in\{1,2\}$, and for given constants $\alpha,\beta,\gamma>0$.

In this appendix we show that, considering $0<\eta<1$ fixed, the relation (29) implies

asymptotically in ${M}/{K}$ and $N$. Notice that, up to a redefinition $\epsilon^{n}\to\epsilon$ and $\gamma/n\to\gamma$, it is sufficient to prove the relation for $n=1$. We also define $\rho:=\beta\log(1/\eta)$.

First, we consider $N$ fixed and show \epsilon=O\big{(}\tfrac{K}{M}\log(\tfrac{M}{K})\big{)}. Let us assume this is not the case, i.e., for all $c>0$, and all $R_{0}>0$, there exists a ratio ${M}/{K}>R_{0}$ such that $\epsilon>c\,({K}/{M})\log({M}/{K})$. Therefore,