稀疏表示理论的含义来源于对视神经系统的研究，最早可追溯到1959年^[1]，之后，Field^[2]提出在视觉皮层V₁区的简单细胞感受野适合用于图像结构的学习。文献[3]提出字典学习的概念，即将稀疏模型应用于二维图像时，学习到的基于哺乳动物视觉系统主视皮层V₁区内神经元的反馈特性相似，并证明了字典学习比传统的基字典表述更准确，自适应性更强。基字典第一次成功地模拟了V₁区神经元细胞具有局部性的空间域、具有方向性和选择性的时域和频域的响应特点。而每个神经元对这些响应的表述均满足稀疏表示理论，将图像在边界、线方向等特性以稀疏模型的形式进行描绘。

2006年，文献[4]第一次阐述了压缩感知概念：如果一个信号具有可压缩性，则可以通过很少的观测值去重构原始信号，打破了香农抽样定理要求信号采样率高于信号带宽两倍的局限，为稀疏表示奠定了理论基础。之后，Candes等^[5]从数学的角度证明了压缩感知原理，为压缩感知的深入研究奠定了理论基础。稀疏表示理论^[6-8]做为压缩感知首个基本要素，它的出现解决了传统信号处理中的多个问题，如就绝大多数信号的稀疏表示可提供一种全新的采样形式，即对采样信号的带宽不作要求，由稀疏性约束取代，从而主信号空间减小，大大减少了采样时间和采样储存空间。

目前，稀疏表示在各个工程应用中都有较好的表现，尤其在模式识别，计算机视觉和图像处理领域中尤为突出。近年来，该理论在测绘遥感领域内也有了较大的突破，如张良培等^[9]用稀疏表示理论对高光谱图像做了展望; 刘帆等^[10]则将字典学习技术和遥感图像融合相结合; 李丽等^[11]在对遥感图像做超分辨率重建过程中利用了非参数下的贝叶斯字典学习。未来，稀疏表示理论还会在更多的领域中崭露头角。

1 稀疏表示模型

稀疏表示的基本框架利用原子的线性组合来表示信号，并计算稀疏解，即原子的表示系数，再利用计算出的稀疏解重构信号。根据不同范数正则化的表达形式，稀疏表示可以被严格地分为5种形式：l₀范数最小化^[12]、l₁范数最小化^[13]、l_p范数(0 < p < 1)最小化^[14-16]、l_{2, 1}范数最小化^[17-21]和l₂范数最小化^[22-24]。

1.1 l₀范数下的稀疏表示模型

假设有一个信号x∈R^m，一观测矩阵或字典D∈R^m×n，D=[d₁, d₂, …, d_n]，若m < n，即字典D中的行数小于字典D的原子数，称D为一过完备字典。信号x和字典D可表示为：

$ \boldsymbol{x}=\boldsymbol{d}_{1} \alpha_{1}+\boldsymbol{d}_{2} \alpha_{2}+\cdots+\boldsymbol{d}_{n} \alpha_{n} $

(1)

式中，α_i(i=1, 2, …, n)就是原子d_i的系数，也称为解系数，α∈Rⁿ，式(1)可简写成：

$ \boldsymbol{x}=\boldsymbol{D \alpha} $

(2)

式中，解系数α=[α₁, α₂, …, α_n]^T。

因为D为一过完备字典，即式(2)为欠定线性系统，若对于稀疏解α没有任何约束条件或先验知识，式(2)会变为病态问题，无唯一解。按照稀疏表示理论的要求，解系数α必须是稀疏的，所谓稀疏性指的是α中只有有限个非零元素，而其他元素均等于或接近等于零。

对于式(2)可以通过l₀范数最小化约束^[25]求得稀疏解α，则式(2)会变为优化问题(P₀)：

$ \left(P_{0}\right) : \hat{\boldsymbol{\alpha}}=\operatorname{argmin}\|\boldsymbol{\alpha}\|_{0}使得\boldsymbol{x}=\boldsymbol{D \alpha} $

(3)

式中，‖·‖₀表示向量中非零元素的个数，也称为稀疏性度量，如果D中只有k(k < n)个原子用来线性表示信号x，式(3)等同于如下优化问题：

$ \boldsymbol{x}=\boldsymbol{D \alpha}使得\|\boldsymbol{a}\|_{0} \leqslant k $

(4)

式(4)称为k稀疏估计问题，若加上噪声，则式(2)变为：

$ \boldsymbol{x=D \alpha+\eta} $

(5)

式中，η∈R^m为上界‖η‖₂≤ε的噪声，则式(3)和式(4)变为：

$ \hat{\boldsymbol{\alpha}}=\operatorname{argmin}\|\boldsymbol{x}-\boldsymbol{D} \boldsymbol{\alpha}\|_{2}^{2}使得\|\boldsymbol{\alpha}\|_{0} \leqslant \varepsilon $

(6)

根据拉格朗日乘子法，取一合适的拉格朗日乘子λ，可以将式(6)变为无约束优化问题：

$ \hat{\boldsymbol{\alpha}}=L(\boldsymbol{\alpha}, \lambda)=\operatorname{argmin}\|\boldsymbol{x}-\boldsymbol{D} \boldsymbol{\alpha}\|_{2}^{2}+\lambda\|\boldsymbol{\alpha}\|_{0} $

