Sparse Reconstruction with Compressed Sensing

Author: Ngoc Ly (SysEn 5800 Fall 2021)

Introduction

$x\in \mathbb {R} ^{N}$often not really sparse but aproximently 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$k e k 2 ≤ η

s.t.

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

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

Sensing matrix $\Phi$must satisfy RIP i.e. Random Gaussian or Bernoulli ma-

traxies satsifies (cite)

let $[N]=\{1,\dots ,N\}$be an index set

$[N]$ enumerates the colums of $\Phi$ and $x$

$\Phi$ is an underdetermined systems with infinite solutions. Why $l_{2}$ norm does

not work

What is compression is sunomunus with to the sparcity.

The problem formulation is to recover sparse data x 0 ∈ R N $\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))$

Restricted isometry property (RIP) Introduced by Candes, Tao

Random Gausian and Bernoulli satsifies RIP

Let Φ ∈ R M × N $\Phi \in \mathbb {R} ^{M\times N}$ satsify RIP, Let $[N]$ be an index set

Before we get into RIP lets talk about RIC

Resiricted Isometry Constant (RIC) is the smallest δ | s s.t. s ⊆ [ N ] $\delta _{|s}\ s.t.\ s\subseteq [N]$that satsi-

fies the RIP condition

For $s$ is a restrciton on $\mathbf {x}$ denoted by $x_{|s}$ $x\in \mathbb {R} ^{N}$ to $s$ k-sparse $\mathbf {x}$ s.t. RIP is

satisified the s = | Γ | i.e. s ⊆ [ N ] and Φ | s ⊆ Φ where the columns of Φ | s is

indexed by i ∈ 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 Φ statisfies RIP for sparcity 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

Gel’fend n-width

Errors E ( S, Φ, D )

Definition Mutual Coherence

LetA ∈ R M × N , themutualcoherenceµ A isde f inedby :

µ A =

|h a i , a j i|

k a i kk a j k

i 6 = j

We want a small µ A because it will be close ot the normal matrix, which

will satisfie RIP

Algorithm IHT

• Initalize $\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}})$

• While halting criterion false do
• $x^{(n+1)}\leftarrow \P _{{\mathfrak {M}}\left[x^{(n)+\Phi ^{*}(\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

Basis Persuit

Iterative Hard Thresholding IHT

Solver

2