信息的有损压缩
约 729 个字 20 张图片 预计阅读时间 2 分钟
[!ABSTRACT] 率失真编码: 相当于香农第三定理
回顾无损压缩：\(R \geq H(U)\) , 但无损压缩中 \(\epsilon \rightarrow 0\)。不减少信息量 事实上可以存在错误率 \(\epsilon\)
有损压缩： 现在需要编码的\(H > R_s\) ， 没法满足\(H<R_s<R_C<C\) 由此：降熵，减少信息量，令\(H'<H \, \Rightarrow H'<R_s<R_C<C √\)
有损压缩的关键问题：给定失真度要求下，尽可能降低数据熵率 （同样损失5%，压缩的最小值是多少？）
例子：
内存无法存放连续的高斯变量，需要对它采样：
连续随机变量\(X\)，用\(R\)比特\((2^R\)个电平)对\(X\)进行表示，令\(\hat{X}(X)\)表示\(X\)的量化值，如何选择量化电平，使平均失真最小。与\(X\)的概率分布有关，设\(X\)满足均值为\(\sigma^2\)的高斯分布，失真定义为\(E[X-\hat{X}]^2\)
法1： 用1bit量化结果应该为：(再生点)
$$ \hat{X}(X) = \left{ \begin{array}{ll} \sqrt{\frac{2}{\pi}}\sigma & X > 0 \ -\sqrt{\frac{2}{\pi}}\sigma & X < 0 \end{array} \right. $$ 可以用拉格朗日乘数法求解： //To be done 这个结果和失真的定义式也有关联。
法2： 最佳再生点和最佳再生区域：
最佳再生区域： - 给定一组再生点，区域的划分应遵循把信源随机变量(X$映射到最邻近的再生点，这样失真最小。Voronoi区域，Dirichlet划分。
最佳再生点： - 在一个给定的区域中，再生点应该选择使得条件期望失真最小，相当于该区域的“质心位置”。
迭代方法(Lloyd算法)： - 首先初始化(2^R$个再生点，算出最佳再生区域。 - 根据最佳再生区域，确定新的再生点。 - 反复迭代直至收敛。
Lloyd 算法复杂度太高，随着量化比特的增加急剧增加 \(\rightarrow\) 率失真理论
率失真编码
有损的思想：让一个区域内的的\(\chi^n\)都用一个\(\mathcal{C}\)来表示。
此时，\(\hat{x_1}^n\)将会恢复成一个区域，有错误概率。
其中\(d(X^n,\hat{X}^n)\)是失真度量函数，是人为定义的，与实际工程相关。
失真度量函数
-
单符号失真度量是一个映射 $$ d(x, \hat{x}) : \chi \times \hat{\chi} \rightarrow R^+ $$
-
失真度量有界是指 $$ d_{\text{max}} = \max_{x \times \hat{x} \in \chi \times \hat{\chi}} d(x, \hat{x}) < \infty $$ 否则，很难满足\(Ed(X^n,\hat{X}^n) \leq D\)
- 序列之间的失真度量一般定义为
有时也定义为 $$ d(x^n, \hat{x}^n) = \max_i d(x_i, \hat{x}_i) $$
我们上次提到过，\(\max_i d(x_i, \hat{x}_i)\)的定义和\(\frac{1}{n} \sum_{i=1}^{n} d(x_i, \hat{x}_i)\)的定义，在\(n \rightarrow \infty\)是一样的。
一些失真函数的例子：
- Hamming失真 $$ d(x, \hat{x}) = \left{ \begin{array}{ll} 0 & x = \hat{x} \ 1 & x \neq \hat{x} \end{array} \right. $$ 即错了是1，没错是0。
-
平方误差失真 $$ d(x, \hat{x}) = (x - \hat{x})^2 $$
-
性质 $$ Ed(X, \hat{X}) = \sum_{x, \hat{x}} p(x, \hat{x})d(x, \hat{x}) \ = 0 \cdot p(X = \hat{X}) + 1 \cdot (X \neq \hat{X}) \ = p(X \neq \hat{X}) $$
失真的规范化
是否有损：看熵率，不看符号
例1：
例2：
规范化：
可以证明\(\Delta\)是常数？
连续：\(H(X) \rightarrow \infty\)
离散一定是：
率失真编码的定义：
曲线相当于是下确界，只有上面是可达的，下面是不可达的。
【图】
\((R',D)\)、\((R,D')\)都可达（在曲线上方）
率失真和失真率函数：两者互为反函数
例子：
事实要计算\(p,q\), 使\(H(\frac{1-p+q}{2})\)最小，求出\(R\)。此时D-R一一对应
下面暂时和上面无关ovo
信息率失真函数
之前我们没提到过\(I\)(互信息)..
X：原始 \(\hat{X}\)：编码后信源
香农第三定理\(R^{(I)}(D)=R(D)\)
不严谨证明：
下一步证明：两个等号同时成立/等号成立是相互独立的情形
\(X \rightarrow \hat{X}\) ，唯一 反之，不唯一(有差错)
例子：
\(\min (p,1-p)\)全取0或者全取1，最大错误概率
异或上\(\hat{X}\)没有影响？
两个等号成立条件:
\(r(1-D)+(1-r)D=p\)
这个证明的意思是，我们找到了一个\(\hat{X}\)，它取0的概率是\(r\), 1的概率是\(1-r\), 从而能够满足我们上面两个取等的条件。
拉格朗日乘数法算出来，事实上推出来的\(R(D)\neq H(p)-H(D)\)