(7)

1.2 l₁范数下的稀疏表示模型

解l₀范数最小化问题可以得到字典D下的稀疏解α，但该问题属多项式复杂程度的非确定性(non-deterministic polynomial, NP)问题，难以得到准确解^[26]。不过，2003年，Donoho^[27]证明了稀疏解的唯一性，随后Candès等^{[28, 29]}进一步证明了对于一个k稀疏信号x，字典D必须满足约束等距条件，则l₀范数最小化问题和l₁范数最小化问题等价。

此外，l₁范数最小化问题在多项式的时间里有解析解。可以看出，l₁范数最小化问题的提出丰富了稀疏表示的内容。同样，和(P₀)一样，(P₁)记为：

$ \left(P_{1}\right) : \operatorname{argmin}\|\boldsymbol{x-D \alpha}\|_{2}^{2}使得\|\boldsymbol{\alpha}\|_{1} \leqslant \varepsilon $

(8)

$ \hat{\boldsymbol{\alpha}}=L(\boldsymbol{\alpha}, \lambda)=\arg \min _{\boldsymbol{\alpha}} \frac{1}{2}\|\boldsymbol{x}-\boldsymbol{D} \boldsymbol{\alpha}\|_{2}^{2}+\lambda\|\boldsymbol{\alpha}\|_{1} $

(9)

式中，λ∈[0, 1]；ε取较小的正数。本文λ和ε取值要求相同。

1.3 l_p范数(0 < p < 1)下的稀疏表示模型

一般的稀疏表示方法是为了解l_p范数最小化问题，除了(P₀)和(P₁)，一些专家试着去求解当p=0.1、0.5、0.9时, l_p范数最小化(0 < p < 1)^[30]，与(P₀)和(P₁)一样，P_p记为：

$ \begin{array}{c}{\left(P_{p}\right) : \hat{\boldsymbol{\alpha}}=L(\boldsymbol{\alpha}, \lambda)=} \\ {\arg \min\limits_{\boldsymbol{\alpha}}\|\boldsymbol{x}-\boldsymbol{D} \boldsymbol{\alpha}\|_{2}^{2}+\lambda\|\boldsymbol{\alpha}\|_{p}^{p}}\end{array} $

(10)

尽管(P_p)在建立稀疏表示模型时并不常用，但同样也对稀疏表示理论的发展作出重要影响。

1.4 l₂范数和l_{2, 1}范数下的稀疏表示模型

解l₂范数最小化下的稀疏表示模型，得到的稀疏解在严格意义上并不稀疏，仅是有限稀疏，没能达到充分稀疏^[31]，(P₂)记为：

$ \left(P_{2}\right) : \operatorname{argmin}\|\boldsymbol{\alpha}\|_{2}^{2}使得\|\boldsymbol{x-D \alpha}\|_{2}^{2} \leqslant \varepsilon $

(11)

$ \hat{\boldsymbol{\alpha}}=L(\boldsymbol{\alpha}, \lambda)=\arg \min\limits_{\boldsymbol{\alpha}}\|\boldsymbol{x}-\boldsymbol{D} \boldsymbol{\alpha}\|_{2}^{2}+\lambda\|\boldsymbol{\alpha}\|_{2}^{2} $

(12)

l_{2, 1}范数又被称作旋转不变的l₁范数，它的提出克服了离散值对于模型鲁棒性的影响。基于l_{2, 1}范数稀疏表示模型的目标方程为：

$ \left(P_{2, 1}\right) ; \operatorname{argmin}\|\boldsymbol{X}-\boldsymbol{D} \boldsymbol{A}\|_{2, 1}+\mu\|\boldsymbol{A}\|_{2, 1} $

(13)

式中，X=[x₁, x₂, …, x_n]为样本组成的矩阵，A=[a₁, a₂, …, a_n]为字典D的系数矩阵；μ∈[0, 1]为较小的正数。

2 基于稀疏表示模型的优化算法

优化稀疏表示模型的算法可以分为贪婪算法、约束优化策略、逼近算法以及同伦算法4种。

2.1 贪婪算法

贪婪算法^[32]的核心思想：确定样本和原子之间的位置关系，用最小二乘法去估计幅值。之前笔者提到(P₀)本身是一个NP难问题，需要转化成(P₁)问题去求解。在针对(P₀)时，贪婪算法提供了一种思路，虽然不能直接求解(P₀)问题，但可以找到(P₀)问题的近似解。

早期经典的贪婪算法包括Mallat等提出的匹配追踪算法^[33]和Pati等提出的正交匹配追踪算法^[34]。匹配追踪的基本思想是在每次迭代中从D中选出最匹配的原子，并计算信号残差，继续选择与信号残差最匹配的原子再计算信号残差，反复迭代，由于得出的每个信号残差都比之前的残差小，故算法收敛。而正交匹配追踪是匹配追踪的改进版，即在分解的每一步对所选择的全部原子进行正交化处理，在精度要求相同的情况下，使算法的收敛速度更快。更多基于上述算法的改进方法被提出：Donoho等^[35]提出了分阶式正交匹配追踪；Dai等^[36]提出了子空间追踪；Do等^[37]结合了最大期望(expectation-maximization algorithm, EM)算法，提出了一种稀疏自适应匹配追踪算法分别估计稀疏度和支撑集；Jost等^[38]在高度冗余的字典里对相同的原子进行分类时，提出了一种树形匹配追踪算法；La等^[39]基于上述算法提出了树形正交匹配追踪算法，该算法将稀疏树形表示作为先验知识，使用很少部分的样本估计出线性逆系统；近年来，稀疏表示理论在图像修复领域又有了较大发展，提出了后向追踪算法^[40]、块结构稀疏^[41]、颜色梯度的块结构稀疏^[42]、多方向颜色梯度的块结构稀疏^[43]等新理论。

