Fast binary embeddings, and quantized compressed sensing with structured matrices
Thang Huynh Rayan Saab
cs.IT eess.SP math.IT stat.ML


Masses of doubly heavy-quark baryons in an extended
  chromomagnetic model
    Wei-Zhen Deng
    
==========================================================================




This paper deals with two related problems, namely distance-preserving binary embeddings and quantization for compressed sensing. First, we propose fast methods to replace points from a subset 𝒳⊂^n, associated with the Euclidean metric, with points in the cube {± 1}^m and we associate the cube with a pseudo-metric that approximates Euclidean distance among points in 𝒳. Our methods rely on quantizing fast Johnson-Lindenstrauss embeddings based on bounded orthonormal systems and partial circulant ensembles, both of which admit fast transforms. 
Our quantization methods utilize noise-shaping, and include Sigma-Delta schemes and distributed noise-shaping schemes. The resulting approximation errors  decay polynomially and exponentially fast in m, depending on the embedding method. This dramatically outperforms the current decay rates associated with binary embeddings and Hamming distances. Additionally, it is the first such binary embedding result that applies to fast Johnson-Lindenstrauss maps while preserving ℓ_2 norms. 

Second, we again consider  noise-shaping schemes, albeit this time to quantize compressed sensing measurements arising from bounded orthonormal ensembles and partial circulant matrices. We show that these methods yield a reconstruction error that again decays with the number of measurements (and bits), when using convex optimization for reconstruction. Specifically, for Sigma-Delta schemes, the error decays polynomially in the number of measurements, and it decays exponentially  for distributed noise-shaping schemes based on beta encoding. These results are near optimal and the first of their kind dealing with bounded orthonormal systems. 


 












§ INTRODUCTION

In signal processing and machine learning, given a linear map y = A x, where x is an unknown signal in ^n and A is an m× n matrix in ^m× n, one would often like to quantize or digitize y, i.e., map each entry y_i of y to a finite discrete set, say 𝒜. 

On the one hand, viewing A as a measurement operator, quantization is the step that allows us to move from the analog world of continuous measurements to the digital world of bit-streams. It thereby allows computer processing of the signals, as well as their storage and transmission. On the other hand, one can view A as a linear embedding, taking some vectors x∈𝒯⊂^n to their image in ^m. For a vector x∈𝒯,  the quantized version of Ax can be viewed as a non-linear embedding of x∈^n into 𝒜^m. It can therefore be used to expedite such tasks as information retrieval (say via nearest neighbor searches) provided the action of A and the quantization both admit fast computation, and provided "distance" computations in the embedding space can be done efficiently as well. 



 §.§ A brief introduction to compressed sensing


While in the remainder of the paper we address binary embeddings before we address quantization  in the compressed sensing context, we find it more convenient here to first introduce  compressed sensing. Suppose x ∈^n is an unknown vector  which we wish to reconstruct from m linear measurements. Specifically, suppose we collect the measurements 
    y_j = a_j, x + w_j
 where each a_j, j=1,...,m, is a known measurement vector in ^n and w_j denotes unknown noise. When x is sparse (i.e., most of its coefficients are zero) or compressible (i.e., well approximated by sparse vectors) x can be recovered (or approximated) from the measurements, even when m≪ n. Indeed, the study of recovery algorithms and reconstruction guarantees from such measurements is the purview of  compressed sensing (CS) and one of the most popular reconstruction methods in this setting is ℓ_1-minimization. Here, the vector x is approximated by x̂, the solution to 

    min_z∈^nz_1     A z - y_2 ≤η.

Above A is the m× n matrix with a_j as its jth row, y = (y_j)_j=1^m is the vector of acquired measurements, and η is an upper bound on the norm of the noise vector w = (w_j)_j=1^m.

Some of the earliest results on compressed sensing (e.g., <cit.>) show that for a certain class of subgaussian random measurement matrices A, including those with i.i.d. standard Gaussian or ± 1 Bernoulli entries, with high probability on the draw of the matrix and uniformly on x, the solution x to (<ref>) obeys

    x - x_2 ≲η+ σ_k(x)_1/√(k),

provided m ≳ klog(n/k). Such guarantees are often based  on the measurement matrix A satisfying the so-called Restricted Isometry Property (RIP), defined precisely in Section <ref>. 













The above results on subgaussian random matrices are mathematically important both for the techniques they introduce and as a proof of concept that compressed sensing is viable. Nevertheless, for physical reasons one may not have full design control over the measurement matrix in practice. Moreover, for practical reasons (including reconstruction speed), one may require that the measurement matrices admit fast multiplications. Such reasons motivated the study of structured random matrices in the compressed sensing context (see, e.g., <cit.>). Perhaps two of the most popular classes of structured random measurement matrices are those drawn from a bounded orthogonal ensemble (BOE) or from a partial circulant ensemble (PCE).  Indeed, studying the interplay between  structured random matrices and quantization is  one focus of this paper.



Herein, we are interested in the case when A is drawn from a bounded orthogonal ensemble, or from a partial circulant ensemble, both of which we now introduce. 





Let 1/√(n)U ∈^n× n be any unitary matrix with |U_ij| ≤ 1 for all entries U_ij of U. A matrix A ∈^m× n is drawn from the bounded orthogonal ensemble associated with U by picking each row a_i of the matrix A uniformly and independently from the set of all rows of U. 

Examples of U include the n× n discrete Fourier matrix and the n× n Hadamard matrix.

For physical reasons, BOEs arise naturally in various important applications of compressed sensing, including those involving Magnetic Resonance Imaging (MRI) (see, e.g., <cit.>). An additional practical benefit of BOEs, e.g., those based on the Fourier or Hadamard transforms, is implementation speed.  When viewed as linear operators, such matrices admit fast implementations with a number of additions and multiplications that scales like n logn. This is in contrast to the cost of standard matrix vector multiplication which scales like n^2. As such, BOEs have also appeared in various results involving fast Johnson-Lindenstrauss embeddings (e.g., <cit.>).


For z∈^n, the circulant matrix H_z ∈^n× n is given by its action H_z x = z*x, where * denotes convolution. Fix Ω⊂{1, 2, …, n} of size m arbitrarily. A matrix A is drawn from the partial circulant ensemble associated with Ω  by choosing a vector σ uniformly at random on {-1, 1}^n (i.e., the entries σ_i of σ are independent ± 1 Bernoulli random variables), and setting the rows of  A to be the rows of H_σ indexed by Ω. 

Partial Circulant Ensembles also appear naturally in various applications of compressed sensing, including those involving radar and wireless channel estimation mainly due to the fact that the action of a circulant matrix on a vector is equivalent to its convolution with a row of the circulant matrix. We refer to <cit.> for a discussion on these applications. As with BOEs, PCEs also admit fast transformations,  as convolution is essentially diagonalized by the Fourier transform, which admits fast implementation. As such, PCEs also admit an implementation with a number of addition and multiplications that scales with nlog n as opposed to n^2. For this reason PCEs, like BOEs, feature prominently in constructions for fast Johnson-Lindenstrauss embeddings. An additional benefit in applications is that the memory required for storing a PCE scales like n (versus mn for an unstructured matrix).

Candés and Tao were the first to study structured random matrices  drawn from a BOE, in the compressed sensing context. In <cit.>, they show that such matrices satisfy the restricted isometry property with high probability, provided that the number of measurements m ≳ klog^6(n). Later, many researchers (e.g., <cit.>)  improved the dependence of the number of measurements m on n, i.e., they improved the logarithmic factors. To our knowledge, the current best result is by Haviv and Regev <cit.> and achieves a lower bound m ≳ klog^2(n). Similarly, many researchers have studied recovery guarantees for compressed sensing with random measurement matrices  drawn from the partial circulant ensembles (e.g., <cit.>), eventually showing a similar dependence of m on k and n, i.e., m≳ klog^4n in <cit.>.  Our own results will apply to both BOEs and PCEs (in both the compressed sensing and binary embedding contexts) with the added caveat of randomizing the signs of their rows. It is therefore useful to introduce the following construction. 

An admissible distribution on m× n matrices corresponds to constructing  Φ∈^m× n as follows.


  * Draw A either from a bounded orthogonal ensemble associated with a matrix U as in Definition <ref> or from a partial circulant ensemble associated with a set Ω of size m as in Definition <ref>. Let a_j be the j-th row of A.

  * Let ϵ_j be independent ± 1 Bernoulli random variables which are also independent of A.

  * Let Φ be an m× n matrix whose j-th row is ϵ_j a_j.






 §.§ A brief introduction to quantization

Consider the linear measurements y = A x of a signal x. Quantization is the process by which the measurement vector y is replaced by a vector of elements from a finite set, say 𝒜, known as the quantization alphabet. The finiteness of 𝒜 allows its elements to be represented with finite binary strings, which in turn allows  digital storage and processing. Indeed, such digital processing is 
necessary in the field of binary embedding <cit.> and compressed sensing (see, e.g., <cit.>), where careful selection of A and 𝒜 can yield faster, memory-efficient algorithms. In binary embedding one wishes to design a quantization map :^m →^m which approximately preserves the distance between two signals (see below). On the other hand, in compressed sensing one typically requires a reconstruction algorithm ℛ: 𝒜^m →^n such that given the quantized measurements (A x),  x̂ = ℛ((A x)) ensures a small reconstruction error x - x̂_2.
Various choices of quantization maps and reconstruction algorithms have been proposed in the context of binary embedding and compressed sensing. These have ranged from the most intuitive quantization approaches, namely memoryless scalar quantization <cit.>, to more sophisticated approaches based on  noise shaping quantization, including ΣΔ  quantization <cit.> and distributed noise shaping quantization <cit.>, as well as others <cit.>. Indeed, the afore-mentioned noise shaping quantization techniques combine computational simplicity and the ability to yield favorable error guarantees as a function of the number of measurements. We will use them to obtain our  results and thus provide a necessary, more detailed, overview in Section <ref>.



 §.§ A brief introduction to binary embeddings


