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 $\mathcal{X} \subset \mathbb{R}^n$,
associated with the Euclidean metric, with points in the cube $\{\pm 1\}^m$ and
we associate the cube with a pseudo-metric that approximates Euclidean distance
among points in $\mathcal{X}$. 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 $\ell_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.

本文提出了一种基于量化的快速 Johnson-Lindenstrauss 嵌入法，该方法使用有界正交系统和部分循环集合进行快速的嵌入，并利用噪声整形实现积极的降噪机制，该方法的误差多项式和指数衰减，是当前二进制嵌入和汉明距离所能达到的巅峰效果；此外，本文还提出了一种基于噪声整形机制的量化压缩感知度量方法，该方法在测量值的数量和比特数上实现了误差的多项式和指数衰减，是目前处理有限正交系统的最优表现。