贪婪算法是通过每一步贪心选择得到问题的一个最优解，虽然每一步都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，或只是对全局解的一个近似解。

2.2 约束优化策略

约束优化策略^[44-48]是为了解l₁范数最小化稀疏表示模型，如式(9)所示，该策略的核心思想是将无约束不可导问题变为光滑约束可导的优化问题，通过约束优化方法的快速收敛得到模型的稀疏解。下面分别介绍约束优化策略的梯度投影稀疏重建法^[44]和交替方向乘子法^[47]两种经典算法。

1) 梯度投影稀疏重建法。梯度投影稀疏表示的核心思想是沿着梯度下降的方向找到稀疏解，最关键的步骤为任意的α值都可由正项系数α₊和负项系数α_-组成：

$ \boldsymbol{\alpha}=\boldsymbol{\alpha}_{+}-\boldsymbol{\alpha}_{-}, \boldsymbol{a}_{+} \geqslant 0, \boldsymbol{\alpha}_{-} \geqslant \bf{0} $

(14)

式中, 算子(·)₊表示取正项部分，即(x)₊={0, x}_max。‖α‖₁=1_d^Tα₊+1_d^Tα_-，1_d^T=$ \underbrace{[1, 1, \cdots, 1]^{\mathrm{T}}}_{d}$表示一维向量，所以式(9)可化为一个带约束的二次规划问题：

$ \begin{array}{c} \arg \min L(\boldsymbol{\alpha})=\arg \min \frac{1}{2}\left\|\boldsymbol{x}-\boldsymbol{D}\left[\boldsymbol{\alpha}_{+}-\boldsymbol{\alpha}_{-}\right]\right\|_{2}^{2}+\\ \lambda\left(\bf{1}_{d}^{\mathrm{T}} \boldsymbol{a}_{+}+\bf{1}_{d}^{\mathrm{T}} \boldsymbol{\alpha}_{-}\right)使得\boldsymbol{a}_{+} \geqslant \bf{0}, \boldsymbol{\alpha}_{-} \geqslant \bf{0} \end{array} $

(15)

或

$ \begin{array}{c}{\arg \min L(\boldsymbol{\alpha})=} \\ {\arg \min \frac{1}{2}\left\|x-\left[\boldsymbol{D}_{+}-\boldsymbol{D}_{-}\right]\left[\boldsymbol{\alpha}_{+}-\boldsymbol{\alpha}_{-}\right]\right\|_{2}^{2}+}\\ \lambda\left(\bf{1}_{d}^{\mathrm{T}} \boldsymbol{\alpha}_{+}+\bf{1}_{d}^{\mathrm{T}} \boldsymbol{\alpha}_{-}\right)使得\boldsymbol{\alpha}_{+} \geqslant \bf{0}, \boldsymbol{\alpha}_{-} \geqslant \bf{0}\end{array} $

(16)

式(16)可重写为：

$ \arg \min G(\boldsymbol{z})=\boldsymbol{c}^{\mathrm{T}} \boldsymbol{z}+\frac{1}{2} \boldsymbol{z}^{\mathrm{T}} \boldsymbol{A z}使得\boldsymbol{z }\geqslant \boldsymbol{0} $

(17)

式中，$ z=\left[\boldsymbol{\alpha}_{+} ; \boldsymbol{\alpha}_{-}\right] ; \boldsymbol{c}=\lambda \bf{1}_{2 d}+\left[-\boldsymbol{D}^{\mathrm{T}} \boldsymbol{x} ; \boldsymbol{D}^{\mathrm{T}} \boldsymbol{x}\right] ; \bf{1}_{2 d}=$$\underbrace{[1, 1, \cdots, 1]^{\mathrm{T}}}_{2 d} ; A=\left(\begin{array}{cc}{\boldsymbol{D}^{\mathrm{T}} \boldsymbol{D}} & {-\boldsymbol{D}^{\mathrm{T}} \boldsymbol{D}} \\ {-\boldsymbol{D}^{\mathrm{T}} \boldsymbol{D}} & {\boldsymbol{D}^{\mathrm{T}} \boldsymbol{D}}\end{array}\right) $。

该算法运用梯度下降和标准线搜索方法^[45]求解式(17)。z值可通过迭代获得：

$ \operatorname{argmin} \boldsymbol{z}^{t+1}=z^{t}-\sigma \nabla G\left(\boldsymbol{z}^{t}\right) $

(18)

梯度$\nabla G\left(z^{t}\right)=\boldsymbol{c}+\boldsymbol{A} \boldsymbol{z}^{t} $，σ为迭代步长，之后更新σ：

$ \sigma^{t}=\arg \min\limits_{\sigma} G\left(z^{t}-\sigma \boldsymbol{g}^{t}\right) $