Low distortion embeddings have played an important role recently in  signal processing and machine learning  as they transform high dimensional signals into low-dimensional ones while preserving geometric properties. The benefits of such embeddings are direct consequences of the dimensionality reduction and they include the potential for reduced storage space and computational time associated with the (embedded) signals. Perhaps one of the most important embeddings is given by the Johnson-Lindenstrauss (JL) lemma <cit.> which shows that one can embed N points in ^n into a m=O(δ^-2log N)-dimensional space and simultaneously preserve pairwise Euclidean distance up to δ-Lipschitz distortion. 
More recently, binary embeddings   have also attracted a lot of attention in the signal processing and machine learning communities (e.g., <cit.>), in part due to theoretical interest, and in part motivated by the potential benefits of further reductions in memory requirements and computational time. Roughly speaking, they are nonlinear embeddings that map high dimensional signals into a discrete cube in lower-dimensional space. As each signal is now represented by a short binary code, the memory needed for storing the entire data set is reduced considerably, as is the cost of computation.


To be more precise, let 𝒯 be a set of vectors in ^n and let {-1, 1}^m be the binary cube. Given a distance d_ on , an α-binary embedding of  is a map f: →{-1, 1}^m with an associated function d on {-1, 1}^m so that 

    |d(f(x), f(x̃)) - d_(x, x̃)| ≤α,     for all  x, x̃∈.

Recent works have shown that there exist such α-binary embeddings <cit.>. For  a finite set of N points in the unit sphere S^n-1, endowed with the angular distance d_(x, x̃) = arccos(x_2^-1x̃_2^-1x, x̃), these works consider the  map

    f_A(x) = (Ax),

where A is an m× n matrix whose entries are independent standard Gaussian random variables. Then with probability exceeding 1 - η, f_A is an α-binary embedding for  into {-1, 1}^m associated with the normalized Hamming distance d_H(q, q̃) = 1/2m∑_i|q_i - q̃_i|, provided that m≳α^-2log(N/η). 

While achieving the optimal bit complexity for Hamming distances as shown in <cit.>, the above binary embeddings rely on A being Gaussian. In general, they suffer from the following drawbacks.


   Drawback (i): To execute an embedding, one must incur a memory cost  of order mn to store A, and must also incur the full computational cost of dense matrix-vector multiplication each time a point is embedded. 

   Drawback (ii): The embedding completely loses all magnitude information associated with the original points. That is, all points c x ∈^n with c > 0 embed to the same image. 

To address the first point above, researchers have tried to design other binary embeddings which can be implemented more efficiently. For example, such embeddings include circulant binary embedding <cit.>, structured hashed projections <cit.>, binary embeddings based on Walsh-Hadamard matrices and partial Gaussian Toeplitz matrices with random column flips <cit.>. To our knowledge, all of these results do not address the second point above; they use the sign function (<ref>) (which is an instance of Memoryless Scalar Quantization) to quantize the measurements. While  simple, this quantization method cannot yield much better distance preservation when we have more measurements, i.e., when m increases, as discussed in Section <ref>. 


   Drawback (iii): At best, the approximation error associated with the embedding distance decays slowly as  m, the embedding dimension (and number of bits) increases.

We resolve these issues in this paper. 





 §.§ Notation

A vector is k-sparse if it has at most k nonzero entries, i.e., it belongs to the set 
    := { z∈^n, |(z)| ≤ k}.
 Roughly speaking, a compressible vector x is one that is close to a k-sparse vector. More precisely, we can use the best k-term approximation error of x in ℓ_1, denoted by σ_k(x)_1 := min_v∈x - v_1, to measure how close x is to being k-sparse. We use the notation B_2^n and B_1^n to refer to the unit Euclidean ball and the unit ℓ_1 ball in ^n, respectively. In what follows A ≲ B means that there is a universal constant c such that A ≤ cB, and ≳ is defined analogously. 
We use the notation _g to indicate expectation taken with respect to the random variable g (i.e., conditional on all other random variables). The operator norm of a matrix A, A_p→ q, is defined as A_p→ q := max_x_p=1Ax_q, though we may simply use A in place of A_2→ 2.




 §.§ Roadmap


 The rest of the paper is organized as follows.  In Section <ref> we highlight the main contributions of the paper, and in Section <ref> we review some necessary technical definitions and tools from compressed sensing, embedding theory, and probability. Section <ref> is dedicated to a review of quantization theory, and in particular the noise-shaping techniques that are instrumental to our results. Sections <ref> and <ref> are dedicated to our main theorems and proofs on binary embeddings and quantized compressed sensing. Section <ref> provides a proof of a critical technical result, namely that certain matrices associated with our methods satisfy a restricted isometry property. Finally Section <ref> provides proofs of some technical lemmas that we require along the way.





























§ CONTRIBUTIONS

Below, we describe our main results as they pertain to binary embeddings and quantized compressed sensing, and we summarize the main technical contribution that allows us to obtain our results. To that end, let D_ϵ be an n× n diagonal matrix with random signs, Φ an m× n  matrix as in Construction <ref>,  be a noise-shaping quantizer, i.e., either _ΣΔ a ΣΔ quantization or _β a distributed noise-shaping quantization (as in Sections <ref> and <ref>). Let V be the associated linear operator defined in (<ref>) below and V = (9/8)V. 







 §.§ Contributions related to binary embeddings

 








Let 𝒯⊂^n be a subset of the unit ℓ_1-ball. In Algorithm <ref> we construct quasi-isometric (i.e., distance preserving) embeddings between  (𝒯, ·_2) and the binary  cube {-1,+1}^m endowed with the pseudometric

    d_V(q̃,q) := V(q̃ -q) _2.




As they rely on Construction <ref> our embeddings f: 𝒯→{± 1}^m  support fast computation, and despite their highly quantized non-linear nature, they perform as well as linear Johnson-Lindenstrauss methods up to an additive error that decays exponentially (or polynomially) in m. 

When 𝒯 is finite we show that with high probability 
and for prescribed distortion α

    m ≳log(|𝒯|)log^4 n/α^2    |d_V(f(x), f(x̃)) - x - x̃_2|    ≤αx - x̃_2 + cη(m), 
         where η(m)  0.

Above, η(m) decays polynomially fast in m (when 𝒬 is a ΣΔ quantizer), or exponentially fast (when 𝒬 is a distributed noise shaping quantizer). In fact, we prove a more general version of the above result, which applies to infinite sets 𝒯. 

When 𝒯 is arbitrary (possibly infinite) we show that with high probability  and for prescribed distortion α

    m ≳log^4 n/α^2·ω(𝒯)^2/(𝒯)^2    |d_V(f(x), f(x̃)) - x - x̃_2| ≤max(√(α),α) (𝒯)+ cη(m)

where η(m) is as before and where ω(𝒯) and (𝒯) denote the Gaussian width and Euclidean radius of  𝒯, defined in Section <ref>.

We remark that our results are even more general in the sense that we can embed into any finite set 𝒜^m, where 𝒜 is the quantization alphabet used by the noise-shaping quantization scheme (see Section <ref> for details). In particular, this means that one may choose an alphabet 𝒜 that contains more than two elements and obtain improved constants in the additive part (i.e., cη(m)) of our error bounds. Thus, in effect our results amount to fast quantized Johnson-Lindenstrauss embeddings.

























 
 
 

 §.§ Contributions related to the quantization of compressed sensing measurements arising from random structured matrices

  

 
 We provide the first non-trivial quantization results, with optimal (linear) dependence on sparsity, in the setting of compressed sensing with bounded orthonormal systems. Our results also apply to partial circulant ensembles and our approach is summarized in Algorithm <ref>. 

 We show that noise-shaping quantization approaches, namely ΣΔ quantization (e.g., <cit.>) and distributed noise-shaping quantization <cit.> significantly outperform the naive (but commonly used) quantization approach, memoryless scalar quantization.  They yield polynomial and exponential error decay, respectively, as a function of the number of measurements. In contrast, the error decay of memoryless scalar quantization can be no better than linear <cit.>. 

Noise shaping quantization techniques produce vectors q whose entries belong to a finite set. Equally importantly,  q is related to the vector of measurements y=Ax via a noise-shaping relation of the form 

    y - q = H u,

where H is a so-called noise shaping operator and u is a vector with bounded entries. 

Recalling that in compressed sensing, one wishes to recover the (approximately) sparse vector x, our reconstruction approach is to solve the optimization problem 

    min_z z_1     subject to   VΦ z-Vq _2 ≤η.

Above, we choose the matrix V and we set the scalar η depending on the quantization scheme. As a result we can show that 

    m ≳ k log^4 n      x -  x̂_2 ≲η(m) +  σ_k(x)_1/√(k)

with high probability, for all x∈^n. Above, the estimate x̂ is produced by Algorithm <ref> and as before η(m) decays polynomially fast in m (when 𝒬 is a ΣΔ quantizer), or exponentially fast (when 𝒬 is a distributed noise shaping quantizer). 



 §.§ Technical considerations

The choice of V is critical to the success of our reconstruction, as we require VΦ to satisfy a restricted isometry property <cit.>, see Section <ref>. Once VΦ satisfies this property, the reconstruction step of Algorithm <ref> yields an estimate x̂ with x̂-x_2 ≤ Cη by standard compressed sensing results (see, e.g. <cit.>). Thus, the main technical challenge is to construct V in such a way that VΦ satisfies the restricted isometry property. This is non-trivial due to the dependencies implicit in the random model which generates bounded orthonormal systems and partial circulant matrices. Simultaneously, the scalar η that we choose must be small enough to yield the desired polynomial or exponential decay rates in the number of measurements m. The choice of V that achieves our goals is 

    V = 1/v_2 √(p) (I_p ⊗ v),

where v = (v_1, …, v_λ)∈^λ depends on the quantization scheme  (v is given explicitly in Sections <ref> and <ref>), I_p is the p× p identity matrix and λ p = m. Here, ⊗ denotes the Kronecker product. We show that with high probability, for matrices Φ drawn according to Construction <ref>  


    m ≳k log^4 n/α^2    sup_x ∈ T_k|  VΦ x_2^2 - x_2^2| ≤α,


