5.4. 线性压缩感知观测

5.4.1. 感知矩阵的设计

感知矩阵的设计需要满足如下条件.

零空间条件

设有信号空间 \({\mathbb X}^n\) 中的任意不同信号 \({\bm x}_1, {\bm x}_2 \in {\mathbb X}^n\), 感知矩阵 \({\bm A}\in{\mathbb R}^{m\times n}\), 对应的观测向量分别为 \({\bm y}_1, {\bm y}_2 \in {\mathbb Y}^m\). 若想从 \({\bm y}_1, {\bm y}_2\) 中恢复 \({\bm x}_1, {\bm x}_2\), 需保证不同信号在投影后依然不同 \({\bm y}_1 = {\bm A}{\bm x}_1 \neq {\bm y}_2 = {\bm A}{\bm x}_2\), 即 \({\bm A}({\bm x}_1 - {\bm x}_2) \neq 0\), 亦即 \({\bm x}_1 - {\bm x}_2 \notin {\mathcal N}({\bm A})\). 这一性质可以通过矩阵的 Spark, 零空间性质等表达.

Theorem 5.3

对于 \(\forall {\bm y}\in {\mathbb Y}^m\), 当且仅当 \({\rm Spark}({\bm A}) > 2k\) 时, 最多存在一个 \(k\) 稀疏信号 \({\bm x}\in {\mathbb X}^n_k\), 使得 \({\bm y} = {\bm A}{\bm x}\) 成立.

该定理的证明参见文献 [5].

下面介绍矩阵的零空间性质 (Null Space Property, NSP) [5].

Definition 5.4 (零空间性质 (Null Space Property, NSP))

设矩阵 \({\bm A} = [{\bm a}_1, {\bm a}_2, \cdots, {\bm a}_n]\in {\mathbb R}^{m\times n}\) , \({\bm a}_i \in {\mathbb R}^m, i=1,2,\cdots, n\). 若 \(\forall {\bm v}\in{\mathcal N}({\bm A})\), 满足

(5.8)\[\|{\bm v}_{\mathbb K}\|_1 < \|{\bm v}_{\bar{\mathbb K}}\|_1 \]

其中, \({\mathbb K} \subset {\mathbb N}\), \({\mathbb N}=\{1, 2, \cdots, n\}\), \(\bar{\mathbb K}\) 为 \({\mathbb K}\) 在 \({\mathbb N}\) 中的补集, \({\rm card}({\mathbb K}) \leq k\). 则称矩阵 \(\bm A\) 满足 \(k\) 阶 零空间性质 (Null Space Property, NSP).

下面介绍矩阵的零空间性质 (Null Space Property, NSP) 的另一种定义 [6].

Definition 5.5 (零空间性质 (Null Space Property, NSP))

设矩阵 \({\bm A} = [{\bm a}_1, {\bm a}_2, \cdots, {\bm a}_n]\in {\mathbb R}^{m\times n}\) , \({\bm a}_i \in {\mathbb R}^m, i=1,2,\cdots, n\). 若 \(\forall {\bm v}\in{\mathcal N}({\bm A})\), \(\exists C>0\) 满足

(5.8)\[\|{\bm v}_{\mathbb K}\|_2 \leq C\frac{\|{\bm v}_{\bar{\mathbb K}}\|_1}{\sqrt{k}} \]

其中, \({\mathbb K} \subset {\mathbb N}\), \({\mathbb N}=\{1, 2, \cdots, n\}\), \(\bar{\mathbb K}\) 为 \({\mathbb K}\) 在 \({\mathbb N}\) 中的补集, \({\rm card}({\mathbb K}) \leq k\). 则称矩阵 \(\bm A\) 满足 \(k\) 阶 零空间性质 (Null Space Property, NSP).

有限等距性质

RIP 被广泛用于压缩感知 (Compressive Sensing, CS) 中 [7] . 在CS中, 感知矩阵 (\({\bm A} = {\bm \Phi}{\bm \Psi}\) ) 是否满足RIP条件直接决定了重构信号质量. 在CS中, 矩阵 \({\bm A}\) 的有限等距常数定义为

Definition 5.6 (有限等距常数 (Restricted Isometry Constant))

设 \({\bm A} = [{\bm a}_1, {\bm a}_2, \cdots, {\bm a}_n]\in {\mathbb R}^{m\times n}\) , \({\bm a}_i \in {\mathbb R}^m, i=1,2,\cdots, n\). 对于每个整数 \(k\in [1, n]\) , 定义矩阵 \({\bm A}\) 的 \(k\) 阶有限等距常数为满足下式的最小的数 \(\delta_k\)

(5.9)\[(1-\delta_k)\|{\bm x}\| \leq \|{\bm A}{\bm x}\| \leq (1+\delta_k)\|{\bm x}\| \]

