Compression for exact match identification
Amir Ingber, Thomas A. Courtade, Tsachy Weissman · 2013
In this paper, we consider the problem of determining whether sequences X and Y, generated i.i.d. according to PX× PY, are equal given access only to the pair (Y, T(X)), where T(X) is a rate-R compressed version of X. In general, the rate R may not be sufficiently large to reliably determine whether X=Y. We precisely characterize this reliability - i.e., the exponential rate at which an error is made - as a function of R. Interestingly, the exponent turns out to be related to the Bhattacharyya distance between the distributions PXand PY. In addition, the scheme achieving this exponent is universal, i.e. does not depend on PX, PY.