Sparse Representation of the Signal: A Brief Introduction and Some Discussion

Sparse Vector and Sparse Representation

对矩阵$\boldsymbol{A}\in \mathbb{C}^{m\times n}$ 有以下是常用的7种范数¹：

• $m_1$范数：$||\boldsymbol{A}||_{m_1}=\sum_{i=1}^{m}\sum_{j=1}^{n}|a_{ij}|.$
• F范数²：$||\boldsymbol{A}||_F=\sqrt{\sum_{i=1}^{m}\sum_{j=1}^{n}|a_{ij}|^2}=\sqrt{tr(\boldsymbol{A}^H\boldsymbol{A})}.$
• M范数/最大范数：$||\boldsymbol{A}||_M=\max\{m,n\}\max_{i,j}|a_{ij}|.$
• G范数/几何平均范数：$||\boldsymbol{A}||_G=\sqrt{mn}\max_{i,j}|a_{ij}|.$
• 1范数/列和范数³：$||\boldsymbol{A}||_1=\max_{j}\sum_{i=1}^m|a_{ij}|.$
• 2范数/谱范数：$||\boldsymbol{A}||_2=\sqrt{\boldsymbol{A}^H\boldsymbol{A}\text{的最大特征值}}.$
• $\infty$范数/行和范数：$||\boldsymbol{A}||_{\infty}=\max_{i}\sum_{j=1}^n|a_{ij}|.$

¹. 矩阵的范数定义除开满足非负性，齐次性和三角不等式外，还需满足相容性: \begin{equation}\label{compatibility} \forall \boldsymbol{A},\boldsymbol{B}\in \mathbb{C}^{n\times n}, \exists || \boldsymbol{AB}||\leq ||\boldsymbol{A}||\cdot ||\boldsymbol{B}||. \end{equation} ↩

². Here, $\boldsymbol{A}^H$ means Hermitian Matrix(埃尔米特/厄米/自伴随矩阵): $\boldsymbol{A}^H=(\bar{a}_{ji})_{n\times n}$. ↩

³. p-范数并不是按照这里给出的公式定义的，而是从属于某向量范数$||\cdot||_v$导出的矩阵范数:$||\boldsymbol{A}||=\max_{\bf{x}\neq\bf{0}}\frac{||\boldsymbol{Ax}||_v}{||\boldsymbol{x}|_v}$，简称导出范数/从属范数，且满足：$||\boldsymbol{E}||=1$. ↩

Sparse Representation

一个含有大多数零元素的向量或者矩阵成为稀疏向量(sparse vector)或者稀疏矩阵(sparse matrix)。也即是：给定$K\in\mathbb{N}^+, |\boldsymbol{x}|_0 \leq K$。

给定一个向量$\boldsymbol{x}\in\mathbb{R}^n$，可以定义如下稀疏测度(sparse measure)：
\begin{equation}
\text{sparseness}(\boldsymbol{x}) = \frac{\sqrt{n} - |\boldsymbol{x}|_1/|\boldsymbol{x}|_2}{\sqrt{n} - 1}.
\end{equation}

信号向量$\boldsymbol{y}\in\mathbb{R}^m$最多可以分解为$m$个正交基$\boldsymbol{g}_k\in\mathbb{R}^m$，这些正交基的集合成为完备正交基(complete orthogonal basis)。此时，信号分解

\begin{equation}
\boldsymbol{y} = \boldsymbol{G}\boldsymbol{c} = \sum_{i=1}^{m}c_i\boldsymbol{g}_i,
\end{equation}
中的系数向量$\boldsymbol{c}$一定是非稀疏的。