(19)

g^t被定义为：

$ \boldsymbol{g}_{i}^{t}=\left\{ \begin{array}{l} {\left( {\nabla G\left( {{\mathit{\boldsymbol{z}}^t}} \right)} \right)_i}, \mathit{\boldsymbol{z}}_i^t > 0或{\left( {\nabla G\left( {{\mathit{\boldsymbol{z}}^t}} \right)} \right)_i} < 0\\ 0, 其他 \end{array} \right. $

(20)

式(19)可写成封闭解形式：

$ \sigma^{t}=\frac{\left(\boldsymbol{g}^{t}\right)^{\mathrm{T}}\left(\boldsymbol{g}^{t}\right)}{\left(\boldsymbol{g}^{t}\right)^{\mathrm{T}} \boldsymbol{A}\left(\boldsymbol{g}^{t}\right)} $

(21)

梯度投影稀疏重建采用回溯线搜索方法^[45]确保在每一次迭代中，梯度下降步长为最优值，该回溯线搜索方法的停止条件必须满足：

$ \begin{array}{*{20}{c}} {G{{\left( {{\mathit{\boldsymbol{z}}^t} - {\sigma ^t}\nabla G\left( {{\mathit{\boldsymbol{z}}^t}} \right)} \right)}_ + } > G\left( {{\mathit{\boldsymbol{z}}^t}} \right) - \beta \nabla G{{\left( {{\mathit{\boldsymbol{z}}^t}} \right)}^{\rm{T}}}X}\\ {\left( {{\mathit{\boldsymbol{z}}^t} - \left( {{\mathit{\boldsymbol{z}}^t} - {\sigma ^t}\nabla G\left( {{\mathit{\boldsymbol{z}}^t}} \right)} \right)_+ } \right)} \end{array} $

(22)

式中，β取一较小常量。

2) 交替方向乘子法。交替方向乘子法的核心思想为在求解l₁范数最小化稀疏表示模型时，通过引入辅助变量s∈R^d，将式(12)转换为如下形式的约束问题：

$ \arg \min\limits_{\alpha \cdot s} \frac{1}{2 \xi}\|\boldsymbol{s}\|_{2}^{2}+\|\boldsymbol{\alpha}\|_{1}使得\boldsymbol{s=x-D \alpha} $

(23)

将式(23)变为增广拉格朗日方程：

$ \begin{aligned} \arg \min\limits_{\boldsymbol{\alpha}, \boldsymbol{s}, \boldsymbol{\omega}}(\boldsymbol{\alpha}, \boldsymbol{s}, \boldsymbol{\omega}) &=\frac{1}{2 \xi}\|\boldsymbol{s}\|_{2}^{2}+\|\boldsymbol{\alpha}\|_{1}-\\\langle\boldsymbol{\omega}, \boldsymbol{s}+\boldsymbol{D} \boldsymbol{\alpha}-\boldsymbol{x}\rangle &+\frac{\mu}{2}\|\boldsymbol{s}+\boldsymbol{D} \boldsymbol{\alpha}-\boldsymbol{x}\|_{2}^{2} \end{aligned} $

(24)

式中，ξ为逼近参数；ω∈R^d代表拉格朗日乘子向量；μ为惩罚参数。其通用框架为：

