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. We introduce Compressed Sensing and then focus on reconstruction.
Introduction
sub module goal
The goal of compressed sensing is to interact with an underdetermined linear system in which the number of variables is much greater than the number of observations, resulting in an infinite number of signal coefficient vectors for the same set of compressive measurements . As a result, additional information is necessary for to recover from . The objective is to reconstruct a vector in a given of measurements and a sensing matrix A. Instead of taking a large number of high-resolution measurements and discarding the majority of them, consider taking way fewer random measurements and reconstructing the original with high probability from its sparse representation.
sub modual
Begin with a linear equation , where is a sensing matrix that must be obtained and will result in either exact or approximated optimum solution depending on how it is chosen, is a signal vector with at most -sparse entries, which means has non-zero entries, be an index set, is a compressed measurement vector, , is a noise vector, and .
The goal of compressed sensing is to being with the under determined linear system
, Where
for
How can we reconstruct x from
The goal is to reconstruct given and
Considerably fewer random measurements and reconstruct the original with high probability from its sparse representation instead of taking a large number of high-resolution measurements and discarding the majority of them. being a random matrix
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.
Notation =
often not really sparse but approximately sparse
for Sensing matrix a Random Gaussian or Bernoulli matrix
are the observed y samples
noise vector
put defn of p norm here
where is the sparsifying matrix and are coeficients
sub module sparsity
A vector is said to be -sparse in if it has at most nonzero coefficients. The support of is , and is a -sparse signal when . The set of all -sparse vectors is denoted by . Consequently, there are different subsets of -sparse vectors. If a random -sparse is drawn uniformly from , its entropy is approximately equivalent to bits are required for compression of ~cite(Measurements vs Bits).
The goal is to search for the sparsest given the meassurment and the constraint matrix .
This is antiquated to find the in the set
This searching problem can be formulated to the following program
Another words we are interested in the smallest , i.e.
sub module
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 module zero norm program
, which is an combinatorial NP-Hard problem. Hence, if noise is presence the recovery is not stable. [Buraniuk "compressed sensing"]
sub modual RIP
RIP defined as
satisfies RIP of order if for satisfies for inequalaty
- TODO switch s to k
If satisfies RIP then doesn't send two distinct k-sparse to the same measurment vector . Anothers words is a unique solution under RIP.
sub module RIP matracies
If a sensing matrix must satisfy RIP, then the number of measurements is required recover with high probability.
sub module RIC
Restricted Isometry Constant (RIC) is the smallest in
if i.e. twise the sparsity, then there exists an unique such that
.
for is k-sparse and and satisfies RIP of order RIC then the program can have to relaxed convex form program.
If satisfies RIP and is sparse the gives sparse solutions and is a unique. It is equivalent to the following convex optimization problem and can solve by Linear Program.
sub problem 1 norm program
From Results of Candes, Romberg, Tao, and Donoho
Theory
Two things need to be considered when recovering
- (1) The design of the sensing matrix
- (2) The recovery algorithm
Sensing Matrix
Check if satisfies RIP Checking satisfies RIP is combinatorial hard in general so it's unreasonable to ask a computer to verify a matrix satisfies RIP. In order to get around this problem, we need an understanding of what matrices satisfy RIP and recover with high probability.
- Random Sensing matrices: Gaussian, Bernoulli, Rademacher
- Deterministic Sensing Matrices: binary, bipolar, ternary, Vandermond
- Structural Sensing Matrices: Toeplitz, Circulant, Hadamard
- Optimized Sensing Matrices: (Parkale, Nalbalwar, Sensing Matrices in Compressed Sensing)
Are some examples. Different sensing matrices are more suited for different problems, but in general, we want to use an alternative to Gaussian because it reduces the computational complexity.
Verification of the Sensing matrix
Definition Mutual Coherence
Let , the mutual coherence is defined by:</math>
- TODO switch s to k
Welch bound > [1] > is the coherence between and 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.
- TODO switch s to k
Algorithms
Three big groups of algorithms are:[2]
- Optimization methods: includes minimization i.e. Basis Pursuit, and quadratically constraint
minimization i.e. basis pursuit denoising.
- Greedy methods: 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. [3] So IHT seems like the ideal place to start. If everything compliment with RIP, then IHT has fast convergence.
Algorithm IHT
The convex program mentioned in introduction has an equivalent nonconstraint optimization program.
(cite IT for sparse approximations) ??? [1]. 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
sub modual
Define the threashholding operators as: selects the best-k term approximation for some k
Stopping criterion is iff RIC [4]
- Input
- output
- Set
- While Stopping criterion false do
- end while
- return:
is a Adjoint matrix i.e. the transpost of it's cofactor.
Numerical Example
Applications
Netflix problem
Many applications, such as medical imaging, deal with massive amounts of data, making it challenging to achieve optimal results in the past. These data sets are required to consider restructuring in accordance with a specific methodology.
Conclusion
Referencse
- ↑ Jump up to: 1.0 1.1 1.2 Cite error: Invalid
<ref>
tag; no text was provided for refs named:1
- ↑ Cite error: Invalid
<ref>
tag; no text was provided for refs named:0
- ↑ Cite error: Invalid
<ref>
tag; no text was provided for refs named:4
- ↑ Cite error: Invalid
<ref>
tag; no text was provided for refs named:2
- ↑ D. L. Donoho, “Compressed sensing,” vol. 52, pp. 1289–1306, 2006, doi: 10.1109/tit.2006.871582.
- ↑ E. J. Candès and T. Tao, “Decoding by linear programming,” IEEE Trans. Inf. Theory, vol. 51, no. 12, Art. no. 12, 2005, doi: 10.1109/TIT.2005.858979.
- ↑ D. L. Donoho, “Compressed sensing,” vol. 52, pp. 1289–1306, 2006, doi: 10.1109/tit.2006.871582.
- ↑ T. Blumensath and M. E. Davies, “Iterative Hard Thresholding for Compressed Sensing,” May 2008.
- ↑ S. Foucart and H. Rauhut, A mathematical introduction to compressive sensing. New York [u.a.]: Birkhäuser, 2013.
- ↑ R. G. Baraniuk, “Compressive Sensing [Lecture Notes],” IEEE Signal Processing Magazine, vol. 24, no. 4, Art. no. 4, 2007, doi: 10.1109/MSP.2007.4286571.