神经学启发

稀疏编码的概念来自于神经生物学。生物学家提出，哺乳类动物在长期的进化中，生成了能够快速，准确，低代价地表示自然图像的视觉神经方面的能力。我们直观地可以想象，我们的眼睛每看到的一副画面都是上亿像素的，而每一副图像我们都只用很少的代价重建与存储。我们把它叫做稀疏编码，即Sparse Coding。

从上可以看出稀疏编码的目的是：在大量的数据集中，选取很小部分作为元素来重建新的数据。

---

数学推导

稀疏编码是一种 unsupervised learning，我们希望找到一组 over-complete 的 基向量 basic vector 来表示我们的数据，也就是数据 $\textbf{x}$ 可以表示为这些基向量的线性组合：

$$\textbf{x} = \sum_{i=1}^k a_i \phi_i$$

对于基向量的学习，我们一般有一组训练数据，另外，基向量的大小规定为 $\textbf{x}\in R^n$，同时，也是数据的大小。一般来讲，$n$ 维的数据最多只需要 $n$ 个线性不相关的基向量就可以了（使用 PCA），但是就 n 个基向量的话，可能有一个现象就是，没个数据可能都需要接近 n 个基向量来表示，我们希望 稀疏编码 能有一个优势，就是组成数据的基向量个数尽可能的小一些，也就是上面的 $\mathbf{a}$ 是稀疏的。。。

为了达成这个目的，我们可以增加基向量的个数 $k > n$，也就是说，一个数据，可能由多种基向量来表示了，在所有的表示中，我们可以尽可能的选取稀疏的表示方法。。

Sparse Coding 可以分为两个部分，一个是 Training 阶段，一个是 Coding阶段

Training

给定一些列样本数据 $[ x_1,x_2,… x_m]$ 我们希望学到一组基 $[ \phi_1,\phi_2,…,\phi_k ]$ 来表示前面的数据，训练的 objective function 如下：

$$\mathop{min}_{a,\phi} \sum_{i=1}^m \left \Vert x_i-\sum_{j=1}^k a_{i,j}\phi_j \right \Vert^2 + \lambda \sum_{i=1}^m \sum_{j=1}^k |a_{i,j}|$$

优化的迭代分为两部（都可以用凸优化来求解）

• 固定字典 $\phi$ 更新 $a$，这个问题其实就是一个 Lasso 问题
• 固定表达 $a$ 更新 $\phi$，这个其实就是一个 QP 问题

Coding

给定一个新的数据，获得它关于字典的表达，这一步，其实就是上面的优化的第二步

$$\mathop{min}_{a} \sum_{i=1}^m \left \Vert x_i-\sum_{j=1}^k a_{i,j}\phi_j \right \Vert^2 + \lambda \sum_{i=1}^m \sum_{j=1}^k |a_{i,j}|$$

---

Reference

https://www.cnblogs.com/aixueshuqian/p/3936892.html
https://www.cnblogs.com/caocan702/p/5666175.html
.