$ \left\{\begin{array}{l}{\boldsymbol{s}^{t+1}=\arg \min L\left(\boldsymbol{s}, \boldsymbol{\alpha}^{t}, \boldsymbol{\omega}^{t}\right)} \\ {\boldsymbol{\alpha}^{t+1}=\arg \min L\left(\boldsymbol{s}^{t+1}, \boldsymbol{\alpha}, \boldsymbol{\omega}^{t}\right)} \\ {\boldsymbol{\omega}^{t+1}=\boldsymbol{\omega}^{t}-\mu\left(\boldsymbol{s}^{t+1}+\boldsymbol{D} \boldsymbol{\alpha}^{t+1}-\boldsymbol{x}\right)}\end{array}\right. $

(25)

首先，对于式(25)中第一个公式，有：

$ \begin{array}{l}{\arg \min L\left(\boldsymbol{s}, \boldsymbol{\alpha}^{t}, \boldsymbol{\omega}^{t}\right)=\frac{1}{2 \xi}\|\boldsymbol{s}\|_{2}^{2}+\left\|\boldsymbol{\alpha}^{t}\right\|_{1}-} \\ {\left(\boldsymbol{\omega}^{t}\right)^{\mathrm{T}} \times\left(\boldsymbol{s}+\boldsymbol{D} \boldsymbol{\alpha}^{t}-\boldsymbol{x}\right)+\frac{\mu}{2}\left\|\boldsymbol{s}+\boldsymbol{D} \boldsymbol{\alpha}^{t}-\boldsymbol{x}\right\|_{2}^{2}=} \\ {\frac{1}{2 \xi}\|\boldsymbol{s}\|_{2}^{2}-\left(\boldsymbol{\omega}^{t}\right)^{\mathrm{T}} \boldsymbol{s}+\frac{\mu}{2}\left\|\boldsymbol{s}+\boldsymbol{D} \boldsymbol{\alpha}^{t}-\boldsymbol{x}\right\|_{2}^{2}+} \\ {\left\|\boldsymbol{\alpha}^{t}\right\|_{1}-\left(\boldsymbol{\omega}^{t}\right)^{\mathrm{T}}\left(\boldsymbol{D} \boldsymbol{\alpha}^{t}-\boldsymbol{x}\right)}\end{array} $

(26)

式(26)关于s的解为：

$ \boldsymbol{s}^{t+1}=\frac{\xi}{1+\mu \xi}\left(\boldsymbol{\omega}^{t}-\mu\left(\boldsymbol{x-D \alpha}^{t}\right)\right) $

(27)

再者，对于式(25)中第二个公式，有：

$ \begin{array}{c}{\arg \min L\left(\boldsymbol{s}^{t+1}, \boldsymbol{\alpha}, \boldsymbol{\omega}^{t}\right)=\frac{1}{2 \xi}\left\|\boldsymbol{s}^{t+1}\right\|_{2}+} \\ {\|\boldsymbol{\alpha}\|_{1}-(\boldsymbol{\omega})^{\mathrm{T}} \times\left(\boldsymbol{s}^{t+1}+\boldsymbol{D} \boldsymbol{\alpha}-\boldsymbol{x}\right)+} \\ {\frac{\mu}{2}\left\|\boldsymbol{s}^{t+1}+\boldsymbol{D} \boldsymbol{\alpha}-\boldsymbol{x}\right\|_{2}^{2}}\end{array} $

(28)

等价于：

$ \begin{array}{l}{\arg \min \left\{\|\boldsymbol{\alpha}\|_{1}-\left(\boldsymbol{\omega}^{t}\right)^{\mathrm{T}}\left(\boldsymbol{s}^{+1}+\boldsymbol{D} \boldsymbol{\alpha}-\boldsymbol{x}\right)+\right.} \\ {\frac{\mu}{2}\left\|\boldsymbol{s}^{t+1}+\boldsymbol{D} \boldsymbol{\alpha}-\boldsymbol{x}\right\|_{2}^{2} \}=\|\boldsymbol{\alpha}\|_{1}+} \\ {\frac{\mu}{2}\left\|\boldsymbol{s}^{t+1}+\boldsymbol{D} \boldsymbol{\alpha}-\boldsymbol{x}-\boldsymbol{\omega}^{t} / \mu\right\|_{2}^{2}=} \\ {\|\boldsymbol{\alpha}\|_{1}+f(\boldsymbol{\alpha})}\end{array} $

(29)

式中，$ f(\boldsymbol{\alpha})=\frac{\mu}{2}\left\|\boldsymbol{s}^{t+1}+\boldsymbol{D} \boldsymbol{\alpha}-\boldsymbol{x}-\boldsymbol{\omega}^{t} / \mu\right\|_{2}^{2}$，用二阶泰勒展开估计f(α)，式(29)变为：

$ \begin{aligned} \arg \min \{ &\|\boldsymbol{\alpha}\|_{1}-\left(\boldsymbol{\alpha}-\boldsymbol{\alpha}^{\mathrm{T}}\right) \boldsymbol{X}^{\mathrm{T}}\left(\boldsymbol{s}^{t+1}+\boldsymbol{D} \boldsymbol{\alpha}-\right.\\ & \boldsymbol{x}-\boldsymbol{\omega}^{t} / \mu )+\frac{1}{2 \xi}\left\|\boldsymbol{\alpha}-\boldsymbol{\alpha}^{\mathrm{T}}\right\|_2^2 \} \end{aligned} $

(30)

式(30)的解可通过软阈值算子得到：

$ \boldsymbol{\alpha}^{t+1}=\operatorname{soft}\left\{\boldsymbol{\alpha}^{t}-\xi \boldsymbol{X}^{\mathrm{T}}\left(\boldsymbol{s}^{t+1}+\boldsymbol{D} \boldsymbol{\alpha}-\boldsymbol{x}-\boldsymbol{\omega}^{t} / \mu\right), \frac{\xi}{\mu}\right\} $

(31)

$ \operatorname{soft}(\boldsymbol{\alpha}, \eta)=\operatorname{sign}(\sigma) \max \{|\sigma|-\eta, 0\}$，最后，通过式(25)第三个公式来更新拉格朗日乘子ω。

2.3 逼近算法

为了求解非光滑约束凸优化逼近算法提出了^[49-55]，用式(9)求解l₁范数最小化稀疏表示模型。该算法的核心思想是将大规模分布式的、非光滑的约束优化问题分解简单子问题的组合，利用逼近算子分别去求解这些子问题，提高运算效率。

经典的逼近算法包括软阈值或收缩算子、迭代收缩阈值算法^[49]、快速迭代收缩阈值算法^[50]、l_1/2范数正则化稀疏重建^[51]、可分近似稀疏重建以及增广拉格朗日乘子法等。下面分别介绍比较常用的软阈值和快速收缩阈值算法。

1) 软阈值或收缩算子。首先，式(9)有封闭解：

$ \boldsymbol{\alpha}^{*}=\min\limits_{\boldsymbol{\alpha}} h(\boldsymbol{\alpha})=\lambda\|\boldsymbol{\alpha}\|_{1}+\frac{1}{2}\|\boldsymbol{\alpha}-\boldsymbol{s}\|^{2}=\\~~~~~~~~\sum\limits_{j=1}^{n} \lambda\left|\boldsymbol{\alpha}_{j}\right|+\sum\limits_{j=1}^{n} \frac{1}{2}\left(\boldsymbol{\alpha}_{j}-\boldsymbol{s}_{j}\right)^{2} $