若将信号向量$\boldsymbol{y}\in\mathbb{R}^m$分解为$n$个$m$维向量$\boldsymbol{a}_i\in\mathbb{R}$（其中$n>m$）的线性组合：
\begin{equation}\label{equ:overcomplete}
\boldsymbol{y} = \boldsymbol{A}\boldsymbol{x} = \sum_{i=1}^{n}x_i\boldsymbol{a}_i. \tag{1}
\end{equation}
则$\boldsymbol{a}_i\in\mathbb{R}$不可能是正交基的集合。为区别于基，这些列向量通常称为原子(atom)或框架。由于原子数大于向量空间的维数，所以称这些原子的集合是过完备的(overcompete)。过完备的原子组成的矩阵$\boldsymbol{A}=[\boldsymbol{a}_1, \cdots , \boldsymbol{a}_n]$称为字典或者库(dictionary)。

对于字典$\boldsymbol{A}\in\mathbb{R}^{m\times n}$，可以做如下假设：

• $n > m$；
• $rank(\boldsymbol{A}) = m$；
• $|\boldsymbol{a}_i|_2 = 1, i = 1, \cdots, n $；

信号过完备分解式\ref{equ:overcomplete}为欠定方程，存在无穷多组解向量$\boldsymbol{x}$。求解这种欠定方程有两种常用方法：

• 古典方法（求最小$L_2$范数解），即是：\begin{equation} \min|\boldsymbol{x}|_2, s.t. \boldsymbol{Ax} = \boldsymbol{y}. \end{equation} 这种方式的优点是：有唯一解，其物理意义为最小能量解。然而由于这种解的每个元素通常为非零值，故不符合很多实际应用的稀疏表示要求。
• 现代方法（求最小$L_0$范数解），即是：\begin{equation}\label{equ:sr} \min|\boldsymbol{x}|_0, s.t. \boldsymbol{Ax} = \boldsymbol{y}. \tag{2}\end{equation} 这种方式的优点是：很多实际应用只选择一个稀疏解向量。然而在计算上难以处理。

假定观测向量存在加性误差或者噪声，最小$L_0$范数解为：
\begin{equation}\label{equ:sa}
\min|\boldsymbol{x}|_0, s.t. |\boldsymbol{Ax - y}|_2 \leq \varepsilon, \tag{3}
\end{equation}
其中$\varepsilon$为很小的误差或者扰动。

当系数向量$\boldsymbol{x}$是稀疏向量时，信号分解$\boldsymbol{y} = \boldsymbol{Ax}$称为（信号的）稀疏分解(sparse decomposition)。其中字典矩阵$\boldsymbol{A}$的列常称为解释变量(explanatory variables)；向量$\boldsymbol{y}$称为相应变量(response variable)或目标信号；$\boldsymbol{Ax}$称为相应的线性预测；$\boldsymbol{x}$可视为目标信号相对于字典$\boldsymbol{A}$的一种表示。

因此，称式\ref{equ:sr}是目标信号$\boldsymbol{y}$相对于字典$\boldsymbol{A}$的稀疏表示(sparse representation)，而式\ref{equ:sa}称为目标信号的稀疏逼近(sparse approximation)。

稀疏表示属于线性求逆问题(linera inverse problem)。在通信和信息论中，$\boldsymbol{A}\in\mathbb{R}^{m\times N}$ 和$\boldsymbol{x}\in\mathbb{R}^N$分别代表编码矩阵和待发送的明文，观测向量$\boldsymbol{y}\in\mathbb{R}^m$则称密文。线性求逆问题便成了解码问题：即如何从密文恢复明文。

Application: Sparse Representation in Face Recognition

我们考虑close-set的人脸识别应用：假定共有$c$类目标，每一目标的脸部图像已经被向量化编码（可以是直接矩阵拉直，也可以是通过CNN进行特征提取），表示为了$m\times 1$的归一化列向量（通常我们这里的$m$为512或者128）。于是第$i$类目标的$N_i$张训练图像即可表示成$\boldsymbol{D}_i=[\boldsymbol{d}_{i,1}, \cdots , \boldsymbol{d}_{i,N_i}]\in\mathbb{R}^{m\times N}$。给定一个足够丰富的训练集$\boldsymbol{D}_{i}$，则第$i$类目标的非训练集新图片$\boldsymbol{y}$可以被表示为已知训练图像的一线性组合$\boldsymbol{y}\approx\boldsymbol{D}_i\boldsymbol{\alpha}_i$，其中$\boldsymbol{\alpha}_i$为系数向量。问题是：在实际应用中往往不知道新图像分属哪一类，而需要识别：判断该样本的属性。

