稀疏编码

复制本地路径 | 在线编辑

什么是稀疏编码：就是比如一大堆数据，用一些基向量去表示他们，相当于坐标转换呗。但是呢，要求转换后的坐标尽可能的稀疏，也就是其中的 0 尽可能的多。

举例而言，有数据 [1, 2, 3]、[2, 4, 6]、[3, 6, 8]。

选择 [1, 0, 0] 和 [0, 1, 0] 和 [0, 0, 1]，那么转换后的坐标还是原来坐标，都没有 0，说明这个基不好。

选择 [1, 2, 3] 和 [0, 1, 0] 和 [0, 0, 1]，转换后的坐标位 [1, 0, 0]、[2, 0, 0]、[3, 0, 0]，这个很稀疏。

选择的基就叫做字典。那么如何构造字典呢？朴素的想法肯定是，我每个数据对应一个基，这样每个数据表示就只有一个 1，其他全是 0，这多稀疏！但是过犹不及，字典一般都有规模限制。

因此构造字典往往是这样的问题：给了 n 个数据，要求你构建大小为 m 的字典。

常用的方法：K-SVD

坏的字典举例

下面给一个用随机数构成的字典，来看看它表示一张图片的情况。

转载自：https://zhuanlan.zhihu.com/p/45964374

# coding:UTF-8
import numpy as np
from sklearn import linear_model
import cv2

shape = [256, 256]
# 使用随机数生成字典，并且归一化
dictionary = np.random.random(shape)
for i in range(shape[1]):
    dictionary[:, i] = dictionary[:, i] / np.linalg.norm(dictionary[:, i])

# 用该随机数表示图片
ori = cv2.imread("/Users/linweichen/Desktop/lena.jpg", 0).astype(np.float)
x = linear_model.orthogonal_mp(dictionary, ori, n_nonzero_coefs=None)
OMP = np.dot(dictionary, x).astype(np.uint8)

cv2.namedWindow("OMP")
cv2.imshow("OMP", OMP)
cv2.waitKey(0)

原图是 lena，就不放了，这是结果，相当糟糕：

K-SVD 方法

设训练集为 Y，字典为 D。流程如下：

阶段一：初始化字典，并且将其二阶范数归一化（其实想想不就是变成坐标系的基向量吗）。构建方式文章使用了 DCT 字典，有人用随机数，效果都差不多，只不过迭代可能会久。然后用字典去表示训练集 Y，得到 X，这里一般用的是 OMP 算法，就是相当于是求 $DX=Y$ 这个方程。

将矩阵用向量表示，其中行数表示的是维度
$$
Y_{MN} = [y_1, y_2, ..., y_{N-1}, y_N] \
D_{MK} = [d_1, d_2, ..., d_{K-1}, d_K] \
X_{K*N} = [x_1, x_2, ..., x_{N-1}, x_N]
$$
阶段二：我们目标更新某一列，那么，我们的目标是最小化：
$$
||Y - DX||2^2 = ||Y - \sum{i=1}^{K} d_i * x_i^T||_2^2
$$

稀疏编码

坏的字典举例

K-SVD 方法

Comments