ヌル空間特性

圧縮センシングにおいて、ヌル空間特性は、緩和法を用いたスパース信号の再構成に必要な十分条件を与える。「ヌル空間特性」という用語は、コーエン、ダーメン、デヴォアに由来する。^[1]ヌル空間特性は実際には検証が難しい場合が多く、圧縮センシングの分野では、制約付き等長性特性の方がより新しい条件である。 ${\displaystyle \ell _{1}}$

の技術${\displaystyle \ell _{1}}$ -リラクゼーション

非凸最小化問題 、 ${\displaystyle \ell _{0}}$

${\displaystyle \min \limits _{x}\|x\|_{0}}$ 、​ ${\displaystyle Ax=b}$

圧縮センシングにおける標準的な問題である。しかし、 -最小化は一般にNP困難であることが知られている。 ^[2]そのため、-緩和法は、 -ノルムを用いた信号再構成の困難さを回避するために用いられることがある。-緩和法では、 ${\displaystyle \ell _{0}}$ ${\displaystyle \ell _{1}}$ ${\displaystyle \ell _{0}}$ ${\displaystyle \ell _{1}}$ ${\displaystyle \ell _{1}}$

${\displaystyle \min \limits _{x}\|x\|_{1}}$ 、​ ${\displaystyle Ax=b}$

問題の代わりに が解かれます。この緩和は凸であり、したがって線形計画法の標準的な手法に適応可能であることに注意してください。これは計算上望ましい特性です。当然のことながら、緩和が問題と同じ答えを与えるのはどのような場合か知りたいものです。零空間性は、一致を保証する一つの方法です。 ${\displaystyle \ell _{0}}$ ${\displaystyle \ell _{1}}$ ${\displaystyle \ell _{0}}$

意味

複素行列は 、 のすべての添字集合 に対して次が成り立つ場合、の順序のヌル空間特性を持ちます。 すべての に対して次が成り立ちます。 ${\displaystyle m\times n}$ ${\displaystyle A}$ ${\displaystyle s}$ ${\displaystyle S}$ ${\displaystyle s=|S|\leq n}$ ${\displaystyle \|\eta _{S}\|_{1}<\|\eta _{S^{C}}\|_{1}}$ ${\displaystyle \eta \in \ker {A}\setminus \left\{0\right\}}$

回復条件

次の定理は、与えられた-スパースベクトルの回復可能性に関する必要十分条件を与える。定理の証明は標準的なものであり、ここで示す証明はHolger Rauhut ^{[3]による要約である。}${\displaystyle s}$ ${\displaystyle \mathbb {C} ^{n}}$

${\displaystyle {\textbf {Theorem:}}}$ を複素行列とする 。すると、すべての-スパース信号は、 の-緩和問題の唯一の解となり、かつ が の位数で零空間性を満たす場合に限ります。 ${\displaystyle A}$ ${\displaystyle m\times n}$ ${\displaystyle s}$ ${\displaystyle x\in \mathbb {C} ^{n}}$ ${\displaystyle \ell _{1}}$ ${\displaystyle b=Ax}$ ${\displaystyle A}$ ${\displaystyle s}$

${\displaystyle {\textit {Proof:}}}$ 順方向については、 と はの線形性により異なるベクトルであり、したがって一意性により、期待どおりに となることが分かります。逆方向については、 を-スパースとし、 およびとなる別の（必ずしも-スパースではない）ベクトルとします。（非ゼロ）ベクトル を定義し、それが の零空間に存在することに注意してください。のサポートを とすると、三角不等式の基本的適用から という結果が導かれ、の最小性が確立されます。${\displaystyle \eta _{S}}$ ${\displaystyle -\eta _{S^{C}}}$ ${\displaystyle A(-\eta _{S^{C}})=A(\eta _{S})}$ ${\displaystyle A}$ ${\displaystyle \|\eta _{S}\|_{1}<\|\eta _{S^{C}}\|_{1}}$ ${\displaystyle x}$ ${\displaystyle s}$ ${\displaystyle z}$ ${\displaystyle s}$ ${\displaystyle z\neq x}$ ${\displaystyle Az=Ax}$ ${\displaystyle \eta =x-z}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle \|x\|_{1}\leq \|x-z_{S}\|_{1}+\|z_{S}\|_{1}=\|\eta _{S}\|_{1}+\|z_{S}\|_{1}<\|\eta _{S^{C}}\|_{1}+\|z_{S}\|_{1}=\|-z_{S^{C}}\|_{1}+\|z_{S}\|_{1}=\|z\|_{1}}$ ${\displaystyle x}$ ${\displaystyle \square }$

参考文献

1. Cohen, Albert; Dahmen, Wolfgang; DeVore, Ronald (2009-01-01). 「圧縮センシングと最良𝑘項近似」. Journal of the American Mathematical Society . 22 (1): 211– 231. doi : 10.1090/S0894-0347-08-00610-3 . ISSN  0894-0347.
2. Natarajan, BK (1995-04-01). 「線形システムのスパース近似解」. SIAM J. Comput . 24 (2): 227– 234. doi :10.1137/S0097539792240406. ISSN  0097-5397. S2CID  2072045.
3. Rauhut, Holger (2011).圧縮センシングと構造化ランダム行列. CiteSeerX 10.1.1.185.3754 .