(32)

式中，α^*是式(32)的最优解；h(α)为式(9)的简单形式；s∈R^d为辅助向量；λ>0为阈值。得出以下结论：① $\boldsymbol{\alpha}_{j}>0, h(\boldsymbol{\alpha})=\lambda \boldsymbol{\alpha}+\frac{1}{2}\|\boldsymbol{\alpha}-\boldsymbol{s}\|^{2}, h^{\prime}(\boldsymbol{\alpha})=\lambda+ $$ \boldsymbol{\alpha}_{j}^{*}-\boldsymbol{s}_{j}=0 \Rightarrow \boldsymbol{\alpha}_{j}^{*}=\boldsymbol{s}_{j}-\lambda$; ② $\boldsymbol{\alpha}_{j}<0, h(\boldsymbol{\alpha})=-\lambda \boldsymbol{\alpha}+ $$ \frac{1}{2}\|\boldsymbol{\alpha}-\boldsymbol{s}\|^{2}, h^{\prime}(\boldsymbol{\alpha})=-\lambda+\boldsymbol{\alpha}_{j}^{*}-\boldsymbol{s}_{j}=0 \Rightarrow \boldsymbol{\alpha}_{j}^{*}=\boldsymbol{s}_{j}+\lambda$; ③ $ -\lambda \leqslant \boldsymbol{s}_{j} \leqslant \lambda, \boldsymbol{\alpha}_{j}^{*}=0$。

式(32)的解为：

$ \boldsymbol{\alpha}_{j}^{*}=\left\{\begin{array}{cc}{\boldsymbol{s}_{j}-\lambda, } & {\boldsymbol{s}_{j}>\lambda} \\ {\boldsymbol{s}_{j}+\lambda, } & {\boldsymbol{s}_{j}<-\lambda} \\ {0, } & {其他}\end{array}\right. $

(33)

综上所述，解α^*=shrink(s, λ)，shrink(s, λ)_j=sign(s_j)max{|s_j|-λ, 0}，shrink(·)可看成逼近算子。

2) 快速迭代收缩阈值算法。该算法是迭代收缩阈值算法的改进版，不仅提升了效率，还在求解过程中全局收敛。该算法中，将汉森矩阵由标量取代，并使用了梯度∇f(α)的最小里普利茨常数去估计汉森矩阵F，即L(f)=2λ_max(D^TD)，则目标方程可变为：

$ \begin{aligned} f(\boldsymbol{\alpha}) \approx \frac{1}{2}\left\|\boldsymbol{D} \boldsymbol{\alpha}^{t}-\boldsymbol{x}\right\|_{2}^{2}+\left(\boldsymbol{\alpha}-\boldsymbol{\alpha}^{t}\right)^{\mathrm{T}} \boldsymbol{D}^{\mathrm{T}}\left(\boldsymbol{D} \boldsymbol{\alpha}^{t}-\boldsymbol{x}\right)+& \\ \frac{L}{2}\left(\boldsymbol{\alpha}-\boldsymbol{\alpha}^{t}\right)^{\mathrm{T}}\left(\boldsymbol{\alpha}-\boldsymbol{\alpha}^{t}\right)=P_{t}\left(\boldsymbol{\alpha}, \boldsymbol{\alpha}^{t}\right) \end{aligned} $

(34)

方程的解为：

$ \boldsymbol{\alpha}^{t+1}=\arg \min \frac{L}{2}\left\|\boldsymbol{\alpha}-\theta\left(\boldsymbol{\alpha}^{t}\right)\right\|_{2}^{2}+l\|\boldsymbol{\alpha}\|_{1} $

(35)

$ \theta\left(\boldsymbol{\alpha}^{t}\right)=\boldsymbol{\alpha}^{t}-\frac{1}{L} \boldsymbol{D}^{\mathrm{T}}\left(\boldsymbol{D} \boldsymbol{\alpha}^{t}-\boldsymbol{x}\right), l$为一较小参数。

为了加速算法的收敛速度，算法改进了迭代点序列，取代了之前使用两个点{α^t, α^t-1}的线性组合，改进的表达式为：

$ \boldsymbol{\alpha}^{t}=\boldsymbol{\alpha}^{t}+\frac{\mu^{t}-1}{\mu^{t+1}}\left(\boldsymbol{\alpha}^{t}-\boldsymbol{\alpha}^{t-1}\right) $

(36)

式中，μ^t为正向序列，需满足μ^t≥ t+1 /2。

根据上述4种算法可知，这些算法是为了提高优化逼近算法的效率而提出的。如Elad等^[52]提出了一种平行坐标下降迭代算法，该算法求解了线性最小平方非二次正则化问题。Donoho等^[53]受置信传播算法的启发，改进了迭代阈值算法，提出了一种估计消息传播算法，将稀疏下采样问题等价于凸优化问题去求解。Becker等^[54]在Nesterov一阶光滑框架下提出了一种广义的Nesterov算法，增加了求解模型的效率和灵活性。随后，Becker等^[55]又在此基础上重新构建了另一广义凸锥模型的求解模板，该模板采用最优一阶方法，解决了原优化问题二次曲线公式的对偶问题，即解决了相关类型的大规模压缩传感重建问题。

