Most Informative Quantization Functions
Most Informative Quantization Functions
复制标题
信息最丰富的量化函数
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. T. T. ParisTech
中科院分区：
文献类型：
--
作者：
V. Chandar;A. T. T. ParisTech
这说明提供了一些见解，最近提出的一个有趣的量化问题Kumar和Courtade。欢迎任何反馈。I.在本文中，X表示{0，1}n中随机均匀选择的向量，Y n表示X通过二进制对称信道的随机观测，交叉概率为p ∈ [0，1/2）。给定一个整数k ≥ 1，我们想找到X的k比特量化，它引起与Y的最大互信息，即我们感兴趣的是I（k，n）def = max f∈Sn，k I（f（X）;Y），其中Sn，k def = {f：{0，1}n → {0，1}k}。这个问题由Kumar和Courtade在[1]中提出，其中k = 1，证明了对于任何n ≥ 1，I（1，n）= 1− h（p），并且h（p）def = −p log p−（1 −p）log（1−p），其中对数以2为底。如果猜想成立，则任何形式为f（X）= Xi，1 ≤ i ≤ n的二元函数都达到最大值。更一般地，我们可以问，对于任意整数k ≥ 1和n ≥ 1，I（k，n）/k是否等于1 − h（p）。也许令人惊讶的是，答案是否定的。二. I（k，n）的性质和正速率极限我们对函数I（k，n）作一些初步的观察。由于I（n，k）≤ k，且对于固定的k，I（k，n）是n的非减函数，（我们总是可以通过忽略额外的符号X2 n1+1来将针对给定n1定义的函数扩展到n2 > n1，并获得相同的互信息）函数I（k）def = lim n→∞ I（k，n）对于任何k ≥ 1都是良好定义的，并且还满足I（k）= sup n≥1 I（k，n）。该函数也是超加性的，即，对任意k ≥ 1和l ≥ 1，I（k + l）≥ I（k）+ I（l）.这个属性反映了这样一个事实，即给定某个输入X 1，我们总是可以将前n位转换为k位，将剩余的n位转换为l位。Fekete引理则保证lim k→∞ I（k）/k是良好定义的，并且等于
This note provides some insights to an intriguing quantization problem recently posed by Kumar and Courtade. Any feedback is welcome. I. THE PROBLEM Throughout this note X denotes a randomly and uniformly chosen vector in {0, 1}n and Y n denotes a random observation of X through a binary symmetric channel with crossover probability p ∈ [0, 1/2). Given an integer k ≥ 1 we want to find the k-bit quantization of X which induces the largest mutual information with Y , that is we are interested in I(k, n) def = max f∈Sn,k I(f(X);Y ) where Sn,k def = {f : {0, 1}n → {0, 1}k}. This problem was posed by Kumar and Courtade in [1] for k = 1, where it is conjectured that I(1, n) = 1− h(p) for any n ≥ 1, and h(p) def = −p log p−(1−p) log(1−p) where the logarithm is to the base 2. If the conjecture is true, then any binary function of the form f(X) = Xi, 1 ≤ i ≤ n, achieves the maximum. More generally we could ask whether I(k, n)/k equals to 1 − h(p) for any integers k ≥ 1 and n ≥ 1. Surprisingly perhaps, the answer turns out to be negative. II. PROPERTIES OF I(k, n) AND POSITIVE RATES LIMITS We make some preliminary observations regarding the function I(k, n). Since I(n, k) ≤ k and since, for fixed k, I(k, n) is a nondecreasing function of n (we can always extend a function defined for a given n1 to n2 > n1 by ignoring the extra symbols X2 n1+1 and achieve the same mutual information) the function I(k) def = lim n→∞ I(k, n) is well defined for any k ≥ 1 and also satisfies I(k) = sup n≥1 I(k, n). This function is also super-additive, i.e., for any k ≥ 1 and l ≥ 1 I(k + l) ≥ I(k) + I(l). This property reflects the fact that, given some input X 1 , we can always quantize the first n bits to k bits and the remaining n bits to l bits. Fekete’s lemma then guarantees that lim k→∞ I(k)/k is well defined and is equal to