于是我们已这$c$类目标的所有训练样本构造一个字典：
\begin{equation}
\boldsymbol{D} = [\boldsymbol{D}_1, \cdots, \boldsymbol{D}_c] = [\boldsymbol{d}_{1,1}, \cdots , \boldsymbol{d}_{1,N_1}, \cdots , \boldsymbol{d}_{c,1}, \cdots , \boldsymbol{d}_{c,N_c}]\in\mathbb{R}^{m\times N}
\end{equation}
其中$N = \sum_{i=1}^cN_i$。于是，待识别的人脸图像编码$\boldsymbol{y}$可以表示为线性组合：
\begin{equation}
\boldsymbol{y} = \boldsymbol{D}\boldsymbol{\alpha}_0= [\boldsymbol{d}_{1,1}, \cdots , \boldsymbol{d}_{1,N_1}, \cdots , \boldsymbol{d}_{c,1}, \cdots , \boldsymbol{d}_{c,N_c}]\begin{bmatrix} \boldsymbol{0}_{N_1} \\ \vdots \\ \boldsymbol{0}_{N_{i-1}} \\ \boldsymbol{\alpha}_i \\\boldsymbol{0}_{N_{i+1}} \\ \vdots \\ \boldsymbol{0}_{N_c} \end{bmatrix}
\end{equation}

现在，人脸识别变成了一个矩阵方程求解的问题或者线性求你问题：已知数据向量$\boldsymbol{y}$和数据矩阵$\boldsymbol{D}$，求矩阵方程$\boldsymbol{y} = \boldsymbol{D}\boldsymbol{\alpha}_0$的解向量$\boldsymbol{\alpha}_0$。需要注意的是，通常$m < N$，因为方程欠定，有无穷多解，其中最稀疏的解才是我们感兴趣的。鉴于此，问题划归为式\ref{equ:sr}的问题。

Optimization Theory for Solving Sparse Matrix Equations

$L_1$ Norm Minimization

$L_1$范数最小化也称为$L_1$线性规划或者$L_1$范数正则化最小二乘。

直接求解优化问题P0，必须筛选出系数向量$\boldsymbol{x}$中所有可能的非零元素。这个方法是不可跟踪的(untractable)或者NP hard⁴的，因为搜索空间过于庞大。

向量$\boldsymbol{x}$的非零元素指标集称为支撑集，记为$\text{supp}(\boldsymbol{x}) = \{i:x_i\neq 0\}$，支撑集的长度即是$L_0$拟范数⁵：

\begin{equation}
|\boldsymbol{x}|_0 = |supp(\boldsymbol{x})|.
\end{equation}

K-稀疏向量的集合记为$\Sigma_K = \{\boldsymbol{x}\in\mathbb{R}^N:|\boldsymbol{x}|_0\leq K\}$。若$\hat{\boldsymbol{x}}\in\Sigma_K$，则称向量$\hat{\boldsymbol{x}}$是$\boldsymbol{x}$的K-项逼近或者K-稀疏逼近。

一般地，称向量$\hat{\boldsymbol{x}}$是$\boldsymbol{x}$在$L_p$范数⁶下的K-稀疏逼近，若：
\begin{equation}
|\boldsymbol{x} - \hat{\boldsymbol{x}}|_p = \inf_{\boldsymbol{z}\in\Sigma_K}|\boldsymbol{x} - \boldsymbol{z}|_p.
\end{equation}