其中, \({\bm x} \in {\mathbb R}^n_k\) 为 \(k\) 稀疏信号.

更一般地, 设 \(0 < \beta < \gamma <+\infty\),

(5.10)\[{\beta}\|{\bm x}\| \leq \|{\bm A}{\bm x}\| \leq {\gamma}\|{\bm x}\| \]

其中, \({\bm x} \in {\mathbb R}^n_k\) 为 \(k\) 稀疏信号.

矩阵 \({\bm A}\) 具有 有限等距特性 (Restricted Isometry Property, RIP) [6] 是指对于足够大的 \(k\) 和充分小的 \(\delta_k\) , 矩阵 \({\bm A}\) 满足 式.5.9. 式.5.9 表明, 矩阵 \({\bm A}\) 对信号 \(\bm x\) 投影前后的长度仅有微小的改变. 即RIP特性保证了来自矩阵 \(\bm A\) 的投影可以保持两个信号 \({\bm x}_1, {\bm x}_2\) 间的距离, 式.5.9 可以等价地表示为

(5.11)\[(1-\delta_k)\|{\bm x}_1-{\bm x}_2\| \leq \|{\bm A}({\bm x}_1-{\bm x}_2)\| \leq (1+\delta_k)\|{\bm x}_1-{\bm x}_2\|. \]

一个矩阵 \(\bm A\) 以很高概率满足 RIP, 也就保证了稀疏信号 \(\bm x\) 可以被以高概率重构.

提示

对于 式.5.10 中的矩阵 \(\bm A\), 用 \(\sqrt{2/(\beta + \gamma)}\) 乘以 \(\bm A\), 则有 \(\sqrt{2/(\beta + \gamma)}{\bm A}\) 满足 式.5.9, 其中, \(\delta_k = (\beta-\gamma)/(\beta+\gamma)\). 更多内容参见 有限等距性 小节.

相干性/一致性条件

Definition 5.7 (相干性/一致性 (Coherence))

设 \({\bm A} = [{\bm a}_1, {\bm a}_2, \cdots, {\bm a}_n]\in {\mathbb R}^{m\times n}\) , \({\bm a}_i \in {\mathbb R}^m, i=1,2,\cdots, n\). 对于每个整数 \(k\in [1, n]\) , 定义矩阵 \({\bm A}\) 的一致性为

(5.12)\[\mu({\bm A}) = \max _{1 \leq i \neq j \leq N}\left|\left\langle{\frac{\bm{a}_{i}}{\|\bm{a}_{i}\|_2}}, \frac{\bm{a}_{j}}{\|\bm{a}_{j}\|_2}\right\rangle\right| = \max _{1 \leq i \neq j \leq N}\frac{\left|\left\langle \bm{a}_{i}, \bm{a}_{j}\right\rangle\right|}{\|\bm{a}_{i}\|_2\|\bm{a}_{j}\|_2} \]

Theorem 5.8

对于任意矩阵 \({\bm A}\) 有

(5.13)\[{\rm Spark}({\bm A}) \geq 1+\frac{1}{\mu({\bm A})} \]

Theorem 5.9

对于矩阵 \({\bm A}\) , 若

(5.14)\[k < \frac{1}{2}\left(1+\frac{1}{\mu({\bm A})}\right) \]

则对于 \(\forall {\bm y}\in{\mathbb R}^m\) , 最多存在一个 \(k\) 稀疏信号, 满足 \({\bm y} = {\bm A}{\bm x}\).

稳定性

Definition 5.10 (C稳定系统)

设有感知系统 \({\mathcal F} = {\bm A}\in{\mathbb R}^{m\times n} : {\mathbb R}^n \rightarrow {\mathbb R}^m\), 重构算法 \({\mathcal G}: {\mathbb R}^m \rightarrow {\mathbb R}^n\), \(m \leq n\) . 若对于任意 \(k\) 稀疏信号 \({\bm x}\in {\mathbb R}^n_k\) 和误差向量 \({\bm e} \in {\mathbb R}^m\), 有

(5.15)\[\|{\mathcal G}({\mathcal F}({\bm x}) + {\bm e}) - {\bm x}\|_2 = \|{\mathcal G}({\bm A}{\bm x} + {\bm e}) - {\bm x}\|_2 \leq C\|{\bm e}\|_2 \]

则称系统 \(\{{\mathcal F}={\bm A}, {\mathcal G}\}\) 是 \(C\) 稳定的.

该定义说明, 对于 \(C\) 稳定的系统, 若观测存在很小的误差或者对观测施加小量的噪声, 重建质量不会受到大的影响, RIP 保证了上述性质的成立.

讨论

• NSP 不容易证明, 且容易受噪声影响;

• RIP 比 NSP 更为严格和鲁棒 1 .

5.4.2. 感知矩阵的构造

5.4.3. 常见感知矩阵

Footnotes

1

参见文献 [5] p24.