• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Small Width, Low Distortions: Quantized Random Embeddings of Low-Complexity Sets
【24h】

Small Width, Low Distortions: Quantized Random Embeddings of Low-Complexity Sets

机译：小宽度，低失真：低复杂度集的量化随机嵌入

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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 (or embedded) 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 of vectors in , a random translation, or dither, of the projected vectors, and a uniform scalar quantizer of resolution applied componentwise. Thanks to this quantized mapping, we are first able to show that, with high probability, an embedding of a bounded set in can be achieved when distances in the quantized and in the original domains are measured with the - and -norm, respectively, and provided the number of quantized observations is large before the square of the “Gaussian mean width” of . In this case, we show that the embedding is actually quasi-isometric and only suffers from both multiplicative and additive distortions whose magnitudes decrease as for general sets, and as for structured set, when increases. Second, when one is only interested in characterizing the maximal distance separating two elements of mapped to the same quantized vector, i.e., the “consistency width” of the mapping, we show that for a similar number of measurements and with high probability, this width decays as for general sets and as for structured ones when increases. Finally, as an important aspect of this paper, we also establish how the non-Gaussianity of sub-Gaussian random projections inserted in the quantized mapping (e.g., for Bernoulli random matrices) impacts the class of vectors that can be embedded or whose consistency width provably decays when increases.
机译：在哪些条件下以及哪些失真下，当映射（或嵌入）到结构化集合（例如稀疏向量集或低秩矩阵之一）中时，我们可以保留低复杂度向量的成对距离。有限的向量集？这项工作通过具体使用量化和抖动的随机线性映射解决了这个普遍的问题，该映射按以下顺序组合了投影向量中的向量的亚高斯随机投影，投影向量的随机平移或抖动，以及分量的统一标量量化器。借助这种量化映射，我们首先能够证明，当分别使用-和-范数测量量化域和原始域中的距离时，可以有界集的嵌入。前提是量化观测的数量在的“高斯平均宽度”的平方之前大。在这种情况下，我们表明嵌入实际上是准等距的，并且仅遭受乘法和加法失真，其失真程度对于一般集合和结构化集合而言都随着增加而减小。其次，当人们仅对表征映射到同一量化矢量的两个元素的最大距离（即映射的“一致性宽度”）感兴趣时，我们表明对于相似数量的测量和高概率，该宽度当增加时，一般集和结构化集都会衰减。最后，作为本文的重要方面，我们还确定了在量化映射中插入的次高斯随机投影的非高斯性（例如，对于伯努利随机矩阵）如何影响可嵌入的矢量类别或其一致性宽度增加时可证明地衰减。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号