【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.压缩感知
在现实任务中，我们常希望根据部分信息来恢复全部信息。例如在数据通讯中要将模拟信号转换为数字信号，根据奈奎斯特（Nyquist）采样定理，令采样频率达到模拟信号最高频率的两倍，则采样后的数字信号就保留了模拟信号的全部信息；换言之，由此获得的数字信号能精确重构原模拟信号。然而，为了便于传输、存储，在实践中人们通常对采样的数字信号进行压缩，这有可能损失一些信息，而在信号传输过程中，由于信道出现丢包等问题，又可能损失部分信息。那么，接收方基于收到的信号，能否精确地重构出原信号呢？压缩感知（compressed sensing或compressive sensing）为解决此类问题提供了新的思路。
奈奎斯特采样定理提供了信号恢复的充分条件而非必要条件。
假定有长度为$m$的离散信号$\mathbf{x}$，不妨假定我们以远小于奈奎斯特采样定理要求的采样率进行采样，得到长度为$n$的采样后信号$\mathbf{y}$，$n \ll m$，即
\[\mathbf{y} = \Phi \mathbf{x} \tag{1}\]$\mathbf{y}$亦称“测量值”。
其中$\Phi \in \mathbb{R}^{n \times m}$是对信号$\mathbf{x}$的测量矩阵，它确定了以什么频率进行采样以及如何将采样样本组成采样后的信号。
在已知离散信号$\mathbf{x}$和测量矩阵$\Phi$时要得到测量值$\mathbf{y}$很容易，然而，若将测量值和测量矩阵传输出去，接收方能还原出原始信号$\mathbf{x}$吗？
一般来说是不能的，这是由于$n \ll m$，因此$\mathbf{y},\mathbf{x},\Phi$组成的式(1)是一个欠定方程，无法轻易求出数值解。
个人注解：
欠定方程（underdetermined equation）是指未知数的数量多于独立方程数量的线性方程组。换句话说，方程的个数少于未知数的个数。在这种情况下，通常无法找到唯一的解，而是有无限多的解。
现在不妨假设存在某个线性变换$\Psi \in \mathbb{R}^{m \times m}$，使得$\mathbf{x}$可表示为$\Psi \mathbf{s}$，于是$\mathbf{y}$可表示为
\[\mathbf{y} = \Phi \Psi \mathbf{s} = \mathbf{A} \mathbf{s} \tag{2}\]假定$\mathbf{x}$本身不是稀疏的。
其中$\mathbf{A} = \Phi \Psi \in \mathbb{R}^{n \times m}$。于是，若能根据$\mathbf{y}$恢复出$\mathbf{s}$，则可通过$\mathbf{x} = \Psi \mathbf{s}$来恢复出信号$\mathbf{x}$。
粗看起来式(2)没有解决任何问题，因为式(2)中恢复信号$\mathbf{s}$这个逆问题仍是欠定的。然而有趣的是，若$\mathbf{s}$具有稀疏性，则这个问题竟能很好地得以解决！这是因为稀疏性使得未知因素的影响大为减少。此时式(2)中的$\Psi$称为稀疏基，而$\mathbf{A}$的作用则类似于字典，能将信号转换为稀疏表示。
事实上，在很多应用中均可获得具有稀疏性的$\mathbf{s}$，例如图像或声音的数字信号通常在时域上不具有稀疏性，但经过傅里叶变换、余弦变换、小波变换等处理后却会转化为频域上的稀疏信号。
显然，与特征选择、稀疏表示不同，压缩感知关注的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。通常认为，压缩感知分为“感知测量”和“重构恢复”这两个阶段。“感知测量”关注如何对原始信号进行处理以获得稀疏样本表示，这方面的内容涉及傅里叶变换、小波变换以及字典学习、稀疏编码等，不少技术在压缩感知提出之前就已在信号处理等领域有很多研究；“重构恢复”关注的是如何基于稀疏性从少量观测中恢复原信号，这是压缩感知的精髓，当我们谈到压缩感知时，通常是指该部分。
压缩感知的相关理论比较复杂，下面仅简要介绍一下“限定等距性”（Restricted Isometry Property，简称RIP）。
对大小为$n \times m \ (n \ll m)$的矩阵$\mathbf{A}$，若存在常数$\delta_k \in (0,1)$使得对于任意向量$\mathbf{s}$和$\mathbf{A}$的所有子矩阵$\mathbf{A}_k \in \mathbb{R}^{n \times k}$有
\[(1-\delta_k) \lVert \mathbf{s} \rVert_2^2 \leqslant \lVert \mathbf{A}_k \mathbf{s} \rVert_2^2 \leqslant (1+\delta_k) \lVert s \rVert_2^2 \tag{3}\]则称$\mathbf{A}$满足$k$限定等距性（k-RIP）。此时可通过下面的优化问题近乎完美地从$\mathbf{y}$中恢复出稀疏信号$\mathbf{s}$，进而恢复出$\mathbf{x}$：
\[\begin{equation*} \begin{aligned} &\min_{\mathbf{s}} \|\mathbf{s}\|_0 \\ &\text{s.t.} \quad \mathbf{y} = \mathbf{A} \mathbf{s} \end{aligned} \end{equation*} \tag{4}\]个人注解：
$L_0$范数用来衡量一个向量中非零元素的个数。式(4)的目的就是找到一个尽可能稀疏的$\mathbf{s}$。为了保证这个稀疏解的准确性和有效性，我们需要k-RIP作为限制条件。
求稀疏解的用途之一就是数据压缩。
然而，式(4)涉及$L_0$范数最小化，这是个NP难问题。值得庆幸的是，$L_1$范数最小化在一定条件下与$L_0$范数最小化问题共解，于是实际上只需关注
\[\begin{equation*} \begin{aligned} &\min_{\mathbf{s}} \|\mathbf{s}\|_1 \\ &\text{s.t.} \quad \mathbf{y} = \mathbf{A} \mathbf{s} \end{aligned} \end{equation*} \tag{5}\]这样，压缩感知问题就可通过$L_1$范数最小化问题求解，例如式(5)可转化为LASSO的等价形式再通过近端梯度下降法求解，即使用“基寻踪去噪”（Basis Pursuit De-Noising）。
基于部分信息来恢复全部信息的技术在许多现实任务中有重要应用。例如网上书店通过收集读者在网上对书的评价，可根据读者的读书偏好来进行新书推荐，从而达到定向广告投放的效果。显然，没有哪位读者读过所有的书，也没有哪本书被所有读者读过，因此，网上书店所搜集到的仅有部分信息。例如表11.1给出了四位读者的网上评价信息，这里评价信息经过处理，形成了“喜好程度”评分（5分最高）。由于读者仅对读过的书给出评价，因此表中出现了很多未知项“?”。
这是一个典型的“协同过滤”（collaborative filtering）任务。
那么，能否将表11.1中通过读者评价得到的数据当作部分信号，基于压缩感知的思想恢复出完整信号呢？
我们知道，能通过压缩感知技术恢复欠采样信号的前提条件之一是信号有稀疏表示。读书喜好数据是否存在稀疏表示呢？答案是肯定的。于是，我们能通过类似压缩感知的思想加以处理。
矩阵补全（matrix completion）技术可用于解决这个问题，其形式为
\[\begin{equation*} \begin{aligned} &\min_{\mathbf{X}} \text{rank}(\mathbf{X}) \\ &\text{s.t.} \quad (\mathbf{X})_{ij} = (\mathbf{A})_{ij}, \ (i,j) \in \Omega \end{aligned} \end{equation*} \tag{6}\]亦称“低秩矩阵恢复”。
其中，$\mathbf{X}$表示需恢复的稀疏信号；$\text{rank}(\mathbf{X})$表示矩阵$\mathbf{X}$的秩；$\mathbf{A}$是如表11.1的读者评分矩阵这样的已观测信号；$\Omega$是$\mathbf{A}$中非“?”元素$(\mathbf{A})_{ij}$的下标$(i,j)$的集合。式(6)的约束项明确指出，恢复出的矩阵中$(\mathbf{X})_{ij}$应当与已观测到的对应元素相同。
与式(4)相似，式(6)也是一个NP难问题。注意到$\text{rank}(\mathbf{X})$在集合$\{ \mathbf{X}\in \mathbb{R}^{m\times n} : | \mathbf{X} |_F^2 \leqslant 1 \}$上的凸包是$\mathbf{X}$的“核范数”（nuclear norm）：
\[\| \mathbf{X} \|_* = \sum_{j=1}^{\min \{m,n\}} \sigma _j (\mathbf{X}) \tag{7}\]核范数亦称“迹范数”（trace norm）。
其中$\sigma _j (\mathbf{X})$表示$\mathbf{X}$的奇异值，即矩阵的核范数为矩阵的奇异值之和，于是可通过最小化矩阵核范数来近似求解式(6)，即
\[\begin{equation*} \begin{aligned} &\min_{\mathbf{X}} \| \mathbf{X} \| _* \\ &\text{s.t.} \quad (\mathbf{X})_{ij} = (\mathbf{A})_{ij}, \ (i,j) \in \Omega \end{aligned} \end{equation*} \tag{8}\]式(8)是一个凸优化问题，可通过半正定规划（Semi-Definite Programming，简称SDP）求解。理论研究表明，在满足一定条件时，若$\mathbf{A}$的秩为$r$，$n\ll m$，则只需观察到$O(mr \log ^2 m)$个元素就能完美恢复出$\mathbf{A}$。
