Sparse Reconstruction with Compressed Sensing: Difference between revisions
Molokaicat (talk | contribs) |
Molokaicat (talk | contribs) No edit summary |
||
Line 22: | Line 22: | ||
Sensing matrix <math>\Phi</math>must satisfy RIP i.e. Random Gaussian or Bernoulli matrixies satisfies (cite) | Sensing matrix <math>\Phi</math>must satisfy RIP i.e. Random Gaussian or Bernoulli matrixies satisfies (cite) | ||
let <math>[ N ] = \{ 1, \dots , N \} </math>be an index set <math>[N]</math> enumerates the columns of <math>\Phi</math> and <math>x</math> <math>\Phi</math> is an under determined systems with infinite solutions since <math> | let <math>[ N ] = \{ 1, \dots , N \} </math>be an index set <math>[N]</math> enumerates the columns of <math>\Phi</math> and <math>x</math> <math>\Phi</math> is an under determined systems with infinite solutions since <math>M \ll N</math>. Why <math>l_2</math> norm does not work | ||
What is compression is synonymous with to the sparsity. | What is compression is synonymous with to the sparsity. |
Revision as of 15:00, 28 November 2021
Author: Ngoc Ly (SysEn 5800 Fall 2021)
Compressed Sensing (CS)
Compressed Sensing summary here
Introduction
often not really sparse but approximately sparse
for is a Random Gaussian or Bernoulli matrix
are the observed y samples
noise vector k e k 2 ≤ η
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 (cite)
let be an index set enumerates the columns of and is an under determined systems with infinite solutions since . Why norm does not work
What is compression is synonymous with to the sparsity.
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
Gel’fand n-width
Errors E ( S, Φ, D )
Definition Mutual Coherence
Let , the mutual coherence is defined by:</math>
We want a small µ A because it will be close ot the normal matrix, which
Then
Define the threashholding operators as: selects the best-k term approximation for some k
will satisfies RIP
Stopping criterion is
Algorithm IHT
- Initialize
- output
- Set
- While halting criterion false do
- end while
- return:
Numerical Example
Iterative Hard Thresholding IHT
Check if satisfies RIP with mutual coherence.
Applications
Distributed Systems peer-to-peer network
Collaborative sensor networks for energy savings.
Distributed Systems where Energy needs to be preserved.
Conclusion
References
- ↑ 2. Emmanuel J. Candès and Terence Tao. Decoding by linear programming. IEEE Trans. Inf. Theory, 51(12):4203–4215, 2005.
- ↑ 5. Stephen A. Vavasis. Elementary proof of the spherical section property for random matrices. Univer-sity of Waterloo, Waterloo,Technical report, 2009.
- ↑ 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.
- ↑ 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.
- ↑ 8. D. L. Donoho. Compressed sensing. 52:1289–1306, 2006.
- ↑ 12. E. J. Candes, J. Romberg, and T. Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. 52:489–509, 2006.
- ↑ 16. Giulio Coluccia, Chiara Ravazzi, and Enrico Magli. Compressed sensing for dis- tributed systems, 2015.
- ↑ 17. Mohammed Rostami. Compressed sensing with side information on feasible re- gion, 2013.
- ↑ 18. Thomas Blumensath and Mike E. Davies. Iterative hard thresholding for com- pressed sensing. May 2008.