|
|
相关文章推荐
|
一直单身的台灯 · 【压缩感知合集7】压缩感知RIP有限等距性： ...· 1 周前 · |
|
|
细心的荒野 · 深圳医院今年新增床位1200张· 1 月前 · |
|
|
私奔的卤蛋 · 国家社科基金艺术学重大项目“中国纪录片的历史 ...· 1 月前 · |
|
|
乐观的芒果 · 【最全】18种扫弦汇总，四大节奏型全在这，练 ...· 2 月前 · |
|
|
一身肌肉的菠萝 · 應用Kano品質模式探討使用者短視頻體驗魅力 ...· 2 月前 · |
|
|
豪情万千的杨桃 · [科普园地]-平顶山市科学技术局· 3 月前 · |
\boldsymbol{A} =\boldsymbol{\Phi}\boldsymbol{X} = \boldsymbol{\Phi}\boldsymbol{\Psi} \boldsymbol{Y} = \boldsymbol{\Theta}\boldsymbol{Y}
A
=
Φ
X
=
Φ
Ψ
Y
=
Θ
Y
3
其中 \left(1-\delta_{K}\right)\|\boldsymbol{c}\|_{2}^{2} \leq\left\|\boldsymbol{\Theta}_{T} \boldsymbol{c}\right\|_{2}^{2} \leq\left(1+\delta_{K}\right)\|\boldsymbol{c}\|_{2}^{2} ( 1 − δ K ) ∥ c ∥ 2 2 ≤ ∥ Θ T c ∥ 2 2 ≤ ( 1 + δ K ) ∥ c ∥ 2 2
成立，其中 \check{\boldsymbol{Y}}=\arg \min \|\boldsymbol{Y}\|_{0} \quad \text { s.t. } \quad \boldsymbol{A} = \boldsymbol{\Theta} \boldsymbol{X} Y ˇ = ar g min ∥ Y ∥ 0 s.t. A = Θ X
实现从 \left(1-\delta_{2 K}\right)\|\boldsymbol{c}\|_{2}^{2} \leq\left\|\boldsymbol{\Theta}_{T} \boldsymbol{c}\right\|_{2}^{2} \leq\left(1+\delta_{2 K}\right)\|\boldsymbol{c}\|_{2}^{2} ( 1 − δ 2 K ) ∥ c ∥ 2 2 ≤ ∥ Θ T c ∥ 2 2 ≤ ( 1 + δ 2 K ) ∥ c ∥ 2 2
成立，其中 \boldsymbol{A}=\boldsymbol{\Phi}\boldsymbol{X}=\boldsymbol{\Phi} \boldsymbol{\Psi} \boldsymbol{Y} A = Φ X = Φ Ψ Y
该过程也可以表示为信号 $ \boldsymbol{Y}$ 通过矩阵 (1-\varepsilon)\|\boldsymbol{Y}\|_{2} \leqslant\|\boldsymbol{\Theta} \boldsymbol{Y}\|_{2} \leqslant(1+\varepsilon)\|\boldsymbol{Y}\|_{2} ( 1 − ε ) ∥ Y ∥ 2 ⩽ ∥ Θ Y ∥ 2 ⩽ ( 1 + ε ) ∥ Y ∥ 2
式中的 K 阶的要求
\min \left\| \boldsymbol{\Psi}^{T} \boldsymbol{X}\right\|_{0} \\s.t. \boldsymbol{\Theta} \boldsymbol{X}=\boldsymbol{\Phi}\boldsymbol{\Psi}\boldsymbol{X}= \boldsymbol{A} min ∥ ∥ ∥ Ψ T X ∥ ∥ ∥ 0 s . t . Θ X = Φ Ψ X = A
1 发展历史
RIP
是压缩感知领域的一个重要概念，主要可以被用来分析还原算法的表现好坏。
| 年份 | 事件 | 相关论文/Reference |
|---|---|---|
| 2005 |
Emmanuel Candès、陶哲轩提出了当\delta_{2s}<1时可以保证(P0)有唯一解，并且用反证法对此问题进行了证明，大概思路是假设有两个解，会发现从
RIP性质
的不等式中可以得出这两个解是相等的。
|
Candes, E.; Tao, T. (2005). Decoding by linear programming. IEEE Transactions on Information Theory. 59(8):4203-4215. |
| 2006 | Emmanuel Candès、陶哲轩和David Donoho证明了在已知信号稀疏性的情况下，可能凭借较采样定理所规定更少的采样数重建原信号，这一理论也是压缩感知的基石。 | Candès, E.; Romberg, J. K.; Tao, T. (2006). Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics. 59 (8): 1207–1223. |
| 2007 |
Richard Baraniuk等人提出了一种简单的技术，用于验证压缩感知基础的随机矩阵的
RIP性质
。
|
Baraniuk, R.G., Davenport, M.A., DeVore, R.A., & Wakin, M.B. (2007). A Simple Proof of the Restricted Isometry Property for Random Matrices. |
| 2008 |
Emmanuel Candès证明了当
−
1
时则可以保证
0范数
和
1范数
等价。零范数求解为NP-hard问题，在此前提下将其转化为1范数求最优化问题，这时是个凸优化，对于求解很有帮助。
|
Candes, E. (2008). The restricted isometry property and its implications for compressedsensing. Comptes Rendus Mathematique. 346(8-9): 589-592. |
2 本篇的主要思路
前文有一定的简单介绍和逻辑分析（ 【压缩感知合集6】压缩感知为什么可以恢复信号；为什么需要满足稀疏性条件、RIP条件、矩阵不相关等限制条件才可以恢复信号的逻辑分析 ）这一篇文章我们详细理解一下，这个条件的必要性
主要的问题如下
-
RIP性质是什么？ -
为什么需要
RIP性质？ -
为什么介绍
K阶RIP性质后恢复K稀疏信号又要用2K阶RIP性质？
3
RIP性质
定义
RIP性质
：有限等距性质（Restricted Isometry Property，RIP）
不同文献上表达RIP的方式不同，一般主要有以下几种（为了不影响理解我将论文中使用的一些字母进行了替换，换成了我前文例子中的字母表示，但是不影响他对性质的具体定义）：
中文定义一
(1-\delta)\|\boldsymbol{Y}\|_{2}^{2} \leqslant\left\|\boldsymbol{\Theta}{\boldsymbol{Y}}\right\|_{2}^{2} \leqslant(1+\delta)\|\boldsymbol{Y}\|_{2}^{2} ( 1 − δ ) ∥ Y ∥ 2 2 ⩽ ∥ Θ Y ∥ 2 2 ⩽ ( 1 + δ ) ∥ Y ∥ 2 2 其中 \left(1-\delta_{K}\right)\|\boldsymbol{c}\|_{2}^{2} \leq\left\|\boldsymbol{\Theta}_{T} \boldsymbol{c}\right\|_{2}^{2} \leq\left(1+\delta_{K}\right)\|\boldsymbol{c}\|_{2}^{2} ( 1 − δ K ) ∥ c ∥ 2 2 ≤ ∥ Θ T c ∥ 2 2 ≤ ( 1 + δ K ) ∥ c ∥ 2 2
成立，其中 \check{\boldsymbol{Y}}=\arg \min \|\boldsymbol{Y}\|_{0} \quad \text { s.t. } \quad \boldsymbol{A} = \boldsymbol{\Theta} \boldsymbol{X} Y ˇ = ar g min ∥ Y ∥ 0 s.t. A = Θ X
实现从 \left(1-\delta_{2 K}\right)\|\boldsymbol{c}\|_{2}^{2} \leq\left\|\boldsymbol{\Theta}_{T} \boldsymbol{c}\right\|_{2}^{2} \leq\left(1+\delta_{2 K}\right)\|\boldsymbol{c}\|_{2}^{2} ( 1 − δ 2 K ) ∥ c ∥ 2 2 ≤ ∥ Θ T c ∥ 2 2 ≤ ( 1 + δ 2 K ) ∥ c ∥ 2 2
成立，其中 \boldsymbol{A}=\boldsymbol{\Phi}\boldsymbol{X}=\boldsymbol{\Phi} \boldsymbol{\Psi} \boldsymbol{Y} A = Φ X = Φ Ψ Y
该过程也可以表示为信号 $ \boldsymbol{Y}$ 通过矩阵 (1-\varepsilon)\|\boldsymbol{Y}\|_{2} \leqslant\|\boldsymbol{\Theta} \boldsymbol{Y}\|_{2} \leqslant(1+\varepsilon)\|\boldsymbol{Y}\|_{2} ( 1 − ε ) ∥ Y ∥ 2 ⩽ ∥ Θ Y ∥ 2 ⩽ ( 1 + ε ) ∥ Y ∥ 2
李坤，马彩文，李艳，陈萍. 压缩感知重构算法综述[J]. 红外与激光工程，2013，42(z1)：225-232.
最多人引用的出处
英文原文：
整理归纳翻译，并改变字母如下：
\left(1-\delta_{K}\right)\|\boldsymbol{c}\|^{2} \leq\left\|\boldsymbol{F}_T \boldsymbol{c}\right\|^{2} \leq\left(1+\delta_{K}\right)\|\boldsymbol{c}\|^{2} ( 1 − δ K ) ∥ c ∥ 2 ≤ ∥ F T c ∥ 2 ≤ ( 1 + δ K ) ∥ c ∥ 2式中的 K 阶的要求
CandesE, Tao T. Decoding by linear programming. IEEE Transactions on InformationTheory, 2005,59(8):4203-4215.
整理归纳翻译，并改变字母如下：
对于每一个整数
\left(1-\delta_{K}\right)\|\boldsymbol{Y}\|_{\ell_{2}}^{2} \leq\|\boldsymbol{\Theta} \boldsymbol{Y}\|_{\ell_{2}}^{2} \leq\left(1+\delta_{K}\right)\|\boldsymbol{Y}\|_{\ell_{2}}^{2}
(
1
−
δ
K
)
∥
Y
∥
ℓ
2
2
≤
∥
Θ
Y
∥
ℓ
2
2
≤
(
1
+
δ
K
)
∥
Y
∥
ℓ
2
2
如果一个向量最多有
K
稀疏的。
CandesE. The restricted isometry property and its implications for compressedsensing[J]. Comptes Rendus Mathematique, 2008,346(8-9): 589-592.
英文定义三
整理归纳翻译，并改变字母如下：
这个简化问题（上所叙述的精确恢复问题）充分必要条件是：对于任意和 1-\varepsilon \leq \frac{\|\boldsymbol{\Theta} \boldsymbol{v}\|_{2}}{\|\boldsymbol{v}\|_{2}} \leq 1+\varepsilon 1 − ε ≤ ∥ v ∥ 2 ∥ Θ v ∥ 2 ≤ 1 + ε
BaraniukR G. Compressive sensing. IEEE Signal Processing Magazine, 2007,24(4): 118-121.
定义之间的分析比较
三种中文
RIP
定义中：
-
其实前两种是等价的。
-
中文定义一定义中要注意要求 δ 。整个式子可以视为信号跟传感矩阵的相似程度，也就是做转换q前后的能量，要被
RIP限制住。4
RIP性质到底是对哪一个矩阵的约束？RIP性质的定义解释完毕，虽然在例子当中都有翻译和换算成统一的符号。在这里再进行一下总结和描述。符号 含义 维度 属性 \begin{aligned} &\boldsymbol{Y} \thicksim \text{sparse}:\\ &\qquad\boldsymbol{Y}\in \boldsymbol{R}^{N\times 1},\;\forall p\in(0,2),\; \exists R>0: \\ &\qquad\|\boldsymbol{Y}\|_{p} \equiv\left(\sum_{i=0}^{N-1}\left|y_{i}\right|^{p}\right)^{1 / p} \leqslant R \\ &\boldsymbol{Y} \thicksim \text{Strict K-sparse}:\\ &\qquad\boldsymbol{Y}\in \boldsymbol{R}^{N\times 1},\quad\|\boldsymbol{Y}\|_{0} =K\\ &\boldsymbol{\Theta} \thicksim \text{K-RIP}:\\ &\qquad \exists\; \delta_{K} \in (0,1),\; \text{For} \; \forall \; \boldsymbol{Y} \thicksim \text{K-sparse} ,\;\boldsymbol{Y} \in \boldsymbol{R}^{N\times 1} \\ &\qquad\left(1-\delta_{K}\right)\|\boldsymbol{Y}\|^{2} \leq\left\|\boldsymbol{\Theta}\boldsymbol{Y}\right\|^{2} \leq\left(1+\delta_{K}\right)\|\boldsymbol{Y}\|^{2} \end{aligned} Y ∼ sparse : Y ∈ R N × 1 , ∀ p ∈ ( 0 , 2 ) , ∃ R > 0 : ∥ Y ∥ p ≡ ( i = 0 ∑ N − 1 ∣ y i ∣ p ) 1 / p ⩽ R Y ∼ Strict K-sparse : Y ∈ R N × 1 , ∥ Y ∥