Small Width, Low Distortions: Quantized Random Embeddings of Low-complexity Sets
Jacques · cs.IT,math.IT · 2016-11-14 · 原文
Under which conditions and with which distortions can we preserve the pairwise-distances of low-complexity vectors, e.g., for structured sets such as the set of sparse vectors or the one of low-rank matrices, when these are mapped in a finite set of vectors? This work addresses this general question through the specific use of a quantized and dithered random linear mapping which combines, in the following order, a sub-Gaussian random projection in \mathbb R^M of vectors in \mathbb R^N, a random translation, or "dither", of the projected vectors and a uniform scalar quantizer of resolution δ>0 applied componentwise. Thanks to this quantized mapping we are first able to show that, with high probability, an embedding of a bounded set \mathcal K \subset \mathbb R^N in δ\mathbb Z^M can be achieved when distances in the quantized and in the original domains are measured with the \ell_1- and \ell_2-norm, respectively, and provided the number of quantized observations M is large before the square of the "Gaussian mean width" of \mathcal K. In this case, we show that the embedding is actually "quasi-isometric" and only suffers of both multiplicative and additive distortion
讲义
讲义·推断 依据「原文」自动生成的结构化摘要（推断），非原文表述；以原文为准。
1. 人话版
Under which conditions and with which distortions can we preserve the pairwise-distances of low-complexity vectors, e.g., for structured sets such as the set of sparse vectors or the one of low-rank matrices, when these are mapped in a finite set of vectors?
This work addresses this general question through the specific use of a quantized and dithered random linear mapping which combines, in the following order, a sub-Gaussian random projection in \mathbb R^M of vectors in \mathbb R^N, a random translation, or "dither", of the projected vectors and a uniform scalar quantizer of resolution δ>0 applied componentwise.
2. 领域脉络
本文类目：cs.IT、math.IT，属于其所在研究脉络的最新进展。
3. 机制拆解
摘要未展开方法细节——精读时重点看方法/模型部分。
4. 证据与数字
Thanks to this quantized mapping we are first able to show that, with high probability, an embedding of a bounded set \mathcal K \subset \mathbb R^N in δ\mathbb Z^M can be achieved when distances in the quantized and in the original domains are measured with the \ell_1- and \ell_2-norm, respectively, and provided the number of quantized observations M is large before the square of the "Gaussian mean width" of \mathcal K.
5. 反例与边界
In this case, we show that the embedding is actually "quasi-isometric" and only suffers of both multiplicative and additive distortion
6. 跨领域连接与意外收获
横跨 2 个类目（cs.IT、math.IT），关注其在你兴趣板块间的迁移面。
7. 可复用方法
把本文机制与你手头项目对照，找一个两周内能验证的最小实验。
8. 术语表
精读时把不熟的术语记入此处，作为下次回忆的锚点。