See my personal website to learn more about me and my research: http://zl19920612.wixsite.com/linzhou
The impossibility result for a model based on applications in database
This line of research has applications in database search and recovery. It was initiated by Willems et. al. then then revisited by many researchers including Ertem Tuncel. We are interested in establishing the strong impossibility result, which states what kind of performance is impossible and thus helps show the optimality of existing results.
Abstract: In this paper, we revisit the high-dimensional content identification with lossy recovery problem (Tuncel and G\"und\"uz, 2014). We first present a non-asymptotic converse bound. Invoking the non-asymptotic converse bound, we derive a lower bound on the exponent of the probability of correct decoding (the strong converse exponent) and show the lower bound is strictly positive if the rate-distortion tuple falls outside the rate-distortion region by Tuncel and G\"und\"uz. Hence, we establish the exponential strong converse theorem for the content identification problem with lossy recovery. As corollaries of the exponential strong converse theorem, we derive an upper bound on the joint excess-distortion exponent for the problem. Our main results can be specialized to the biometrical identification problem~(Willems, 2003) and the content identification problem~(Tuncel, 2009) since these two problems are both special cases of the content identification problem with lossy recovery. We leverage the information spectrum method introduced by Oohama (2015, 2016). We adapt the strong converse techniques therein to be applicable to the problem at hand and we unify the analysis carefully to obtain the desired results.
Pub.: 21 Feb '17, Pinned: 01 Sep '17