显然$L_0$是$L_p$范数范数的特殊形式：$|\boldsymbol{x}|_0 = \lim\limits_{p\to 0}|\boldsymbol{x}|_p^p$。由于当且仅当$p\geq 1$时$|\boldsymbol{x}|_p$为凸函数，所以$L_1$范数时最接近于$L_0$拟范数的凸目标函数。于是从最优化角度讲，称$L_1$范数是$L_0$拟范数的凸松弛[1]。因此，$L_0$拟范数最小化问题便可以转变为凸松弛的$L_1$范数最小化问题：
\begin{equation}\label{equ:l1sr}
\min_{\boldsymbol{x}}|\boldsymbol{x}|_1, s.t. \boldsymbol{y} = \boldsymbol{Ax}.\tag{4}
\end{equation}
由于$|\boldsymbol{x}|_1$是凸函数，并且约束等式$\boldsymbol{y} = \boldsymbol{Ax}$为一个仿射变换，因此这是一个凸优化问题。

存在观测噪声的情况下，等式约束可以松弛为不等式约束的最优化问题（$L_1$最小化）：
\begin{equation}\label{equ:l1sr-e}
\min_{\boldsymbol{x}}|\boldsymbol{x}|_1, s.t. |\boldsymbol{y} - \boldsymbol{Ax}| \leq \varepsilon.\tag{5}
\end{equation}

$L_1$范数下的最优化问题又称为基追踪(base pursuit, BP)。这是一个二次约束线性规划问题(quadratically constrained linear problem, QCLP)。

若$\boldsymbol{x}_1$是$L_1$的解，$\boldsymbol{x}_0$是$L_0$的解，则有[2]：
\begin{equation}
|\boldsymbol{x}_1|_1 \leq |\boldsymbol{x}_0|_1.
\end{equation}
因为$\boldsymbol{x}_1$是可行解，$\boldsymbol{x}_0$是最优解。同时$A\boldsymbol{x}_1 = A\boldsymbol{x}_0$。

同样的，式\ref{equ:l1sr-e}也有两种变形：

• （$L_1$惩罚最小化）利用$\boldsymbol{x}$是K稀疏向量的约束，将$L_1$不等式范数最小化变成$L_2$： \begin{equation}\min_{\boldsymbol{x}}\frac{1}{2}|\boldsymbol{y}- \boldsymbol{Ax}|_2^2,s.t.|\boldsymbol{x}|\leq q. \end{equation} 划归为一类二次规划(quadratic program, QP)问题。
• 利用Lagrangian乘子法，将$L_1$不等式范数最小化变成： \begin{equation}\label{equ:presu-Tik} \min_{\lambda, \boldsymbol{x}}\frac{1}{2}|\boldsymbol{y}- \boldsymbol{Ax}|_2^2 + \lambda|\boldsymbol{x}|_1. \end{equation} 划归为一类基追踪去噪(basis pursuit denoising, BPDN)问题[3]。

在基于小波变换的图像/信号重构和恢复（deconv）中，也经常会遇到基追踪去噪问题。

参数稀疏的好处主要有以下两点：

• 特征选择(Feature Selection)
• 可解释性(Interpretability)

⁴. 指所有NP问题都能在多项式时间复杂度内归约到的问题. ↩

⁵. $L_0$范数不满足范数公理中的齐次性：$|c\boldsymbol{x}|_0 = |c||\boldsymbol{x}|_0$，故严格来讲它是一种虚拟的范数，也称拟范数。 ↩

⁶. $\forall p\in\mathbb{R}^+, |\boldsymbol{x}|_p = \left( \sum_{i\in supp(\boldsymbol{x})}|x_i|^p\right)^{1/p} $. ↩

Restricted Isometry Property Condition

前文讨论了$L_1$范数最小化问题是$L_0$范数最小化某种程度的凸松弛。接下来考察两种问题的解之间的关系。
Definition 1.(Restricted Isometry Property Condition)[4][5]
若存在矩阵$\boldsymbol{A}$和K-稀疏向量$|\boldsymbol{x}|_0\leq K$，
\begin{equation}
(1-\delta_K)|\boldsymbol{x}|_2^2 \leq |\boldsymbol{A}_K\boldsymbol{x}|_2^2 \leq (1 + \delta_K)|\boldsymbol{x}|_2^2,
\end{equation}
其中$0\leq \delta_K < 1$是一个与稀疏度K有关的常数(约束等距常数, restricted isometry constants, RIC)，$\boldsymbol{A}_K$是字典矩阵$\boldsymbol{A}$的任意K列组成的子矩阵。则称矩阵$\boldsymbol{A}$满足K阶RIP条件。

