稀疏表示和压缩感知

##　前言

最近看了些联邦学习通信量相关的文章，想要看看联邦学习通信量压缩是否有可以做的点. 在这个过程中,看到了很多相关的概念,需要梳理帮助理解.

##　基本概念

在压缩感知中经常有稀疏的概念, 它的意思是: 对于N维的向量, 它的N个元素值只有K个是非零的,其中K«N, 则我们称这个向量是严格K稀疏的.

严格K稀疏比较困难,一般而言,只要除了这K个值以外的其他值都很小, 那么就称这个向量是K稀疏.

从字面就可以理解,在压缩感知中,稀疏是很重要的. 稀疏就意味着可以压缩, 对于一个向量,我们只需存储非零值及位置就可以. 换而言之, 稀疏性是压缩感知的前提.

范数的概念我之前在UnivMon中也看到过,但是并没有很在意,没想到在这里又遇到了.

定义集合 $x = {x_1, x_2, …, x_n}$, 则$l_p$范数定义为:

\[||x||_p = (\sum_{i=1}^{n}x_i^p)^{1/p}\]

常见的有$l_0,l_1,l_2$范数, 通常需要将$l_0$范数等价为$l_1$范数求解,因为$l_1$范数求解是凸优化问题,而$l_0$范数求解是一个NP难问题.

从数学意义上讲:

$l_0$范数是集合中的非零元素的个数,即稀疏度. 当然也可以理解成基数

$l_1$范数是

当函数取最小值时,自变量的值.

如$\arg\min_x(1-

)={0}$, $\arg\min_x(x(10-x)) = 5$

稀疏表示是对原始信号的分解过程,该过程借助一个事先得到的字典(也称为过完备基, overcomplete basis),将原始信号转化为字典的线性近似的过程.

稀疏表示包含两个关键步骤: 构建过完备字典和求取稀疏矩阵

参考文献