Sparse Reconstruction with Compressed Sensing

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search

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. We introduce Compressed Sensing and then focus on reconstruction by Iterative Hard Thresholding (IHT).

Introduction

often not really sparse but approximately sparse

for is a Random Gaussian or Bernoulli matrix

are the observed y samples

noise vector

s.t.

How can we reconstruct x from The goal is to reconstruct given and

Sensing matrix must satisfy RIP i.e. Random Gaussian or Bernoulli matrixies satisfies

let be an index set enumerates the columns of and . is an under determined systems with infinite solutions since . Why norm does not work


The problem formulation is to recover sparse data


The support of is we say is sparse when

We are interested in the smallest , i.e.

Before we get into RIP lets talk about RIC

Restricted Isometry Constant (RIC) is the smallest that satisfies the RIP condition introduced by Candes, Tao

Random Gaussian and Bernoulli satisfies RIP

RIP defined as

Let satisfy RIP, Let be an index set For is a restriction on denoted by to k-sparse s.t. RIP is satisfied the i.e. and where the columns of is indexed by

In search for a unique solution we have the following optimization problem. , which is an NP-Hard.

From Results of Candes, Romberg, Tao, and Donoho

If satisfies RIP and is sparse the has a unique solution. The equivalent convex program to the program.


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 , the mutual coherence is defined by:</math>


We want a small because it will be close to the normal matrix, which satisfies RIP


Algorithm IHT

The convex program mentioned in introduction has an equivalent nonconstraint optimization program.

Not exactly for CS need to modify.!!!!

Then

Define the threashholding operators as: selects the best-k term approximation for some k

Stopping criterion is

  • Initialize
  • output
  • Set
  • While Stopping criterion false do
    • end while
  • return:

Numerical Example

Check if 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.

MRIs of children and pets because they will move around.

Conclusion

References

[1]


[2]

[3]

[4]


[5]


[6]


[7]

[8]

[9]

  1. 2. Emmanuel J. Candès and Terence Tao. Decoding by linear programming. IEEE Trans. Inf. Theory, 51(12):4203–4215, 2005.
  2. 5. Stephen A. Vavasis. Elementary proof of the spherical section property for random matrices. Univer-sity of Waterloo, Waterloo,Technical report, 2009.
  3. 6. Angshul Majumdar. Compressed sensing for engineers. Devices, circuits, and systems. CRC Press, Taylor & Francis Group, Boca Raton, FL, 2019. Includes bibliographical references and index.
  4. 7. Simon Foucart and Holger Rauhut. A mathematical introduction to compressive sens- ing. Applied and numerical harmonic analysis. Birkhäuser, New York [u.a.], 2013.
  5. 8. D. L. Donoho. Compressed sensing. 52:1289–1306, 2006.
  6. 12. E. J. Candes, J. Romberg, and T. Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. 52:489–509, 2006.
  7. 16. Giulio Coluccia, Chiara Ravazzi, and Enrico Magli. Compressed sensing for dis- tributed systems, 2015.
  8. 17. Mohammed Rostami. Compressed sensing with side information on feasible re- gion, 2013.
  9. 18. Thomas Blumensath and Mike E. Davies. Iterative hard thresholding for com- pressed sensing. May 2008.