当RIP条件满足时，非凸的$L_0$范数最小化问题与$L_1$范数最小化问题等价。也即是：
\begin{equation}
\min||\boldsymbol{x}||_0\,\,s.t. \boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}\overset{\text{概率为1 的}}{\underset{}{\iff}}\min||\boldsymbol{x}||_1\,\,s.t. \boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}
\end{equation}

带参数$\delta_K$的K阶RIP条件简记为$RIP(K,\delta_K)$，定义为所有使$RIP(K,\delta_K)$成立的参数$\delta$的下确界：
\begin{equation}
\delta_K = \inf\left\lbrace \delta: (1-\delta)|\boldsymbol{z}|_2^2 \leq |\boldsymbol{A}_{supp(z)}\boldsymbol{z}|_2^2 \leq (1 + \delta)|\boldsymbol{z}|_2^2, \forall |supp(z)| \leq K, \forall \boldsymbol{z}\in\mathbb{R}^{|supp(\boldsymbol{z})|} \right\rbrace
\end{equation}
显然若$\boldsymbol{A}_K$正交，则$\delta_K = 0$。于是，RIC的非零值实际上可以评价该矩阵的非正交程度。此外，由于$\boldsymbol{A}_K$的任意性，要求$\boldsymbol{A}$在每一列的能量分布投影尽可能均匀。

RIC有三个重要性质：

• 系数信号精确重构的充分条件[6]： 若字典矩阵$\boldsymbol{A}$分别满足$\delta_K, \delta_{2K}, \delta_{3K}$的RIP条件，并且： \begin{equation}\delta_K + \delta_{2K} + \delta_{3K} < 1.\end{equation} 则$L_1$范数最小化可以精确重构所有K稀疏信号。也即是，在此条件下，若无噪声存在，则K稀疏信号可以确保由$L_1$范数最小化精确恢复；并且在有噪声的情况下可以稳定估计。
• RIC与特征值的关系[7]：若字典矩阵$\boldsymbol{A}\in\mathbb{R}^{m\times n}$满足$RIP(K,\delta_K)$，则：\begin{equation}1 - \delta_K \leq \lambda_{min}(\boldsymbol{A}_K^T\boldsymbol{A}_K) \leq \lambda_{max}(\boldsymbol{A}_K^T\boldsymbol{A}_K) \leq 1 + \delta_K.\end{equation}
• 单调性[6]：若$K\leq K’$，则$\delta_K \leq \delta_{K’}$.

Reference

[1]: Tropp, J. A. . “Algorithms for simultaneous sparse approximation. Part II: Convex relaxation.” Signal Processing 86.3(2006):589-602.
[2]: David, L., and Donoho. “For most large underdetermined systems of linear equations the minimal 1-norm solution is also the sparsest solution.” Communications on Pure and Applied Mathematics (2006).
[3]: Chen, S. S. . “Atomic decomposition by basis persuit.” Siam J Sci Comp 20(1999).
[4]: Dandes, E. J. . “Near-optimal signal recovery from random projections.” Universal encoding strategies IEEE Transactions on Information Theory 52(2006).
[5]: Foucart, Simon , and M. J. Lai . “Sparsest solutions of underdetermined linear systems via $0{ extbackslashell$0q$0-minimization for $00{ extlessq{ extbackslashleq 1$0.” (2009).
[6]: Cai, T. T. , L. Wang , and G. Xu . “New bounds for restricted isometry constants.” IEEE Press (2010).
[7]: Dai, W. , and O. Milenkovic . “Subspace Pursuit for Compressive Sensing Signal Reconstruction.” IEEE Transactions on Information Theory 55.5(2009).