where T_k denotes the set of k-sparse signals on the unit sphere. That is, we show that VΦ has the restricted isometry property. This restricted isometry property is also crucial for our results on binary embeddings. 



















































§ DEFINITIONS AND TOOLS




 §.§ The restricted isometry property and its implications

We now recall the restricted isometry property of matrices along with some of its implications to compressed sensing, as well as theorems showing that BOEs and PCEs satisfy it with high probability if m≳ k polylogn.

We say that a matrix A∈^m× n satisfies the (δ_k,k)-RIP if for every x∈Σ_k^n, we have 

    (1-δ_k)^2x^2≤Ax _2^2 ≤ (1+δ_k)^2x^2.



It is by now well-known that, if a matrix A satisfies (δ_k, k)-RIP with an appropriate small constant δ_k, ℓ_1-minimization is robust. We present one such result as a representative.


Suppose that the matrix A∈^m× n satisfies the (δ_2k,k)-RIP with δ_2k(A) < 4/√(41). Then for any x∈^n and b∈^m with A x - b_2 ≤η, a solution x^# of 

    min_z∈^nz_1 A z - b_2 ≤η

approximates the vector x with 

    x - x^#_2    ≤ Cη + D/√(k)σ_k(x)_1,

where the constants C, D > 0 depend only on δ_2k.


Indeed several ensembles of random matrices satisfy the RIP and in this paper we are particularly interested in bounded orthonormal ensembles and partial circulant matrices for which we recall the following results. 


Let A∈^m× n be drawn from the bounded orthogonal ensemble. Fix α∈ (0,1). Then there exists a universal constant C >0 such that

    sup_x∈ T_k| 1/mAx_2^2 - x_2^2 | ≤α,

provided m/log(9m)≥ Cklog^2(4k)log(8n)/α^2.



Let A∈^m× n be drawn from the partial circulant ensemble associated with an index set Ω of size m. Fix α∈ (0, 1). Then there exists a universal constant C > 0 such that

    sup_x∈ T_k| 1/mAx_2^2 - x_2^2 | ≤α,

provided m ≥ Cklog^2(k)log^2(n)/α^2.




 §.§ Embedding tools

We begin with some useful definitions of  quasi-isometric embeddings, and of Gaussian widths of sets.


A function f: 𝒳→𝒴 is called a quasi-isometry between metric spaces (𝒳, d_𝒳) and (𝒴, d_𝒴) if there exist C > 0 and D ≥ 0 such that

    1/Cd_(x, x̃) - D ≤ d_𝒴(f(x), f(x̃)) ≤ Cd_(x,x̃) + D

for all x, x̃∈.

 We will relax the above definition by only requiring that d_𝒴 be a pseudo-metric, so we require d_𝒴(x,y)=d_𝒴(y,x) and we require d_𝒴 to respect the triangle inequality, but we allow d_𝒴(x,y)=0 for x≠ y. 



 Let 𝒞 = {-1,1}^m be a discrete cube in ^m and let V∈^p× m with p≤ m. We define a pseudo-metric d_V on 𝒞 by 
    d_V(q, q̃) = V(q - q̃)_2.
 




For a set 𝒯⊂^n, the Gaussian mean width ω(𝒯) is defined by

    ω(𝒯) := [sup_v∈𝒯⟨ v, g⟩]

where g is a standard Gaussian random vector in ^n. Moreover, 
    (𝒯) = sup_v∈𝒯v_2
 is the maximum Euclidean norm of a vector in 𝒯.


Krahmer and Ward <cit.> showed that matrices satisfying the RIP can be used to create Johnson-Lindenstrauss, i.e., near-isometric, embeddings of finite sets. 

Fix ν > 0 and α∈ (0, 1). Consider a finite set ⊂^n. Set k ≥ 40(log(40||) + ν), and suppose that Ψ∈^p× n satisfies (α/4, k)-RIP. Let D_ϵ∈^n× n be a random sign diagonal matrix. Then, with probability exceeding 1 - e^-ν, the matrix Ψ D_ϵ satisfies

    |Ψ D_ϵ  x_2^2 - x_2^2| ≤αx_2^2

simultaneously for all x∈.



We will need the following “multiresolution” version of the restricted isometry property, used by Oymak et. al in <cit.> to prove embedding results for arbitrary, i.e., not necessarily finite, sets.

Let L = ⌈log_2 n⌉. Given δ > 0 and a number s ≥ 1, for ℓ = 0, 1, …, L, let (δ_ℓ, s_ℓ) = (2^ℓ/2δ, 2^ℓ s) be a sequence of distortion and sparsity levels. We say a matrix A∈^m× n satisfies the Multiresolution Restricted Isometry Property (MRIP) with distortion δ > 0 at sparsity s, if for all ℓ∈{1, 2, …, L}, (δ_ℓ, s_ℓ)-RIP holds.





Let 𝒯⊂^n and suppose the matrix Ψ∈^m× n obeys the Multiresolution RIP with sparsity and distortion levels 

    s = 150(1 + η)   and  α̃ = α·()/Cmax{(𝒯), ω(𝒯)},

with C > 0 an absolute constant. Then, for a diagonal matrix D_ϵ with an i.i.d. random sign pattern on the diagonal, the matrix A = Ψ D_ϵ obeys

    sup_x∈𝒯|Ax_2^2 - x_2^2| ≤max{α, α^2}((𝒯))^2,

with probability at least 1 - e^-η.





 §.§ Tools from probability

We start with a definition of the γ_2 functional, followed by a result by Krahmer et al. <cit.> that will be very useful in proving our technical results.
 

For a metric space (T,d), an admissible sequence of T is a collection of subsets of T, {T_r:r≥ 0}, such that for every s≥ 1, |T_r|≤ 2^2^r and |T_0|=1. For β≥1, the γ_β functional is given by the following infimum, taken over all admissible sequences of T:

    γ_β(T, d) = infsup_t∈ T∑_r = 0^∞ 2^r/β d(t, T_r).
  




 Let ℳ⊂ℂ^p× n be a symmetric set of matrices, i.e., ℳ = -ℳ. Let ϵ be a ± 1 Bernoulli vector of length n. Then

    sup_M∈ℳ| Mϵ_2^2 - Mϵ_2^2 | ≲ d_F(ℳ)γ_2(ℳ, ·_2→ 2) + γ_2(ℳ, ·_2→ 2)^2,

where d_F(ℳ) = sup_M∈ℳM_F and γ_2(·) is as in Definition <ref>.


Next we present a version of Bernstein's inequality that we will use in proving that our matrix VΦ satisfies an appropriate RIP with high probability.


Let ℱ be a countable set of functions F:^n →. Let Y_1, …, Y_M be independent random vectors in ^n such that F(Y_ℓ) = 0 and F(Y_ℓ) ≤ K almost surely for all ℓ∈ [M] and for all F ∈ℱ with some constant K > 0. Introduce 
    Z = sup_F∈ℱ∑_ℓ = 1^M F(Y_ℓ).

Let σ_ℓ^2 > 0 such that [F(Y_ℓ)^2] ≤σ_ℓ^2 for all F∈ℱ and ℓ∈[M]. Then, for all t > 0,

    (Z ≥ Z + t) ≤exp(-t^2/2/σ^2 + 2K Z + tK/3),

where σ^2 = ∑_ℓ = 1^Mσ_ℓ^2.






§ QUANTIZATION: BACKGROUND AND PRELIMINARIES





As previously mentioned, various choices of quantization maps and reconstruction algorithms have been proposed in the context of binary embedding and compressed sensing. 
Below, we first review the lower bounds associated with optimal (albeit highly impractical) quantization and decoding, which no scheme can outperform. We then review the basics of memoryless scalar quantization as well as noise shaping quantization, as we will need these for our results. 



 §.§ Optimal error bounds via vector quantization











For a class 𝒳 of signals (e.g., 𝒳 = Σ_k^n), the performance of a practical data acquisition scheme consisting of three stages (i.e., measurement, quantization, and reconstruction) can be measured against the optimal error bounds. Specifically, the performance of any such a scheme can be measured by the tradeoff between the number of bits (rate) and reconstruction error (distortion) and we now describe how to examine the optimal rate-distortion relationship. Given a desired worst-case  approximation error ϵ, measured in the ℓ_2 norm,  we can cover the class 𝒳 with balls of radius ϵ associated with the Euclidean norm ·_2. The smallest number of such ϵ-balls is called the covering number of 𝒳 and denoted by 𝒩(𝒳, ·_2, ϵ). An optimal scheme consists of  encoding each signal x in the class 𝒳 using R := log_2𝒩(𝒳, ·_2, ϵ) bits by mapping x to the center of an ϵ-ball in which it lies. A simple volume argument yields the optimal lower bound of the approximation error in term of the rate (see, e.g. <cit.>) which, when 𝒳=Σ_k^n, satisfies 
    ϵ(R) ≳n/k 2^-R/k.




On the other hand, the distortion of a three-stage scheme comprised of measurements using a matrix A, quantization via the map 𝒬, and reconstruction using an algorithm ℛ is defined by 
    𝒟(A,, ℛ) := sup_x∈𝒳x - ℛ((Ax))_2.
 
Thus, trivially, 

    𝒟(A, , ℛ)≳n/k2^-R/k,

and one seeks practical[Note that the optimal scheme described herein is impractical as it requires direct measurements of x which may not be available, and it requires finding the ball to which x belongs. As the number of such balls scales exponentially with the ambient dimension, this task becomes prohibitively expensive.] schemes that approach this lower bound.

