Sparse Reconstruction with Compressed Sensing

Author: Ngoc Ly (SysEn 5800 Fall 2021)

Compressed Sensing (CS)

Compressed Sensing summary here

Compression is synonymous with sparsity. So when we talk about compression we are actually referring to the sparsity.

Introduction

$x\in \mathbb {R} ^{N}$often not really sparse but approximately sparse

$\Phi \in \mathbb {R} ^{M\times N}$for i$M\ll N$s a Random Gaussian or Bernoulli matrix

$y\in \mathbb {R} ^{M}$are the observed y samples

$e\in \mathbb {R} ^{M}$noise vector $\|e\|_{2}\leq \eta$

s.t.

How can we reconstruct x from $y=\Phi x+e$

The goal is to reconstruct $x\in \mathbb {R} ^{N}$given $y$ and $\Phi$

Sensing matrix $\Phi$must satisfy RIP i.e. Random Gaussian or Bernoulli matrixies satisfies (cite)

let $[N]=\{1,\dots ,N\}$be an index set $[N]$ enumerates the columns of $\Phi$ and $x$ $\Phi$ is an under determined systems with infinite solutions since $M\ll N$. Why $l_{2}$ norm does not work

The problem formulation is to recover sparse data $\mathbf {x} \in \mathbb {R} ^{N}$

The support of $\mathbf {x}$ is $supp(\mathbf {x} )=\{i\in [N]:\mathbf {x} _{i}\neq 0\}$ we say $\mathbf {x}$ is $k$ sparse when $|supp(x)|\leq k$

We are interested in the smallest $supp(x)$ , i.e. $min(supp(x))$

Before we get into RIP lets talk about RIC

Restricted Isometry Constant (RIC) is the smallest $\delta _{|s}\ s.t.\ s\subseteq [N]$that satisfies the RIP condition introduced by Candes, Tao

Random Gaussian and Bernoulli satisfies RIP

RIP defined as

$(1-\delta _{s})\|x\|_{2}^{2}\leq \|\Phi x\|_{2}^{2}\leq (1+\delta _{s})\|x\|_{2}^{2}$

Let $\Phi \in \mathbb {R} ^{M\times N}$ satisfy RIP, Let $[N]$ be an index set For $s$ is a restriction on $\mathbf {x}$ denoted by $x_{|s}$ $x\in \mathbb {R} ^{N}$ to $s$ k-sparse $\mathbf {x}$ s.t. RIP is satisfied the $s=supp(\mathbf {x} )$ i.e. $s\subseteq [N]$and $\Phi _{|s}\subseteq \Phi$ where the columns of $\Phi _{|s}$ is indexed by $i\in S$

In search for a unique solution we have the following $l_{0}=|supp(x)|$ optimization problem. $\mathbf {\hat {s}} ={\underset {s}{argmin}}\|\mathbf {s} \|_{0}\quad s.t.\quad \mathbf {y} =\Phi \mathbf {s}$, which is an NP-Hard.

From Results of Candes, Romberg, Tao, and Donoho

If $\Phi$ satisfies RIP and $\mathbf {y}$ is sparse the $l_{0}$ has a unique solution. The equivalent $l_{1}$ convex program to the $l_{0}$ program. $\mathbf {\hat {s}} ={\underset {s}{argmin}}\|\mathbf {s} \|_{1}\quad s.t.\quad \mathbf {y} =\Phi \mathbf {s}$

�

x i , i f i ∈ S

( x | S ) i =

0 otherwise

RIP defined as

( 1 − δ s )k x k 22 ≤ k Φx k 22 ≤ ( 1 + δ s )k x k 22

3 Lemmas Page 267 Blumensath Davies IHT for CS

Lemma 1(Blumensath, Davis 2009 Iterative hard thresholding for compressed

sensing), For all index sets Γ and all Φ for which RIP holds with s = | Γ | that is

s = supp ( x )

