Sparse Reconstruction with Compressed Sensing: Difference between revisions
Molokaicat (talk | contribs) |
Molokaicat (talk | contribs) |
||
Line 223: | Line 223: | ||
Checking <math>\Phi</math> satisfies RIP is NP-complete in general, must use shortcuts. | Checking <math>\Phi</math> satisfies RIP is NP-complete in general, must use shortcuts. | ||
We will do some hacking to make use it works. If <math>\Phi</math> is a gaussian random matrix then we know that it satisfies RIP with high probability and IHT will reconstruct the the true signal find <math>x</math> with <math>l_1</math> minimization. (cite Ca, Ro, ta, Robust uncertainty exact signal) (cite Blu, Davies IHT for CS) Other words we don't really know in general if <math>\Phi</math> satisfies RIP in general unless we solve an NP-complete problem; however, we can cross our fingers <math>\Phi</math> satisfies RIP with a high probability and not go through all the work for total verification of RIP. | We will do some hacking to make use it works. If <math>\Phi</math> is a gaussian random matrix then we know that it satisfies RIP with high probability and IHT will reconstruct the the true signal find <math>x</math> with <math>l_1</math> minimization. (cite Ca, Ro, ta, Robust uncertainty exact signal) (cite Blu, Davies IHT for CS) Other words we don't really know in general if <math>\Phi</math> satisfies RIP in general unless we solve an NP-complete problem; however, we can cross our fingers that <math>\Phi</math> satisfies RIP with a high probability because it's Gaussian and not go through all the work for total verification of RIP. | ||
Iterative Hard Thresholding IHT | Iterative Hard Thresholding IHT |
Revision as of 22:09, 2 December 2021
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.
Three big groups of algorithms are:[1]
Optimization methods: includes minimization i.e. Basis Pursuit, and quadratically constraint minimization i.e. basis pursuit denoising.
greedy include Orthogonal matching pursuit and Compressive Sampling Matching Pursuit (CoSaMP)
thresholding-based methods such as Iterative Hard Thresholding(IHT) and Iterative Soft Thresholding, Approximate IHT or AM-IHT, and many more.
More cutting-edge methods include dynamic programming.
We will cover one, i.e. IHT. WHY IHT THEN? Basis pursuit, matching pursuit type algorithms belong to a more general class of iterative thresholding algorithms. [2] So IHT seems like the ideal place to start. If everything compliment with RIP, then IHT has fast convergence.
Introduction
often not really sparse but approximately sparse
for a Random Gaussian or Bernoulli matrix
are the observed y samples
noise vector
sub modual 1
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 A which is the number of measurements required for standard compressive sensing to recover with high probability.
let be an index set enumerates the columns of and . is an under determined systems with infinite solutions since . Why norm won't give sparse solutions, where asl norm will return a sparse solution.
submodual 2
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.
sub modual 3
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.
sub modual 4
, which is an combinatorial NP-Hard problem. Hence, if noise is presence the recovery is not stable. [Buraniuk "compressed sensing"]
From Results of Candes, Romberg, Tao, and Donoho
If satisfies RIP and is sparse the gives sparse solutions and is a unique. It is equivalent to convex optimization problem and can solve by Linear 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>
Welch bound > [3] >
We want a small because it will be close to the normal matrix, which satisfies RIP. Also, will be needed for the step size for the following IHT.
Need to make the connection of Coherence to RIP and RIC.
Algorithm IHT
The convex program mentioned in introduction has an equivalent nonconstraint optimization program.
(cite IT for sparse approximations) ??? [3]. In statistics we call the regularization LASSO with as the regularization parameter. This is the closest convex relaxation to the first program menttioned in the introduction.[The Benefit of Group Sparsity]
Then
Define the threashholding operators as: selects the best-k term approximation for some k
Stopping criterion is iff RIC [4]
- Initialize
- output
- Set
- While Stopping criterion false do
- end while
- return:
Numerical Example
Check if satisfies RIP Checking satisfies RIP is NP-complete in general, must use shortcuts.
We will do some hacking to make use it works. If is a gaussian random matrix then we know that it satisfies RIP with high probability and IHT will reconstruct the the true signal find with minimization. (cite Ca, Ro, ta, Robust uncertainty exact signal) (cite Blu, Davies IHT for CS) Other words we don't really know in general if satisfies RIP in general unless we solve an NP-complete problem; however, we can cross our fingers that satisfies RIP with a high probability because it's Gaussian and not go through all the work for total verification of 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.
Netflix problem
Conclusion
References
- ↑ 1.0 1.1 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.
- ↑ Cite error: Invalid
<ref>
tag; no text was provided for refs named:4
- ↑ 3.0 3.1 3.2 3.3 17. Mohammed Rostami. Compressed sensing with side information on feasible re- gion, 2013.
- ↑ 4.0 4.1 18. Thomas Blumensath and Mike E. Davies. Iterative hard thresholding for com- pressed sensing. May 2008.
- ↑ https://doi.org/10.1007/s00041-008-9035-z
- ↑ 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.
- ↑ 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.