In the case of Gaussian (and subgaussian) matrices A, there exist schemes <cit.> that approach the optimal error bounds, albeit with various tradeoffs. Among these, the results in <cit.> apply only to Gaussian random matrices A, while those of 
 <cit.> and <cit.> rely on noise-shaping quantization techniques and apply to a more general class of subgaussians. In the quantization direction, our work extends the noise-shaping results of  <cit.> and <cit.> to the case of structured random matrices which are selected according to Construction <ref>. Before describing the necessary technical details pertaining to noise-shaping we quickly describe the most basic  (but highly suboptimal) approach to quantization, i.e., memoryless scalar quantization, as the most widely assumed approaches to binary embeddings and quantization of compressed sensing measurements use it.




 §.§ Memoryless Scalar Quantization

The most intuitive approach to quantize linear measurements y = Ax is the so-called memoryless scalar quantization (MSQ) in which the quantization map _MSQ is defined by

    q_i := (_MSQ( y))_i := min_r∈|y_i - r|.

In other words, we round each measurement y_i to the nearest element in the quantization alphabet . For instance, in the case of binary embedding, i.e., = {-1, 1}, (_MSQ(y))_i = (y_i). Here (t) = 1 if t ≥ 0 and -1 otherwise. 

If the quantization alphabet = δ for some step size δ > 0 is to be used, we can bound  y - q_2 ≤1/2δ√(m). Thus, in the setting of binary embedding, MSQ defines a quasi-isometric embedding

    (1 - α)v - w_2 - δ≤1/√(m)(Av) - (Aw)_2 ≤ (1 + α)v - w_2 + δ

with high probability if A is a Gaussian random matrix <cit.>.
On the other hand, if we consider the quantization problem in compressed sensing, the robust recovery result (<ref>) guarantees that

    x - x̂_MSQ_ 2 ≲δ

when x is a k-sparse vector.

In spite of its simplicity, MSQ is not optimal when one oversamples, i.e., one has more measurements than needed. In particular, the error bounds (<ref>) and (<ref>) do not improve with increasing the number of measurements m. This is due to the fact that MSQ ignores correlations between measurements as it acts component-wise. While one can in principle still get a reduction in the error by  using a finer quantization alphabet (i.e., a smaller δ), this is often not feasible in practice because the quantization alphabet is fixed once the hardware is built, or not desirable as one may prefer a simple, e.g., 1-bit embedding.  In order to address this problem, noise-shaping quantization methods, such as Sigma-Delta (ΣΔ) modulation and alternative decoding methods (see, e.g., <cit.>), have been proposed in the settings of quantization of bandlimited functions, finite frame expansions, and compressed sensing measurements. However, these methods have not been studied in the framework of binary embedding problems. As stated before, the main contributions of our work are to extend noise-shaping approaches to embedding problems and to compressed sensing with structured random matrices.



 §.§ Noise-shaping quantization methods

Noise-shaping quantizers, for example ΣΔ modulation, were first proposed for analog-to-digital conversion of bandlimited functions (see, e.g., <cit.>). Their success is essentially due to the fact they push the quantization error toward the nullspace of their associated reconstruction operators. These methods have been successfully extended to the frameworks of finite frames (see, e.g., the survey <cit.> and  <cit.>) and compressed sensing 

(see, e.g. <cit.>). In fact, the approaches based on ΣΔ quantization  <cit.> and beta encoders <cit.> achieve near-optimal bounds for sub-Gaussian measurements. 



To explain these methods, consider a real quantization alphabet _L, δ consisting of 2L symmetric levels of spacing 2δ, i.e., 
    _L, δ := {aδ |  a = -2L + 1, …, -1, 1, …, 2L - 1},
 and let := _L, δ + i_L, δ be a complex quantization alphabet. 
We  mention the complex case here for the sake of completeness and remark that all our results apply in the complex setting, but after this discussion we will restrict our attention to real valued matrices and vectors.
 
A noise-shaping quantizer :^m→^m, associated with the so-called noise transfer operator H, is defined such that for each y∈^m the resulting quantization q := (y) satisfies the noise-shaping relation

    y - q = Hu,

where u∈^m is called the state vector and u_∞≤ C for some constant C independent of m. Here, H is an m× m lower triangular Toeplitz matrix with unit diagonal. Noise-shaping quantizers do not exist unconditionally because of the requirement that u_∞ is uniformly bounded in m. However, under certain suitable assumptions on H and , they exist and can be simply implemented via recursive algorithms <cit.>. For example, the following lemma provides conditions under which the schemes are stable.

Let := _L, δ +i_L, δ. Assume that H = I - H where H is strictly lower triangular, and μ≥ 0 such that  
    H_∞→∞ + μ/δ≤ 2L.
 Suppose that |y_j|_* := max{|(y_j)|, |(y_j)|}≤μ for all j∈[m]. For each s ≥ 1, let w_s := y_s + ∑_j = 1^s - 1H_s, s - ju_s - j,

    q_s := ((y))_s = min _r∈|w_s - r|_*,

and

    u_s := w_s - q_s.

Then the resulting q satisfies the noise shaping relation (<ref>) with u_∞≤√(2)δ. In the case of strictly real y, the √(2) factor can be replaced by 1. 

The proof of the above is simply by induction and can be found, for example,  in <cit.>.


Our algorithm are inspired by the approach to reconstruction from noise-shaping quantized measurements used in <cit.> and <cit.> (see also <cit.>). We first introduce a so-called condensation operator V: ^m →^p, for some p ∈ [m], defined by

    V:= I_p⊗ v = [ v    ;   v  ;     ⋱;       v ],

where v is a row vector in ^λ. Here, for simplicity, we suppose that λ = m/p is an integer.

In this approach, to embed or recover the signal x, we first apply V to the noise-shaping relation (<ref>) and obtain

    VΦ x - Vq = VHu.

Our goal is to design a p× m matrix V and an m× m matrix H such that the norm VHu_2 is exponentially (or polynomially depending on the quantization scheme) small in m and our quantization algorithm is stable. This in turn helps us achieve exponentially and polynomially small errors in the settings of binary embedding and compressed sensing. We now present two candidates for the pair (V, H) based on ΣΔ quantization and distributed noise shaping.












 §.§ Sigma-Delta quantization

The standard rth-order ΣΔ quantizer with input y computes a uniformly bounded solution u to the difference equation

    y - q = D^r u.

