摘要翻译：
本文研究了两个相关的问题，即保持距离的二进制嵌入和压缩感知的量化。首先，我们提出了快速的方法，将与欧几里得度量相关的子集$\mathcal{X}\子集\mathbb{R}^n$中的点替换为立方体$\{\pm1\}^m$中的点，并将立方体与近似于$\mathcal{X}$中的点之间欧几里得距离的伪度量相关联。我们的方法依赖于量化基于有界正交系统和部分循环系综的快速Johnson-Lindenstrauss嵌入，这两种方法都允许快速变换。我们的量化方法利用噪声整形，包括∑-Δ方案和分布式噪声整形方案。根据嵌入方法的不同，由此产生的逼近误差以$m$为单位以多项式和指数形式快速衰减。这大大超过了与二进制嵌入和汉明距离相关的当前衰减速率。此外，这是第一个适用于快速Johnson-Lindenstrauss映射的二进制嵌入结果，同时保持$\ell2$范数。其次，我们再次考虑噪声整形方案，尽管这一次是为了量化由有界正交系综和部分循环矩阵产生的压缩感知测量。我们证明，当使用凸优化方法进行重建时，这些方法产生的重建误差再次随测量数（和比特数）衰减。具体而言，对于Sigma-Delta方案，误差随测量次数呈多项式衰减，而对于基于beta编码的分布式噪声整形方案，误差呈指数衰减。这些结果几乎是最优的，也是第一个处理有界正交系统的结果。
---
英文标题：
《Fast binary embeddings, and quantized compressed sensing with structured
  matrices》
---
作者：
Thang Huynh, Rayan Saab
---
最新提交年份：
2018
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Information Theory        信息论
分类描述：Covers theoretical and experimental aspects of information theory and coding. Includes material in ACM Subject Class E.4 and intersects with H.1.1.
涵盖信息论和编码的理论和实验方面。包括ACM学科类E.4中的材料，并与H.1.1有交集。
--
一级分类：Electrical Engineering and Systems Science        电气工程与系统科学
二级分类：Signal Processing        信号处理
分类描述：Theory, algorithms, performance analysis and applications of signal and data analysis, including physical modeling, processing, detection and parameter estimation, learning, mining, retrieval, and information extraction. The term "signal" includes speech, audio, sonar, radar, geophysical, physiological, (bio-) medical, image, video, and multimodal natural and man-made signals, including communication signals and data. Topics of interest include: statistical signal processing, spectral estimation and system identification; filter design, adaptive filtering / stochastic learning; (compressive) sampling, sensing, and transform-domain methods including fast algorithms; signal processing for machine learning and machine learning for signal processing applications; in-network and graph signal processing; convex and nonconvex optimization methods for signal processing applications; radar, sonar, and sensor array beamforming and direction finding; communications signal processing; low power, multi-core and system-on-chip signal processing; sensing, communication, analysis and optimization for cyber-physical systems such as power grids and the Internet of Things.
信号和数据分析的理论、算法、性能分析和应用，包括物理建模、处理、检测和参数估计、学习、挖掘、检索和信息提取。“信号”一词包括语音、音频、声纳、雷达、地球物理、生理、（生物）医学、图像、视频和多模态自然和人为信号，包括通信信号和数据。感兴趣的主题包括：统计信号处理、谱估计和系统辨识；滤波器设计；自适应滤波/随机学习；（压缩）采样、传感和变换域方法，包括快速算法；用于机器学习的信号处理和用于信号处理应用的机器学习；网络与图形信号处理；信号处理中的凸和非凸优化方法；雷达、声纳和传感器阵列波束形成和测向；通信信号处理；低功耗、多核、片上系统信号处理；信息物理系统的传感、通信、分析和优化，如电网和物联网。
--
一级分类：Mathematics        数学
二级分类：Information Theory        信息论
分类描述：math.IT is an alias for cs.IT. Covers theoretical and experimental aspects of information theory and coding.
它是cs.it的别名。涵盖信息论和编码的理论和实验方面。
--
一级分类：Statistics        统计学
二级分类：Machine Learning        机器学习
分类描述：Covers machine learning papers (supervised, unsupervised, semi-supervised learning, graphical models, reinforcement learning, bandits, high dimensional inference, etc.) with a statistical or theoretical grounding
覆盖机器学习论文（监督，无监督，半监督学习，图形模型，强化学习，强盗，高维推理等）与统计或理论基础
--

---
英文摘要：
  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.
---
PDF链接：
https://arxiv.org/pdf/1801.08639