1k Φ Γ T k 2 ≤

q

1 + δ | Γ | k y k 2

( 1 − δ | Γ | )k x Γ k 22 ≤ k Φ Γ T Φ Γ x Γ k 22 ≤ ( 1 + δ | Γ | )k x Γ k 22

and

k( I − Φ Γ T Φ Γ )k 2 ≤ δ | Γ | k x Γ k 2

SupposeΓ ∩ Λ = ∅

k Φ Γ T Φ Λ ) x Λ k 2 ≤ δ s k x Λ k 2

Lemma 2 (Needell Tropp, Prop 3.5 in CoSaMP: Iterative signal recovery

from incomplete and inaccurate √ samples)

If Φ satisfies RIP k Φx s k 2 ≤ 1 + δ s k x s k 2 , ∀ x s : k x s k 0 ≤ s, Then ∀ x

k Φx k 2 ≤

p

1 + δ s k x k 2 +

p

1 + δ s

k x k 1

sqrts

Lemma 3 (Needell Tropp, Prop 3.5 in CoSaMP: Iterative signal recovery

from incomplete and inaccurate samples)

Let x s be the best s-term approximation to x. Let x r = x − x s Let

y = Φx + e = Φx s + Φx r + e = Φx s + ẽ

If Φ satisfies RIP for sparsity s, then the norm of error ẽ is bounded by

k ẽ k 2 ≤

p

1 + δ s k x − x s k 2 +

p

1 + δ s

k x − x s k 1

√

+ k e k 2

s

∀ x

Theory

Verification of the Sensing matrix

Gel’fand n-width

Errors E ( S, Φ, D )

Definition Mutual Coherence

Let $\Phi \in R^{M\times N}$, the mutual coherence $\mu _{\Phi }$ is defined by:</math>

$\mu _{\Phi }={\underset {i\neq j}{\frac {|\langle a_{i},a_{j}\rangle |}{\|a_{i}\|\|a_{j}\|}}}$

We want a small $\mu _{\Phi }$ because it will be close to the normal matrix, which satisfies RIP

Algorithm IHT

$z_{v}^{(n)}=\nabla f_{v}(x^{(n)})=-\Phi _{v}^{T}(\mathbf {y} -\Phi \mathbf {x} )$ Then $x^{n+1}={\mathcal {H}}\left(\mathbf {x} ^{(n)}-\tau \sum _{j\in N}^{N}z_{v}^{(n)}\right)$

Define the threashholding operators as: ${\mathcal {H}}_{s}[\mathbf {x} ]={\underset {z\in \sum _{s}}{argmin}}\|x-\Phi \mathbf {x} \|_{2}$ selects the best-k term approximation for some k

Stopping criterion is $\|y-\Phi \mathbf {x} ^{(n)}\|_{2}\leq \epsilon$

• Initialize $\Phi ,\mathbf {y} ,\mathbf {e} \ {\mbox{with}}\ \mathbf {y} =\mathbf {\Phi } \mathbf {x} |\mathbf {e} and{\mathfrak {M}}$
• output $IHT(\mathbf {y} ,\mathbf {\Phi } ,{\mathfrak {M}})$
• Set $x^{(0)}=\mathbf {0}$
• While halting criterion false do
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^{(n+1)} \leftarrow \mathcal{H}_{s} \left[ x^{(n) + \Phi^T (\mathbf{y} - \mathbf{\Phi x}^{(n)})}\right]}}
  • $n\leftarrow n+1$
  • end while
• return: $IHT(\mathbf {y} ,\mathbf {\Phi } ,{\mathfrak {M}})\leftarrow \mathbf {x} ^{(n)}$

Numerical Example

Check if $\Phi$ satisfies RIP

Iterative Hard Thresholding IHT

Applications

Distributed Systems peer-to-peer network

Collaborative sensor networks for energy savings.

Distributed Systems where Energy needs to be preserved.