This can be achieved recursively by choosing q := _ΣΔ(y) and u as in the expressions (<ref>) and (<ref>), respectively, for the matrix H = D^r. Here the matrix D is the m× m first-order difference matrix with entries given by

    D_ij = {[              1     if  i = j,;             -1 if  i = j + 1,;              0     otherwise. ].





Constructing stable ΣΔ schemes of arbitrary order r, i.e., where 
    y_∞≤μu_∞≤ c(r)
 with a constant c(r) that is independent of dimensions (but dependent on the order) is non-trivial for a fixed quantization alphabet. Nevertheless, there exist several constructions (see <cit.>) with exactly this boundedness property, albeit with different constants c(r). For our results herein, when we assume a fixed alphabet, we use the stable ΣΔ schemes of <cit.>. The relevant result for us is the following proposition from <cit.> summarizing the results of <cit.>[In the relevant proposition of <cit.>, there is a typo (in equation (12)) as there is a missing r^r factor. This can be seen from comparing their equations (11) and (12). We remedy this in the version presented here.]. 

(<cit.>, see <cit.> Proposition 1)
There exists a universal constant C>0 such that for any alphabet ={± (2ℓ-1)δ:  1 ≤ℓ≤ L,  ℓ∈}, there is a stable ΣΔ scheme such that 

    y_∞≤μu_∞≤ Cδ( ⌈π^2/(cosh^-1(2L-μ/δ))^2⌉e/π· r   )^r.


In particular, this guarantees that even with the 1-bit alphabet, i.e.,  𝒜={± 1} and δ=1, as assumed in binary embeddings, stability can be guaranteed as long as y_∞≤μ < 1 with a corresponding bound 

    y_∞≤μ < 1 u_∞≤ C · c(μ)^r · r^r.


Previous works (e.g., <cit.>) using ΣΔ schemes in compressed sensing achieve a polynomially small error bound (in m). However, these approaches assume gaussian or subgaussian random matrices and the proof techniques are not easily extended to the case of structured random matrices. This is in part due to the role that D^-r, applied to Φ, plays in the associated proofs; one essentially requires D^-rΦ to have a restricted isometry property. Due to the dependencies among the rows of Φ in the case of BOEs and PCEs, such a property  is difficult to prove. Nevertheless, in <cit.>, the authors were first to study PCEs and prove  error bounds that decay polynomially in m. The approach proposed in <cit.> uses a different sampling scheme to generate the PCE, a different reconstruction method (whose complexity scales polynomially in m, versus p in our case), and requires a different proof technique. 

To circumvent the above issue, and generate the first results for BOEs,  we will need the following condensation operator. Let 
    λ:= m/p=: rλ̃ - r + 1
 for some integer λ̃.

Let v be a row vector in ^λ whose entry v_j is the jth coefficient of the polynomal (1 + z + … + z^λ̃- 1)^r. Define the ΣΔ condensation operator V_ΣΔ:^m →^p by

    V_ΣΔ= I_p⊗ v = [ v    ;   v  ;     ⋱;       v ],

	and define its normalized versions



    V_ΣΔ = 9/8 v_2√(p)V_ΣΔ,
 
and 

    V_ΣΔ = 1/v_2√(p)V_ΣΔ.
 



In the case r=1, we have v=(1,...,1)∈^λ, while when r=2, v=(1,  2,  ,  λ̃-1,  λ̃,  λ̃-1, ,  2,  1)∈^λ.

 For a stable rth order ΣΔ quantization scheme  we have


    VD^r_∞→ 2≤ (8r)^r+1λ^-r + 1/2.



The proof of Lemma <ref> is given in Section <ref>. 





 §.§ Distributed noise shaping

In <cit.>, Chou and Güntürk achieved an exponentially small error bound in the quantization  of unstructured random (e.g., Gaussian) finite frame expansions by using a so-called distributed noise-shaping approach. Our work in this paper  extends this approach handle the practically important cases of compressed sensing and binary embeddings, both with structured random matrices drawn from a BOE or a PCE. To that end, we now review distributed noise-shaping. 

Fixing β > 1, let H_β be a λ×λ noise transfer operator given by 

    (H_β)_ij = {[              1     if  i = j,;             -β if  i = j + 1,;              0     otherwise. ].


Moreover, let H:^m→^m be the block-diagonal distributed noise-shaping transfer operator given by

    H = I_p⊗ H_β = [ H_β        ;     H_β    ;           ⋱;             H_β ]

In analogy with Definition <ref> we now introduce the distributed noise-shaping condensation operator.


Define the row vector 
    v_β :=  [β^-1 β^-2  …  β^-λ]
 and  define the distributed noise-shaping condensation operator V_β:^m →^p by

    V_β= I_p⊗ v_β = [ v_β        ;     v_β    ;           ⋱;             v_β ].

	Define its normalized versions


    V_β = 9/8v_β_2√(p)V_β,

and

    V_β = 1/v_β_2√(p)V_β.



Notice that in this setting, 
    V_β H = I_p⊗ (v_β H_β)
 and consequently




    V_β H_∞→∞ = β^-λV_β H_∞→ 2≤9β^-λ/8v_β_2≤9β^-λ + 1/8


since v_β H_β = [0  0…β^-λ] and v_β_2 ≥β^-1. 






§ MAIN RESULTS ON BINARY EMBEDDINGS
 
We are now ready to present our main results on binary (and more general) embeddings, showing that Algorithm <ref> yields quasi-isometric embeddings that preserve Euclidean distances. We start with the case of finite sets, and we then present an analysis of our methods for infinite sets.  




















































 
Consider a finite set 
⊂ B_1^n.
Fix α∈ (0, 1)  and ρ∈(0,1). 
Let Φ∈^m× n, D_ϵ∈^n× n, V∈^p× m be as in Algorithm <ref> and suppose λ = m/p is an integer. Define Φ = 8/9Φ and let : ^m →{± 1}^m, be the stable quantization scheme  corresponding either to the rth order ΣΔ quantization or to the distributed noise shaping quantization with β∈(1, 10/9], that is used in Algorithm <ref>. 

Fix ν > 0, and define the embedding map f:→{± 1}^m by f = ∘Φ∘ D_ϵ. Assume that k ≥ 40(log(8||) + ν). Then there exist constants, C_1>0 and C_2 > 0,  that depend on the quantization such that if


    m ≥ p ≥ C_1 klog^4 n/α^2ρ^2,

the map f satisfies

    |d_V(f(x), f(x̃)) - x - x̃_2| ≤αx - x̃_2 + C_2η(λ),   ∀ x,x̃∈

with probability exceeding 1-ρ - e^-ν. 
Here, η(λ) = λ^-r + 1/2 
if we use the ΣΔ quantization scheme and η(λ)= β^-λ+1 
if we use the distributed noise-shaping scheme.














The proof follows from Theorem <ref> and our main technical result, Theorem <ref>, respectively showing that RIP matrices with randomized column signs provide Johnson-Lindenstrauss embeddings, and that the matrices VΦ satisfy the appropriate RIP. The proof also requires bounds on VH_∞→ 2 to obtain the advertised decay rates. Indeed, 

 we have

    |d_V(f(x), f(x̃)) - x - x̃_2| ≤|d_V(f(x), f(x̃))     - VΦ D_ϵ  (x - x̃)_2| 
       + | VΦ D_ϵ  (x - x̃)_2 - x - x̃_2|

so we must bound the two summands on the right to obtain our result and we start with the second term. 

By (<ref>) in  Theorem <ref>, with αρ in place of α, and Markov's inequality, for any ρ∈(0,1), VΦ satisfies (α, k)-RIP with probability exceeding 1-ρ, provided that p ≥ C_1klog^4 n/(ρ^2α^2) for some constant C_1 > 0. Hence by Theorem <ref>, with probability at least 1-ρ - e^-ν, the matrix VΦ D_ϵ satisfies

    |VΦ D_ϵ (x - x̃)_2^2 - x - x̃_2^2| ≤αx - x̃_2^2,

which yields

    |VΦ D_ϵ (x - x̃)_2 - x - x̃_2| ≤αx - x̃_2

simultaneously for all x, x̃∈. 
To bound the first summand in (<ref>), note that in the case of ΣΔ quantization, for any z∈𝒯, (<ref>) implies that 


    Vf(z) - VΦ D_ϵ  z_2 = VD^r u_z_2 ≤VD^r  _∞→ 2u_z _∞≤   C_1 c_2(μ)^r r^2rλ^-r + 1/2,

where u_z is the resulting state vector of z as in (<ref>).

To obtain the last inequality above,  use Lemma  <ref> to bound  VD^r _∞→ 2; additionally, 
since all the entries of the matrix Φ are uniformly bounded by 1 and z_1 ≤ 1, we obtain Φ D_ϵ z_∞ = (8/9) Φ D_ϵ z_∞≤ 8/9 that allows us to invoke the stability bound (<ref>) to control u_z_∞. 
Consequently by the triangle inequality we have




    | V(f(x)-f(x̃))_2 -VΦ D_ϵ  (x-x̃)_2 | ≤ 2C_1 c_2(μ)^r r^2rλ^-r + 1/2,

which yields the desired result for ΣΔ quantization when combined with (<ref>), and (<ref>).
The exact same technique yields the advertised bound for distributed noise shaping, albeit we now use (<ref>) in place of Lemma <ref>.




















 (Extension to the ℓ_2 ball) 
Theorem <ref> can be  modified to apply to finite subsets of the unit Euclidean ball instead of the ℓ_1 ball.  Indeed, under the condition (<ref>) and the considered event in Theorem <ref>, the matrix 1/√(m)Φ satisfies the (α, k)-RIP   by Theorems <ref> and <ref>. This implies 1/√(m)Φ D_ϵ z_2 ≤√(1 + α)z_2 ≤√(1 + α) for all z∈ by Theorem <ref>. Hence, Φ D_ϵ z_∞≤√(1 + α)√(m). So scaling the quantization alphabet carefully, e.g., considering {±√((1+α)m)} in place of {± 1}, ensures our quantization schemes are stable with stability constant √((1+α)m) for all z∈. This yields the same error bound up to the transformation η(λ) ↦√((1+α)m) η(λ). The price of this extension is that for the new η(λ) to be small (e.g., less than one) and decreasing with m one would require m ≳ p^r-1/2/r-1 in the case of ΣΔ quantization and m≳ plogm in the case of distributed noise shaping.  This extension is also applicable to Theorem <ref> below by using Theorem <ref> in place of Theorem <ref>. 

Alternatively, in the case of a finite subset ⊂ B_2^n, to avoid the lower bound on m   one can use Bernstein's inequality and a union bound over the m rows of Φ followed by a union bound over all x∈𝒯 (instead of invoking the restricted isometry property and Theorem <ref>). This would yield the bound Φ D_ϵ x_∞<clog n for all x∈𝒯, with high probability, provided || is at most polynomial in n. In turn, scaling the alphabet by clog n would imply the same bound in Theorem <ref> up to the transformation η(λ) ↦ cη(λ)log n.




(The condition on β) Note that the condition β∈ (1,10/9] is just a byproduct of the convenient normalization of Φ that we chose, and the resulting bound on ΦD_ϵ_2→∞. Different normalizations would have allowed pushing β closer to 2. 













(Root-exponential error decay)
In the case of ΣΔ quantization, one can optimize the bound (<ref>) by selecting r as a function of λ. Choosing the ΣΔ scheme of order r^*, where r^* minimizes the function c_2(μ)^r r^2rλ^-r + 1/2 (see, e.g., <cit.> for a similar detailed calculation) yields a quantization error decay of exp(-c√(λ)) for some constant c so that

 
    |d_V(f(x), f(x̃)) - x - x̃_2| ≤αx - x̃_2 + C e^-c√(λ),   ∀ x,x̃∈.




(Optimizing the dimension p)
The parameter α in Theorem <ref> behaves essentially as 1/√(p), and  x-x̃_2 ≤ 2 for points in the unit ℓ_1 ball. So, one can consider choosing p to improve the bounds C( 1/√(p) + e^-c √(m/p) ) and C( 1/√(p) + β^- m/p+1) in the case of ΣΔ and distributed noise-shaping quantization respectively. Slightly sub-optimal but nevertheless good choices of p are then p_ΣΔ≈ m/log^2(m)
and p_dist.≈ m/log(m), where the ≈ notation hides constants. In turn this yields a quantized Johnson-Lindenstrauss error decay of the form logm/√(m) and √(log m/m) for the two schemes, respectively. 
In other words, quantizing the Johnson-Lindenstrauss Lemma only costs us a logarithmic factor in the embedding dimension.



(Embedding into 𝒜^m) It is easy to see from the proof that one could replace the cube {± 1}^m by the set 𝒜^m generated by the 2L level alphabet  in (<ref>) provided (2L-1)δ≥ 1. In turn, this simply reduces the constant C_2 in Theorem <ref> by a factor of L.

(Unstructured random matrices)
Note that the only requirement on Φ in the proof is that VΦ satisfies an appropriate restricted isometry property. It is not hard to see that matrices Φ with independent entries drawn from appropriately normalized Gaussian or subgaussian distributions yield such a property. Hence a version of our results holds for such matrices, and we leave the details to the interested reader. 


We now present our result on embedding arbitrary subsets of the unit ball, and comment that the contents of Remarks <ref>, <ref>, <ref>, and <ref> apply to the theorem below as well, with minor modification.




Consider the same setup as Theorem <ref> albeit now with any set ⊂ B_1^n.  
Let γ = v_1/v_2. Suppose that 

    m≥ p ≥ C_1γ^2(1 + ν)^2log^4 n max{1, ω^2( - )/(( - ))^2}/α^2.





Then, with probability at least 1 - e^-ν, the map f:𝒯→{-1, 1}^m given by f = ∘Φ∘ D_ϵ  ensures that

    |d_V(f(x), f(x̃)) - d_ℓ_2(x, x̃) | ≤max{√(α), α}( - ) + C_2η(λ),   for all  x, x̃∈.

Here η := λ^-r + 1/2 if we use a stable ΣΔ quantization scheme; and η := β^-λ + 1 if we use the distributed noise-shaping scheme.























Note that as in Theorem <ref>, our quantization scheme is stable since Φ D_ϵ z_∞≤ 8/9 for all z∈𝒯. To start, as in <cit.>, let L = ⌈log_2 n ⌉. Fix k and α, then by Theorem <ref> we have that for any level ℓ∈{0, 1, …, L} 

    (sup_x∈ T_2^ℓ k|VΦ x_2^2 - x_2^2| ≥ 2^ℓ/2α) ≤ e^-ν

if p ≳ k(log^4 n + γ^2 ν)/α^2.
Notice that by Theorem <ref>, coupled with a union bound applied to L levels and a change of variable ν↦ν + log L, we have that VΦ satisfies the Multiresolution RIP with sparsity k and distortion α > 0 with probability exceeding 1 - e^-ν whenever

    m ≥ p ≳k[log^4 n + γ^2(ν + log(L + 1))]/α^2.

Since log(L + 1) ≤log^4 n and log^4 n + ν≤ (1 + ν)log^4 n, we can achieve (<ref>) by setting

    m ≥ p ≳γ^2(1 + ν)klog^4 n/α^2.


Consequently, we may now apply Theorem <ref> (with VΦ in place of H) with 

    k = 150(1+ ν)   and  α̃ = α/Cmax(1, ω( - )/( - ))
  
to conclude that 

    sup_x∈-|VΦ D_ ϵ x_2^2 - x_2^2 | ≤max{α, α^2}((-))^2

with probability exceeding 1 - e^-ν. Indeed, this happens whenever

    m≥ p ≥ C_1γ^2(1 + ν)^2log^4 n max{1, ω^2(-)/((-))^2}/α^2.





















Conditioning on the events happening simultaneously, we have that for all x∈-

    | VΦ D_ϵ x_2/x_2 - 1 |^2 ≤| VΦ D_ϵ x_2^2/x_2^2 - 1 | ≤max{α, α^2}((-))^2/x_2^2.

This yields

    |VΦ D_ϵ x_2 - x_2 | ≤max{√(α), α}(-)   for all  x∈-.



Then for any w and v in , applying the quantization state equations (<ref>), we have (as in the proof of Theorem <ref>) and proceeding as in the proof of that theorem,

    |V(Φ D_ϵ w)  -  V(Φ D_ϵ v)_2 -    w - v_2  | 
       = |(VΦ D_ϵ w - VΦ D_ϵ v) - (VHu_w - VHu_v)_2 - w - v_2|
       ≤| VΦ D_ϵ (w - v)_2 - w - v_2| + |VH(u_w - u_v)|
       ≤max{√(α), α}( - ) + C_2η.











In distributed noise-shaping quantization, we can bound γ^2 ≤2β/β-1=:C_β if 1<β≤10/9, so we can set the condition (<ref>) as m≥ p ≥ C_β C_1(1 + ν)^2log^4(n) max{1, ω^2( - )/(( - ))^2}α^-2. In ΣΔ quantization, we can bound γ^2 ≤λ = m/p. Hence, the condition (<ref>) becomes m≥ p ≥ C_1√(m)log^2(n)max{1, ω( - )/(( - ))}α^-1. Note that this restriction on dimensions in the ΣΔ case, i.e., √(m)≲ p≤ m is not problematic as one should use p≈m/log(m)^2 as described in Remark <ref>, and this choice satisfies the restriction.








§ MAIN RESULTS ON COMPRESSED SENSING WITH BOE AND PCE: QUANTIZERS, DECODERS, AND ERROR BOUNDS

Herein, we present our results on the compressed sensing acquisition and reconstruction paradigm outlined in Algorithm <ref>. First, we cover the case when the acquired BOE or PCE measurements Φ x are quantized using a ΣΔ scheme, and we show polynomial error decay of the quantization error. Second, we present an analogous result with distributed noise shaping quantization, and we show exponential error decay of the quantization error as a function of the number of measurements.


Let k and p be in {1, …, m} such that the sampling ratio λ := m/p is an integer. Let Φ∈^m× n and V∈^p× m be as in Algorithm <ref>.
Denote by _ΣΔ^r a stable[e.g., ^r_ΣΔ can be either as in Proposition <ref> or as in Lemma <ref> with  2^r + 1/δ≤ 2L and H=D^r in the latter case.] rth-order scheme with the alphabet . For ν > 0, there exists an absolute constant c such that whenever


    m ≥ p ≥ cmax{klog^4 n, √(km ν)}

 the following holds with probability at least 1 - e^-ν on the draw of Φ.

Let x∈^n such that Φ x_∞≤μ <1 
and  q := _ΣΔ^r(Φ x), then the solution x to (<ref>) satisfies

    x - x_2 ≤ C_1 (m/p)^-r + 1/2δ + C_2σ_k(x)_1/√(k)

where C_1 and C_2 are explicit constants given in the proof.


The proof essentially boils down to finding an upper bound for VD^ru_2 which we do by controlling VD^r_∞→ 2 and u_∞ . Indeed, by Lemma <ref>

    VD^r_∞→ 2≤ (8r)^r+1λ^-r + 1/2.







































Moreover, since Φ x_∞≤μ <1, the quantization scheme is stable, i.e., u_∞≤ c δ, where c may depend on r. The noise-shaping relation (<ref>) implies that

    VΦ x - Vq_2 = VD^r u_2 ≤ (8r)^r+1λ^-r + 1/2u_∞≤  C_1(r)λ^-r + 1/2δ.

where in the case of noise shaping schemes as in Lemma <ref> we have C_1(r) = (8r)^r+1. 
On the other hand,  in the case of stable coarse schemes we have C_1(r)=(8r)^r+1 C(r), with C(r) being the r-dependent constant on the right hand side of the bound in Prop. <ref>.

We will now apply 
Theorem <ref> with γ^2:=v_1^2/v_2^2 ≤ m/p, as it is in the case of ΣΔ quantization. Thus we deduce that if p ≥ cmax{klog^4 n/α^2, √(km ν)/α}, VΦ satisfies (α, k)-RIP with probability at least 1 - e^-ν. Therefore, robustness of the convex program (<ref>) (see Theorem <ref>) implies that the solution, x, to (<ref>) satisfies

    x - x_2 ≤ C_1 (m/p)^-r + 1/2δ + C_2σ_k(x)_1/√(k).














































Fix  β∈(1 ,   2L- μ/δ)  and consider the same setup as Theorem <ref> albeit now with the distributed noise shaping quantization.




There exist positive constants c, C, and D such that whenever 

    m ≥ p ≥ ck(log^4(n) + ν)

 the following holds with probability at least 1 - e^-ν on the draw of Φ.


Let x∈^n such that Φ x_∞≤μ < 1. and let q := _β(Φ x) be its resulting distributed noise-shaping quantization as in Lemma <ref>, then the solution x to (<ref>) satisfies

    x -  x_2 ≤ Cβ^-m/p + 1δ + D σ_k(x)_1/√(k).





The proof is identical to the one of Theorem <ref>.
The noise-shaping relation (<ref>) implies that 

    VΦ x - Vq = VHu,

and Lemma <ref> yields u_∞≤δ.
Hence, using the first equality in (<ref>) we have

    VΦ x - Vq_2 = VHu_2 ≤√(p)VHu_∞≤√(p)VH_∞→∞u_∞≤δβ^-λ+ 1.





By Theorem <ref> with γ = v_1/v_2 ≤2β/β-1 and p ≥ ck(log^4(n) + ν)/α^2,
VΦ =VΦ/v_2√(p) satisfies (α, k)-RIP with probability 1 - e^-ν. This completes the proof by using the robustness of the convex program (<ref>) as before.



(Noise robustness)
We note that by modifying the reconstruction technique slightly, non-quantization noise can be handled in a robust way, in an analogous manner to the method in <cit.>. We leave the details to the interested reader. 




§ THE RESTRICTED ISOMETRY PROPERTY OF VΦ


Our main technical theorem shows that a scaled version of VΦ satisfies the restricted isometry property. Our proof of Theorem <ref> below is based on the technique of <cit.>, which in-turn relies heavily on <cit.>.
The rough architecture of the proof is as follows. We first show that the desired RIP property holds in expectation, then we leverage the expectation result and a generalized Bernstein bound to obtain the RIP property with high probability. The proof that the RIP holds in expectation in turn comprises several steps. A triangle inequality shows that the expected value of the RIP constant is bounded by the sum of the expected RIP constant of a BOS or PCE matrix and the expected supremum of a chaos process. To bound the chaos process, we use Theorem <ref> which requires controlling a Dudley integral and hence certain covering numbers. Here again, we use a technique adapted from the works of Nelson et al. <cit.>, and Rudelson and Vershynin <cit.>.

 
Fix α∈(0, 1) and ν > 0. Let k and p be in {1, …, m} with  λ := m/p  an integer. Let 

    V :=  I_p⊗ v  and V := 1/v_2√(p)V

 for a row vector v∈^λ, and let Φ be as in Construction <ref>.  Then there exist universal constants C_1 and C_2 that may depend on the distribution of Φ but not the dimensions, such that if 
    m ≥ p ≥ C_1klog^4 n/α^2,
 we have

    sup_x ∈ T_k|  VΦ x_2^2 - x_2^2| ≤α;




and if 

    m ≥ p ≥ C_2kmax{log^4 n/α^2, γ^2 ν/α^2}  or   m ≥ p ≥ C_2k(log^4 n + γ^2ν)/α^2,
 
we have


    ℙ(	sup_x ∈ T_k|  VΦ x_2^2 - x_2^2| ≤α) ≥ 1-e^-ν.

Here, γ := v_1/v_2.



We begin with the bound on the expectation.

Step (I): Let S_ℓ = {(ℓ - 1)λ + 1, …, ℓλ} for ℓ = 1, …, p. Let Λ be a diagonal matrix having the random signs ϵ_j from Step 2 of Construction <ref> as its diagonal entries and let a_j be the jth row of A. Then 

    VΦ x = VΛ Ax = VΛ[ a_1, x;      ⋮; a_m, x ]
    = V[ ϵ_1a_1, x;         ⋮; ϵ_ma_m, x ]
    
    = [        ∑_j∈ S_1v_jϵ_ja_j, x;                           ⋮; ∑_j∈ S_pv_j-(p-1)λϵ_ja_j, x ],


and the expected squared modulus, with respect to the random vector ϵ = (ϵ_j)_j=1^m, of an entry of VΦ x is

    _ϵ|∑_j∈ S_ℓ v_j-(ℓ-1)λϵ_ja_j, x|^2    = _ϵ∑_j, j'∈ S_ℓ v_j-(ℓ-1)λ v_j'-(ℓ-1)λϵ_j ϵ_j'a_j, xa_j', x
       = ∑_j∈ S_ℓv_j-(ℓ-1)λ^2 |a_j, x|^2.


Then, defining A_Ω_j as the restriction of A to its rows indexed by Ω_j = {j, j + λ, …, j + (p-1)λ}⊂{1,...,m}, for j = 1, …, λ we have


    _ϵVΦ x_2^2    = ∑_ℓ = 1^p ∑_j∈ S_ℓ v_j-(ℓ-1)λ^2 |a_j, x|^2
       = ∑_j=1^λ v_j^2 ∑_j'∈Ω_j |a_j', x|^2
       = ∑_j=1^λ v_j^2 A_Ω_j x_2^2.


  By the triangle inequality

    | 1/v_2^2 pVΦ x_2^2 - x_2^2|
       ≤1/v_2^2 p| VΦ x_2^2 - ∑_j = 1^λ v_j^2 A_Ω_jx_2^2| + | 1/v_2^2∑_j = 1^λ v_j^2 (1/pA_Ω_jx_2^2 - x_2^2) |
       ≤1/v_2^2 p| VΦ x_2^2 - ∑_j = 1^λ v_j^2 A_Ω_jx_2^2| + 1/v_2^2∑_j = 1^λ v_j^2 |1/pA_Ω_jx_2^2 - x_2^2 |,


which implies that for 
    T_k := { x ∈Σ_k^n, x_2=1}
 we have

    _A, ϵsup_x ∈ T_k| 1/v_2^2 pVΦ x_2^2 - x_2^2| ≤   1/v_2^2 p_A, ϵsup_x∈ T_k|VΦ x_2^2 - _ϵVΦ x_2^2| 
        + 1/v_2^2∑_j=1^λ v_j^2 _Asup_x∈ T_k|1/pA_Ω_jx_2^2 - x_2^2 |.

















The second summand above is the expected value of the RIP constant of matrices A_Ω_j drawn from the BOE or PCE, and this quantity is bounded by α_A provided p ≳ klog^4 n/α_A^2 by Theorems <ref> and <ref>. 
Therefore,

    _A, ϵsup_x ∈ T_k| 1/v_2^2 pVΦ x_2^2 - x_2^2| ≤1/v_2^2p_A, ϵsup_x∈ T_k|VΦ x_2^2 - _ϵVΦ x_2^2| + α_A.


 Here, α_A is the RIP constant in either (<ref>) or (<ref>). 

Step (II): Now, we need to bound _A, ϵsup_x∈ T_k|VΦ x_2^2 - _ϵVΦ x_2^2|.  

To control this quantity, we will use Theorem <ref>, which requires a little bit of setting up. To that end, let 
    A_j^v = [ v_1 a_(j-1)λ + 1;                ⋮;         v_λ a_jλ ],

and observe that

    VΦ x
       = [          v_1a_1, x                  …          v_λa_λ, x                                                                                                                  ;                                                               v_1a_1 + λ, x                  …        v_λa_2 λ, x                                                         ;                                                                                                                                    ⋱                                      ;                                                                                                                                      v_1a_1 + (p-1)λ, x                  …         v_λa_pλ, x ][ ϵ_1; ϵ_2;   ⋮; ϵ_m ]
       =: [ (A_1^v x)^*                                    ;             (A_2^v x)^*            ;                                   ⋱            ;                                     (A_p^v x)^* ][ ϵ_1; ϵ_2;   ⋮; ϵ_m ]
       =: A_x^v ϵ.


Let ^v be the set of matrices given by 
    ^v := {A_x^v, x∈ T_k}.
 Then, conditioning on A, by Theorem <ref>

    _ϵsup_x∈ T_k|VΦ x_2^2 - _ϵVΦ x_2^2|
       = _ϵsup_A_x^v ∈^v| A_x^v ϵ_2^2 - _ϵA_x^v ϵ_2^2 | 
       ≲ d_F(^v)γ_2(^v, ·_2→ 2) + γ_2(^v, ·_2→ 2)^2.


Our next step will be taking expectations over A, for which we will obtain an upper bound on the γ_2 functional, and a bound on the expectation of d_F(𝒜^v). We start with the latter term, for which we observe that A_x^v_F^2 = ∑_j=1^λ v_j^2 A_Ω_j x_2^2. Hence, taking expectations over A, we have

    [d_F(^v)]    = sup_x∈ T_k√(∑_j=1^λ v_j^2 A_Ω_j x_2^2)
       ≤√(∑_j=1^λ v_j^2 sup_x∈ T_kA_Ω_j x_2^2)
       ≤√(∑_j=1^λ v_j^2 (psup_x∈ T_k|1/pA_Ω_j x_2^2 - x_2^2| + psup_x∈ T_kx_2^2))
       ≤√(2p)v_2

where the third inequality is due to the fact the expected value of the RIP constant of matrices A_Ω_j is bounded by 1.


Now to control the γ_2 term, we note that since

    A_x^v - A_z^v_2→ 2   = max_w_2 = 1(A_x^v - A_z^v)w_2
       = max_w_2 = 1√(∑_j=1^λ |(w_i)_i = 1 + (j-1)λ^jλ, A_j^v(x - z)|^2)
       = max_j A_j^v (x-z)_2,

we have A_x^v - A_z^v_2→ 2 = max_j A_j^v(x - z)_2 = x - z_X where we have defined the seminorm 

    z_X := max_j≤ pA_j^v z_2.

Hence, 
    γ_2(^v, ·_2→ 2) = γ_2(T_k,·_X).
 Then, 

    _A, ϵsup_x∈ T_k|VΦ x_2^2 - _ϵVΦ x_2^2| ≤ _A [d_F(^v)γ_2(T_k, ·_X)] + _Aγ_2(T_k, ·_X)^2.
 

To bound 
 γ_2(T_k, ·_X), 
we first observe that for any vector x

    x_X ≤v_2 max_1≤ j ≤ p|⟨ a_j, x⟩| =: v_2 x_X',

which implies that

    γ_2(T_k, ·_X) ≤v_2 γ_2 (T_k, ·_X').

By Dudley's inequality (e.g., <cit.>), we have

    γ_2(T_k, ·_X') ≲∫_0^∞√(log𝒩(T_k, ·_X', u)) du.

Since a_j_∞≤ 1, the right hand side of (<ref>) can be bounded as

    ∫_0^∞√(log𝒩(T_k, ·_X', u)) du ≲√(klog plog n)log k

(see, e.g., the proof of Lemma 3.8 in <cit.>).











































































Thus, we obtain

    γ_2(T_k, ·_X) ≲v_2√(klog plog(n))log k.





















Finally, substituting (<ref>) and (<ref>) into a scaled version of (<ref>), we obtain

    sup_x∈ T_k|1/v_2^2 p(VΦ x_2^2 - VΦ x_2^2) |   ≲1/v_2^2p(v_2√(p)) v_2√(klog plog(n))log k
            + 1/v_2^2 pv_2^2klog plog(n)log^2 k
       ≲√(klog plog(n))log k/√(p) + (√(klog plog(n))log k/√(p))^2
       ≲√(klog plog(n))log k/√(p)
       ≲√(klog^4 n/p)
       ≤α_1,

provided that 
n ≳ p ≳ klog^4 n/α_1^2.
Therefore,

    _A_ϵsup_x ∈ T_k| 1/v_2^2 pΦ x_2^2 - x_2^2| ≤α_1 + α_A = α,

provided that p ≥ C_1klog^4 n/α^2.










Step (III): The probability estimate. We will use Theorem <ref> and follow the technique that was used in <cit.> (Chapter 12) to prove a similar result for BOE's (i.e., without the condensation operator V). To that end, let X^*_ℓ be the ℓ-th row of the matrix VΦ, and define Q_k, n = ⋃_S⊂ [n], |S| ≤ k Q_S, n with Q_S, n = {(z, w): z_2 = w_2 = 1, supp(z), supp(w)⊂ S}. The restricted isometry constant δ_k satisfies

    pδ_k    = sup_S⊂[n], |S| = k∑_ℓ=1^p((X_ℓ)_S(X_ℓ^*)_S - (I_n)_S) _2→ 2
    = sup_(z, w) ∈ Q_k, n⟨∑_ℓ = 1^p (X_ℓ X_ℓ^* - I_n)z, w⟩
       = sup_(z, w)∈ Q_k, n∑_ℓ = 1^p 
    ⟨ (X_ℓ X_ℓ^* - I_n)z, w⟩.



Let Q^*_k, n be a dense countable subset of Q_k, n. Then

    pδ_k = sup_(z, w)∈ Q^*_k, n∑_ℓ = 1^p f_z, w(X_ℓ),

where f_z, w(X) = 
⟨(XX^* - I_n)z, w⟩. To apply Theorem <ref>, we first check the boundedness of f_z, w for (z, w)∈ Q_k, n. That is,


    |f_z, w(X)|    ≤ |⟨ (XX^* - I_n)z, w⟩|
       ≤X_SX_S^* - (I_n)_S_2→ 2
       ≤X_SX_S^* - (I_n)_S_1→ 1.

Recall that any row of VΦ/v_2 is of the form 1/v_2∑_ℓ=1^λ v_ℓϕ_ℓ^* where ϕ_ℓ^* is a row of Φ. Since ϕ_ℓ_∞≤ 1, with δ_s,s' denoting the Kronecker delta function, we now have

    |f_z, w(X)|   ≤X_SX_S^* - (I_n)_S_1→ 1 = max_s∈ S∑_s' ∈ S|(1/v_2∑_ℓ = 1^λ v_ℓϕ_ℓ^*(s))(1/v_2∑_ℓ = 1^λ v_ℓϕ_ℓ^*(s')) - δ_s, s'|
       ≤max_s∈ S∑_s' ∈ S|v_1^2/v_2^2sup_ℓϕ_ℓ_∞sup_ℓ'ϕ_ℓ'_∞ + 1|
     ≤ 2γ^2 k,
 
where γ = v_1/v_2.

We also observe that

    |f_z, w(X)|^2 ≤|⟨ (XX^* - I_n)z, w⟩|^2 ≤(X_S X_S^* - I_n)z_2^2 = X_S_2^2 |⟨ X, z⟩|^2 - 2|⟨ X, z⟩|^2 + 1.

We bound X_S_2^2 and |⟨ X, z⟩|^2 as follows:

    X_S_2^2    = ∑_j∈ S|X_S(j)|^2
    = ∑_j∈ S|1/v_2∑_ℓ = 1^λ v_ℓϕ_ℓ(j)|^2
       ≤∑_j∈ S1/v_2^2v_1^2 ϕ_ℓ_∞^2
    
    ≤γ^2 k,

and

    |⟨ X, z⟩|^2    = 1/v_2^2|∑_ℓ = 1^λ v_ℓ⟨ϕ_ℓ, z⟩|^2
    = 1/v_2^2(∑_ℓ, ℓ'v_ℓv_ℓ'⟨ϕ_ℓ, z⟩⟨ϕ_ℓ', z⟩)
       =  1/v_2^2∑_ℓ, ℓ'v_ℓv_ℓ'⟨ϕ_ℓ, z⟩⟨ϕ_ℓ', z⟩ 
    =  1/v_2^2∑_ℓv_ℓ^2  |⟨ϕ_ℓ, z⟩|^2
       = 1/v_2^2∑_ℓ v_ℓ^2z_2^2 
    = 1.
















Therefore,
|f_z, w(X)^2| ≤γ^2 k - 1 < γ^2 k.


Applying Theorem <ref> with t = α_2 p, we obtain

    (δ_k ≥α + α_2) ≤(pδ_k ≥ pδ_k + α_2 p) ≤exp(-(α_2 p)^2/2/pγ^2 k + 4γ^2 kpδ_k + 2α_2 pγ^2 k/3),

where δ_k ≤ C√(klog^4 n/p)≤α < 1, by the first part of the theorem. Hence,

    (δ_k ≥α + α_2) ≤exp(-α_2^2 p/2kγ^21/1 + 4α + 2α_2/3) ≤exp(-c(α)α_2^2 p/2kγ^2)

where c(α) := (1 + 4α_1 + 2/3)^-1≥ (1 + 4 + 2/3)^-1 = 3/17. The above term is less than e^-ν provided that 

    p ≥34/3γ^2 kν/α_2^2.

In conclusion, by taking α_2 = α and rescaling, we have that δ_k ≤α with probability exceeding 1 - e^-ν provided that 

    p ≥ C_2max{klog^4 n/α^2, γ^2 kν/α^2}  or   p ≥ C_2k(log^4 n + γ^2ν)/α^2

for some absolute constant C_2.



§ TECHNICAL LEMMAS AND PROOFS




 §.§ Proof of Lemma <ref>

We first need the following lemma


Let (v_ℓ)_ℓ∈ℤ and (u_ℓ)_ℓ∈ℤ be any sequences such that v_ℓ = 0 for ℓ≠ 1, …, λ. Then for any integer t ≥ 0,

    ∑_ℓ = 1^λ v_ℓ (Δ^r u)_t + ℓ = (-1)^r ∑_ℓ = 1^λ (Δ^r v)_ℓ + ru_t + ℓ + ∑_j = 1^r (-1)^j (Δ^j - 1 v)_j (Δ^r - j u)_t.


Here Δ denotes the first order difference operator. That is, for any sequence (a_j)_j∈,  (Δ a)_j = a_j - a_j-1. 










The proof is by induction. First, let's check the case r = 1. 

    ∑_ℓ = 1^λ v_ℓ (Δ u)_t + ℓ   = ∑_ℓ = 1^λ v_ℓ u_t+ℓ - ∑_ℓ = 1^λ v_ℓ u_t + ℓ -1
       = ∑_ℓ = 1^λ v_ℓ u_t+ℓ - ∑_ℓ = 1^λ v_ℓ + 1u_t + ℓ + v_λ + 1 u_t + λ - v_1u_t
       = (-1)∑_ℓ = 1^λ (Δ v)_ℓ + 1u_t + ℓ + (-1)v_1u_t.

Here, we used the fact that v_λ + j = 0 for j ≥ 1.

Suppose that (<ref>) is true. Then

    ∑_ℓ = 1^λ v_ℓ (Δ^r + 1 u)_t + ℓ   = ∑_ℓ = 1^λ v_ℓ (Δ^r(Δ u))_t + ℓ
       = (-1)^r ∑_ℓ = 1^λ (Δ^r v)_ℓ + r(Δ u)_t + ℓ + ∑_j = 1^r (-1)^j (Δ^j - 1 v)_j (Δ^r - j + 1 u)_t
       = (-1)^r[∑_ℓ=1^λ (Δ^r v)_ℓ + ru_t +ℓ - ∑_ℓ = 1^λ(Δ^r v)_ℓ + ru_t + ℓ - 1] + ∑_j = 1^r (-1)^j (Δ^j - 1 v)_j (Δ^r - j + 1 u)_t
       = (-1)^r[∑_ℓ=1^λ (Δ^r v)_ℓ + ru_t +ℓ - ∑_ℓ = 1^λ(Δ^r v)_ℓ + r + 1u_t + ℓ - (Δ^r v)_r + 1 u _t]
            + ∑_j = 1^r (-1)^j (Δ^j - 1 v)_j (Δ^r - j + 1 u)_t
       = (-1)^r+1∑_ℓ = 1^λ (Δ^r+1 v)_ℓ + r + 1u_t + ℓ + (-1)^r+1(Δ^r v)_r+1 u_t + ∑_j = 1^r(-1)^j(Δ^j-1 v)_j (Δ^r + 1 - j u)_t.

In the fourth equality, we use the fact that (Δ^r v)_λ + r + 1 = ∑_j = 0^r (-1)^j rjv_λ + r + 1 - j = 0. 


We are now ready to prove Lemma <ref>. Let V_j be the jth row of the matrix V,

then by Lemma <ref>

    V_jD^r u    = ∑_ℓ = 1^λ v_ℓ (Δ^r u)_(j - 1)λ + ℓ
       = (-1)^r ∑_ℓ = 1^λ (Δ^r v)_ℓ + ru_t + ℓ_(I) + ∑_j = 1^r (-1)^j (Δ^j - 1 v)_j (Δ^r - j u)_t_(II),

where t = (j - 1)λ.

To bound (I) and (II), we first define the Fourier series of a sequence z := (z_j)_j∈ in ℓ^2() as

    z(ξ) := ∑_j∈ z_j e^-i j ξ.

Let h := (h_j)_j∈ where h_j = (-1)^j rj, for j = 0, …, r, and 0 otherwise. We observe that

    |(I)|    ≤u_∞∑_ℓ = 1^λ |(Δ^r v)_ℓ + r|
       = u_∞∑_ℓ = 1^λ |(h*v)_ℓ + r|
       ≤u_∞h*v_1,

where (h*v)_ℓ = ∑_j∈h_j v_ℓ -j denotes the convolution of h and v. 



Since

    h(ξ) = ∑_j∈h_j e^-ijξ = ∑_j = 0^r (-1)^j rj(e^-iξ)^j = (1 - e^-iξ)^r

and

    v(ξ) = ∑_j∈v_j e^-ijξ = (1 + e^-iξ + … + e^-iξ(λ̃ - 1))^r,

we obtain

    h*v(ξ) = h(ξ)v(ξ) = (1 - e^-iξλ̃)^r = ∑_j=0^r(-1)^jrje^-iξλ̃ j,

which implies that the non-zero entries of h*v are (h*v)_λ̃ j = (-1)^j rj. Thus, h*v_1 = 2^r 
and 
    |(I)| ≤ 2^ru_∞.


To bound (II), we observe that |(Δ^j-1v)_j|≤ 2^j-1max_1≤ j≤ r|v_j| 
and |(Δ^r-ju)_t|≤ 2^r-ju_∞, thus

    |(II)| ≤ r2^r-1max_1≤ j≤ r|v_j| u_∞≤ r2^r-12^2r-1u_∞,

where the last inequality is due to the fact that by the definition of v, v_j are multinomial coefficients satisfying 
max_1≤ j ≤ r |v_j| ≤2r-1r-1 = 1/22rr≤1/2 4^r.
Combining the bounds on  (I) and (II), we get

    |V_j D^r u|/u_∞≤  2^r + r2^3r - 2≤ r2^3r - 1.

This yields




    VD^r _∞→ 2≤9/8r2^3r - 1/v_2≤ (8r)^r+1λ^-r + 1/2.


Here, the first and second inequalities in (<ref>) are due to the facts that 


    VD^r_∞→ 2≤√(p)VD^r_∞→∞ = 9/8v_2VD^r_∞→∞
 
and v_2 ≥λ^r - 1/2r^-r, respectively.





























































































§ ACKNOWLEDGMENTS

RS was supported in part by the NSF via DMS-1517204. The authors would like to thank Sjoerd Dirksen and Laurent Jacques for stimulating conversations on binary embeddings. 
abbrv


