Compression for Quadratic Similarity Queries: Finite Blocklength and Practical Schemes.
Compression for Quadratic Similarity Queries: Finite Blocklength and Practical Schemes.
复制标题
二次相似性查询的压缩：有限块长度和实用方案。
DOI：
10.1109/tit.2016.2535172
复制
发表时间：
2016
影响因子：
2.5
通讯作者：
Weissman,Tsachy
中科院分区：
文献类型：
--
作者：
Steiner,Fabian;Dempfle,Steffen;Ingber,Amir;Weissman,Tsachy
我们研究的问题，压缩的目的是相似性识别，其中相似性是衡量向量之间的均方欧氏距离。虽然渐近基本限制的问题-最小压缩率和误差指数-在以前的工作中发现，在本文中，我们专注于非渐近域和实际的，可实现的计划。首先，我们提出了一个有限的块长度的可扩展性界的基础上的形状增益量化：通过标量量化的矢量的增益（幅度）进行压缩，和形状（单位球上的投影）使用球形码进行量化。数值计算的结果，他们收敛到渐近值，预测的误差指数。然后，我们给出了一个非渐近下界的任何压缩方案的性能，并比较上（可压缩性）界。对于这样一个计划的实际实施，我们使用包裹球形码，研究由Hamkins和Zeger，并使用水蛭格作为一个例子的基础晶格。作为一个侧面的结果，我们得到一个绑定的覆盖角的任何包裹的球形代码，作为覆盖半径的基础晶格的函数。
We study the problem of compression for the purpose of similarity identification, where similarity is measured by the mean square Euclidean distance between vectors. While the asymptotical fundamental limits of the problem—the minimal compression rate and the error exponent—were found in a previous work, in this paper, we focus on the nonasymptotic domain and on practical, implementable schemes. We first present a finite blocklength achievability bound based on shape-gain quantization: the gain (amplitude) of the vector is compressed via scalar quantization, and the shape (the projection on the unit sphere) is quantized using a spherical code. The results are numerically evaluated, and they converge to the asymptotic values, as predicted by the error exponent. We then give a nonasymptotic lower bound on the performance of any compression scheme, and compare to the upper (achievability) bound. For a practical implementation of such a scheme, we use wrapped spherical codes, studied by Hamkins and Zeger, and use the Leech lattice as an example for an underlying lattice. As a side result, we obtain a bound on the covering angle of any wrapped spherical code, as a function of the covering radius of the underlying lattice.