2.4 同伦算法

同伦算法^[56-61]的核心思想起源于拓扑学，主要求解非线性方程组问题，该算法通过跟踪路径从而求得复杂方程组的解，是一种大范围的收敛算法。对于稀疏表示问题，同伦算法的提出是求解带有l₁范数的最小二乘问题^[56]，近年来，相继提出基于卷积稀疏表示的同伦算法，如最小角度回归^[57]、正交匹配追踪和多面型脸追踪^[58]等算法。对比最小角度回归和正交匹配追踪两种算法，同伦算法通过从有效集中加上或减去元素，有效连续地更新稀疏解，目前，基于同伦思想的l₁范数最小化稀疏表示模型的求解算法主要有拉索同伦法^[59]、基追踪去噪同伦法^[57]和范数迭代重加权同伦法^[61]3种。

拉索同伦算法是为了求解(P₁), (P₁)为：

$ \left(P_{1}\right) : \operatorname{argmin}\|\boldsymbol{\alpha}\|_{1} 使得\boldsymbol{x=D \alpha} $

(37)

$ \hat{\boldsymbol{\alpha}}=\arg \min _{\boldsymbol{\alpha}} \lambda\|\boldsymbol{\alpha}\|_{1}使得\|\boldsymbol{x-D \alpha}\|_{2}^{2} \leqslant \varepsilon $

(38)

通过在参数l_{2, 1}大范围下降的情形下，跟踪所有同伦解路径。在选取合适的参数值的条件下式(9)等价于式(37)，通过改变λ值，式(9)的解收敛到式(37)的解。

根据凸优化基本思想可知，零向量必须是子梯度的解。在给定任意λ值的条件下，可以得到关于α的式(9)的子梯度：

$ \frac{\partial L}{\partial \boldsymbol{\alpha}}=-\boldsymbol{D}^{\mathrm{T}}(\boldsymbol{x}-\boldsymbol{D} \boldsymbol{\alpha})+\lambda \partial\|\boldsymbol{\alpha}\|_{1} $

(39)

式中，第一项D^T(x-Dα)叫做残差向量；λ为一参数；子梯度∂‖ α ‖₁为：

$ \partial\|\boldsymbol{\alpha}\|_{1}=\left\{\theta \in R^{N} | \begin{array}{l}{\theta_{i}=\operatorname{sgn}\left(\boldsymbol{\alpha}_{i}\right), \boldsymbol{\alpha}_{i} \neq 0} \\ {\theta_{i} \in[-1, 1], \boldsymbol{\alpha}_{i}=0}\end{array}\right\} $

(40)

定义Λ和u分别为α的支撑集和α在支撑集Λ上的符号序列，考虑到式(14)需满足KKT(Karush- Kuhn-Tucker)条件，得到式(9)的两个相等价的条件：

