PROJECT TITLE :

Compression for Quadratic Similarity Queries: Finite Blocklength and Practical Schemes

ABSTRACT:

We tend to study the matter of compression for the aim of similarity identification, where similarity is measured by the mean square Euclidean distance between vectors. While the asymptotical elementary limits of the matter—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 have a tendency to 1st present a finite blocklength achievability certain primarily 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 employing a spherical code. The results are numerically evaluated, and that they converge to the asymptotic values, as predicted by the error exponent. We then offer a nonasymptotic lower bound on the performance of any compression scheme, and compare to the higher (achievability) certain. For a practical implementation of such a theme, we use wrapped spherical codes, studied by Hamkins and Zeger, and use the Leech lattice as an example for an underlying lattice. As a facet result, we tend to get a bound on the covering angle of any wrapped spherical code, as a perform of the covering radius of the underlying lattice.