User:Molokaicat
MEng Systems Engineering student MS and BS in Statistics
Introduction
$x \in \mathbb{R}^N$ often not really sparse but aproximently sparse
$\Phi \in \mathbb{R} ^{M \times N}$ for $M \ll N$ is a Random Gaussian or Bernoulli matrix
$y \in \mathbb{R}^M$ are the observed $y$ samples
$e \in \mathbb{R}^M$ nosie vector $ \| e\|_2 \leq \eta$
s.t.
the support s is the smallest delta that satisfies RIP
= Introduction = <math display="inline">x \in \mathbb{R}^N</math> often not really sparse but aproximently sparse <math display="inline">\Phi \in \mathbb{R} ^{M \times N}</math> for <math display="inline">M \ll N</math> is a Random Gaussian or Bernoulli matrix <math display="inline">y \in \mathbb{R}^M</math> are the observed <math display="inline">y</math> samples <math display="inline">e \in \mathbb{R}^M</math> nosie vector <math display="inline">\| e\|_2 \leq \eta</math> s.t. How can we reconstruct <math display="inline">x</math> from <math display="inline">y = \Phi x + e</math> The goal is to reconstruct <math display="inline">x_0 \in \mathbb{R}^N</math> given <math display="inline">y</math> and <math display="inline">\Phi</math> Sensing matrix <math display="inline">\Phi</math> must satisfy RIP i.e. Random Gaussian or Bernoulli matraxies satsifies (cite) let <math display="inline">[N] = \{1, \dots , N\}</math> be an index set <math display="inline">[N]</math> enumerates the colums of <math display="inline">\Phi</math> and <math display="inline">x</math> <math display="inline">\Phi</math> is an underdetermined systems with infinite solutions. Why <math display="inline">l_2</math> norm does not work What is compression is sunomunus with to the sparcity. The problem formulation is to recover sparse data <math display="inline">x_0 \in R^N</math> The support of <math display="inline">x_0</math> is <math display="inline">supp(x_0) = \{i \in [N]: x_0(i) \neq 0 \}</math> we say <math display="inline">x</math> is <math display="inline">k</math> sparse when <math display="inline">|supp(x)| \leq k</math> We are interested in the smallest <math display="inline">supp(x)</math>, i.e. min(<math display="inline">supp(x)</math>) Restricted isometry property (RIP) Introduced by Candes, Tao Random Gausian and Bernoulli satsifies RIP Let <math display="inline">\Phi \in \mathbb{R}^{M \times N}</math> satsify RIP, Let <math display="inline">[N]</math> be an index set Before we get into RIP lets talk about RIC Resiricted Isometry Constant (RIC) is the smallest <math display="inline">\delta |_s</math> s.t. <math display="inline">s \subseteq [N]</math> that satsifies the RIP condition For <math display="inline">s</math> is a restrciton on <math display="inline">x</math> denoted by <math display="inline">x_{|s}</math> <math display="inline">x \in \mathbb{R}^N \mbox{to} s</math> k-sparse <math display="inline">x</math> s.t. RIP is satisified the s = <math display="inline">|\Gamma|</math> i.e. <math display="inline">s \subseteq [N]</math> and <math display="inline">\Phi_{|s} \subseteq \Phi</math> where the columns of <math display="inline">\Phi_{|s}</math> is indexed by <math display="inline">i \in S</math>
<math display="block">(x_{|S})_i = \left\{
\begin{array}{c c}
x_i, & if \ i \in S\\
0 & otherwise
\end{array}
\right.</math>
RIP defined as
<math display="block">(1 - \delta_s) \| x \|_2 ^2 \leq \| \Phi x \|_2^2 \leq (1 + \delta_s) \| x \|_2 ^2</math>
3 Lemmas Page 267 Blumensath Davies IHT for CS
Lemma 1(Blumensath, Davis 2009 Iterative hard thresholding for compressed sensing), For all index sets <math display="inline">\Gamma</math> and all <math display="inline">\Phi</math> for which RIP holds with <math display="inline">s = |\Gamma|</math> that is <math display="inline">s = supp(x)</math>
<math display="block">\begin{split}
&\| \Phi_\Gamma^T\|_2 \leq \sqrt{1 + \delta_{|\Gamma|}} \| y\|_2\\
&(1 - \delta_{|\Gamma|}) \| x_{\Gamma} \|_2 ^2 \leq \| \Phi_{\Gamma}^T \Phi_{\Gamma} x_{\Gamma} \|_2^2 \leq (1 + \delta_{|\Gamma|}) \| x_{\Gamma} \|_2 ^2 \\
and & \\
&\| (I - \Phi_{\Gamma}^T \Phi_{\Gamma})\|_2 \leq \delta _{|\Gamma|} \| x_{\Gamma}\|_2\\
& Suppose \Gamma \cap \Lambda = \emptyset\\
& \| \Phi_{\Gamma}^T \Phi_{\Lambda}) x_\Lambda \|_2 \leq \delta_s \| x_\Lambda \|_2
\end{split}</math>
Lemma 2 (Needell Tropp, Prop 3.5 in CoSaMP: Iterative signal recovery from incomplete and inaccurate samples)
If <math display="inline">\Phi</math> satisfies RIP <math display="inline">\| \Phi x^s\|_2 \leq \sqrt{1 + \delta_s} \| x^s\|_2</math>, <math display="inline">\forall \ x^s: \| x^s\|_0 \leq s</math>, Then <math display="inline">\forall x</math>
<math display="block">\| \Phi x\|_2 \leq \sqrt{1 + \delta_s} \| x\|_2 + \sqrt{1 + \delta_s} \frac{\| x \|_1}{sqrt{s}}</math>
Lemma 3 (Needell Tropp, Prop 3.5 in CoSaMP: Iterative signal recovery from incomplete and inaccurate samples)
Let <math display="inline">x^s</math> be the best s-term approximation to x. Let <math display="inline">x_r = x - x^s</math> Let <math display="block">y = \Phi x + e = \Phi x^s + \Phi x_r + e = \Phi x^s + \tilde{e}</math>
If <math display="inline">\Phi</math> statisfies RIP for sparcity s, then the norm of error <math display="inline">\tilde{e}</math> is bounded by
<math display="block">\| \tilde{e} \|_2 \leq \sqrt{1 + \delta_s} \| x - x^s\|_2 + \sqrt{1 + \delta_s} \frac{\| x - x^s\|_1}{\sqrt{s}} + \| e \|_2 \quad \forall x</math>
= Theory =
Gel’fend n-width
Errors <math display="inline">E(S, \Phi, D)</math>
Definition Mutual Coherence
<math display="inline">Let A \in R^{M \times N}, the mutual coherence \mu_A is defined by:</math>
<math display="block">\mu_A = \underset{i \neq j} {\frac{| \langle a_i, a_j \rangle |}{ \| a_i \| \| a_j \|}}</math>
We want a small <math display="inline">\mu_A</math> because it will be close ot the normal matrix, which will satisfie RIP
= Numerical Example =
Basis Persuit
Iterative Hard Thresholding IHT
Solver