$ \left\{ {\begin{array}{*{20}{l}} {\mathit{\boldsymbol{D}}_\mathit{\Lambda }^{\rm{T}}(\mathit{\boldsymbol{x}} - \mathit{\boldsymbol{D\alpha }}) = \lambda \mathit{\boldsymbol{u}}}\\ {{{\left\| {\mathit{\boldsymbol{D}}_{{\mathit{\Lambda }^c}}^{\rm{T}}(\mathit{\boldsymbol{x}} - \mathit{\boldsymbol{D\alpha }})} \right\|}_\infty } \le \lambda } \end{array}} \right. $

(41)

式中，Λ^c为支撑集Λ的补集。当减小λ的值到λ-τ时，τ为步长并取较小值，须满足下式：

$ \begin{array}{l}{\boldsymbol{D}_{\mathit{\Lambda }}^{\mathrm{T}}(\boldsymbol{x}-\boldsymbol{D} \boldsymbol{\alpha})+\tau \boldsymbol{D}_{\mathit{\Lambda }}^{\mathrm{T}} \boldsymbol{D} \boldsymbol{\delta}=(\lambda-\tau) \boldsymbol{u}} \\ {\|\boldsymbol{p}+\tau \boldsymbol{q}\|_{\infty} \leqslant \lambda-\tau}\end{array} $

(42)

式中，$ \boldsymbol{p}_{i}=\boldsymbol{d}_{i}^{\mathrm{T}}(\boldsymbol{D} \boldsymbol{\alpha}-\boldsymbol{x}) ; \hat{\boldsymbol{x}}_{p}=\arg \min\limits_{\boldsymbol{x}_{p}} b_{p}\left(\boldsymbol{x}_{p}\right)$；δ为更新方向。同伦算法中，步长τ和第l阶的更新方向δ_l两个参数最为重要。而δ_l为：

$ \boldsymbol{\delta}_{l}=\left\{\begin{array}{l}{\boldsymbol{D}_{\mathit{\Lambda }}^{\mathrm{T}} \boldsymbol{D}_{\mathit{\Lambda }} \boldsymbol{\delta}_{l}} \\ {\boldsymbol{0}}\end{array}\right. $

(43)

同论算法通过跟踪同伦解的路径计算步长τ，得到临界点。可以通过计算τ_l^*=min(τ_l⁺, τ_l^-)得到临界点的最小步长，τ_l⁺和τ_l^-为：

$ \tau _l^ + = {\min\limits_{i \in {\mathit{\Lambda }^c}}}{\left( {\frac{{\lambda - {\mathit{\boldsymbol{p}}_i}}}{{1 - \mathit{\boldsymbol{x}}_i^{\rm{T}}{\mathit{\boldsymbol{X}}_\mathit{\Lambda }}{\mathit{\boldsymbol{\delta }}_l}}}, \frac{{\lambda + {\mathit{\boldsymbol{p}}_i}}}{{{\bf{1}} + \mathit{\boldsymbol{x}}_i^{\rm{T}}{\mathit{\boldsymbol{X}}_\mathit{\Lambda }}{\mathit{\boldsymbol{\delta }}_l}}}} \right)_ + } $

(44)

$ \tau _l^ - = \mathop {\min }\limits_{i \in \mathit{\Lambda }} {\left( {\frac{{ - \mathit{\boldsymbol{\alpha }}_l^i}}{{\mathit{\boldsymbol{\delta }}_l^i}}} \right)_ + } $

(45)

式中，$\boldsymbol{p}_{i}=\boldsymbol{x}_{i}^{\mathrm{T}}\left(\boldsymbol{y}-\boldsymbol{x}_{i} \boldsymbol{\alpha}_{l}^{i}\right) ; \tau_{l}^{+} $和τ_l^-都代表最小步长，前者表示支撑集中的有效元素，后者表示减少非零元素到零。

稀疏解通过下式更新：

$ \boldsymbol{\alpha}_{l+1}=\boldsymbol{\alpha}_{l}+\tau_{l}^{*} \boldsymbol{\delta} $

(46)

同伦算法通过反复计算步长τ和更新方向δ更新同伦解以及相关的支撑集和符号序列，直到满足条件‖p‖_∞=0，式(37)得到解。

3 讨论

综上所述，笔者介绍了5种主流的稀疏表示模型和4种比较常用的求解稀疏模型的优化算法如表 1所示。从压缩感知中引出最早的稀疏表示理论，其核心作用是降维，即用最少的数据去线性表示庞大的原始数据。要想得到稀疏解，该模型必须是在l₀正则化项下才能求出，否则模型就失去最初的意义。由于l₀范数下的模型非凸且全局不可导，所以贪婪算法在求解上述模型时只能得到一个全局近似解，且算法收敛较慢，这导致了上述模型的局限性，阻碍了稀疏表示理论在工程技术上的发展。随着后续专家们在数学理论上的突破，即证明了l₁范数下的稀疏模型只要满足约束等距条件，就可以和l₀正则化项下的稀疏模型等价，这加速了稀疏表示理论在各应用上的发展，尤其是在模式识别、计算机视觉和图像处理领域中的突破，也为研究人员开辟了另一条解决问题的思路。不过大多数稀疏表示和字典学习算法仍着重于使用l₀范数或l₁范数正则化来获得稀疏解，对基于l_p、l₂和l_{2, 1}范数正则化的稀疏模型研究略少，间接导致了稀疏表示理论在某一段时间的沉寂。或许，只有当所有的稀疏表示模型被研究透彻时，其他应用研究可能才会到达另一高度。

4 结束语

近年来，稀疏表示已经成为一种基本工具，嵌入到各种学习系统中，应用范围也广泛地扩展到机器学习和计算机视觉领域，并且取得了巨大的进步和前所未有的成就。本文总结和介绍了各种稀疏表示模型以及相对应的求解算法，从理论上分析了它们之间的关系，对稀疏表示理论前景的发展总结如下。

1) 稀疏表示方法的有效性和效率并不能完全满足实际应用的需要。特别是稀疏表示的复杂性极大地影响了大规模问题的求解，这也是近些年来，稀疏表示理论在其他工程领域中应用缓慢的根本原因。因此，为稀疏表示开发出一种高效且快速的优化求解算法仍然是主要挑战，这不仅有助于性能改进，同时也极大地扩展了稀疏表示理论在其他领域的应用范围。

2) 单一的模型建立以及复杂的求解算法同样也成为阻碍稀疏表示理论的发展，这是因为针对各个领域中的不同问题，文中总结的5种不同范数正则化下的模型几乎无法满足现实需求，所以相对应的优化求解算法也就失去了意义，因此，如何更深层次地挖掘稀疏表示理论，完善稀疏表示模型，是今后值得继续研究的问题。

3) 基于深度学习的研究成为计算机视觉领域压倒性的趋势。当前深度学习技术的主要局限性是昂贵的训练成本，在基于稀疏表示的研究并未完全转移到学习框架的情况下，如何将成熟的稀疏表示方法全面引入深度学习框架同样值得研究。

从应用角度来看，稀疏表示理论主要应用在计算机视觉和图像处理等工程领域，尤其在图像去噪、特征提取、异常检测和人脸识别等领域表现出色。在遥感领域中，依然停留在简单的应用上，如遥感图像融合和遥感图像分类两大研究方向，在遥感图像中异常检测和目标分割等方向研究较少，如何将稀疏表示理论与更多的遥感应用相结合，是今后重点研究的方向。本文提出的评论和分析可以帮助和激励更多的研究人员提出并完善稀疏表示理论和方法。