Sparse Reconstruction with Compressed Sensing

Author: Ngoc Ly (SysEn 5800 Fall 2021)

Introduction

sub module goal

The goal of compressed sensing is to solve the 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 $x$ for the same set of compressive measurements $y$. The objective is to reconstruct a vector $x$ in a given of measurements $y$ and a sensing matrix A. Instead of taking a large number of high-resolution measurements and discarding the majority of them, consider taking far fewer random measurements and reconstructing the original $x$ with high probability from its sparse representation.

sub modual

Begin with a linear equation $y=Ax+e$, where $A\in \mathbb {R} ^{M\times N}$ is a sensing matrix that must be obtained and will result in either exact or approximated optimum solution depending on how it is chosen, $x\in \mathbb {R} ^{N}$ is a signal vector with at most $k$-sparse entries, which means $x$ has $k$ non-zero entries, $[N]=\{1,\dots ,N\}$be an index set, $y\in \mathbb {R} ^{M}$ is a compressed measurement vector, $[M]=\{1,\dots ,M\}$, $e\in \mathbb {R} ^{M}$ is a noise vector and assumed to be bounded $\|e\|_{2}\leq \eta$ if it exists, and $M\ll N$.

sub module sparsity

A vector $x$ is said to be $k$-sparse in $\mathbb {R} ^{N}$ if it has at most $k$ nonzero coefficients. The support of $x$ is $supp(x)=\{i\in [N]:x_{i}\neq 0\}$, and $x$ is a $k$-sparse signal when the cardinality $|supp(x)|\leq k$. The set of $k$-sparse vectors is denoted by $\Sigma _{k}=\{x\in \mathbb {R} ^{N}:\|x\|_{0}\leq k\}$. Consequently, there are ${\binom {N}{k}}$ different subsets of $k$-sparse vectors. If a random $k$-sparse $x$ is drawn uniformly from $\Sigma _{k}$, its entropy $\log {\binom {N}{k}}$ is approximately equivalent to $k\log {\frac {N}{k}}$ bits are required for compression of $\Sigma _{k}$ ~cite(Measurements vs Bits).

The idea is to search for the sparsest $x\in \Sigma _{k}$ from the measurement vector $y\in \mathbb {R} ^{M}$ and a sensing matrix $A\in \mathbb {R} ^{M\times N}$ with $M\ll N$. If the number of linear measurements is at least twice as its sparsity $x$, i.e., $M\geq 2k$, then there exists at most one signal $x\in \Sigma _{k}$ that satisfies the constraint $y=Ax$ and produce the correct result for any $x\in \Sigma _{k}$ [coluccia2015 book7]. Hence, the reconstruction problem can be formulated as an $l_{0}$"norm" program.

${\hat {x}}={\underset {x\in \Sigma _{k}}{argmin}}\|x\|_{0}\quad s.t.\quad y=Ax$

This optimization problem minimizes the number of nonzero entries of $x$ subject to the constraint $y=Ax$, that is to find the sparsest element in the affine space $\{x\in \mathbb {R} ^{N}:Ax=y\}$ [2019 book33]. It turns out to be a combinatorial optimization problem, which is NP-Hard because it includes all possible sets of $k$-sparse out of $[N]$. Furthermore, if noise is present, the recovery is unstable [Buraniuk "compressed sensing"].

Restricted Isometry Property (RIP)

A matrix $A$ is said to satisfy the RIP of order $k$ if for all $x\in \Sigma _{k}$ has a $\delta _{k}\in [0,1)$. A restricted isometry constant (RIC) of $A$ is the smallest $\delta _{k}$ satisfying this condition [2019 book38, coluccia2015 book7].

$(1-\delta _{k})\|x\|_{2}^{2}\leq \|Ax\|_{2}^{2}\leq (1+\delta _{k})\|x\|_{2}^{2}$

Under projections through matrix $A$, the restricted isometry property allows $k$-sparse vectors to have unique measurement vectors $y$. If $A$ meets RIP, then $A$ does not send two distinct $k$-sparse $x\in \Sigma _{k}$ to the same measurement vector $y$, indicating that $x$ is a unique solution under RIP.

If the matrix $A\in {\mathcal {R}}^{M\times N}$ satisfies the RIP condition of order $2k$ and the constant $\delta _{2k}\in [0,1)$, there are two distinct $k$-sparse vectors in $\Sigma _{2k}$. When they are equal, the restricted isometry property holds. If $A$ is a $2k$-order RIP matrix, it means that no two $k$-sparse vectors are mapped to the same measurement vector $y$ by $A$. In other words, when working with sparse vectors, the RIP ensures that the columns of $A$ are nearly orthonormal. Furthermore, $A$ is an approximately norm-preserving function, which means that it preserves its distance when mapping for $k$-sparse signals for all or more as $\delta _{k}$ approaches zero. [Candes, Romberg, Tao[4]] demonstrate that if $x$ is $k$-sparse, and $A$ satisfies the RIP of order $2k$ with RIP-constant $\delta _{2k}<{\sqrt {(}}2)-1$, then $l_{1}$ gives a unique sparse solution. The $l_{1}$ convex optimization problem is the same as the solution to the $l_{0}$ program and can solve by the Linear Program [2019 book38, coluccia2015 book7]. Hence, the $\ell _{1}$ reconstruction problem is as followed which can be solved by basis pursuit.

${\hat {x}}={\underset {x\in \Sigma _{k}}{argmin}}\|x\|_{1}\quad s.t.\quad y=Ax$

Theory

Two main things need to be considered when recovering $x$

• (1) The design of the sensing matrix

• (2) The recovery algorithm

Sensing Matrix

Although the sensing matrix $A$ satisfies RIP of order $k$ in some situations, confirming a given matrix $A$ meets RIP's criteria is NP-hard in general. As a result, designing an efficient sensing matrix is critical. These sensing matrices are responsible for signal compression at the encoder end and accurate or approximate reconstruction at the decoder end. For signal compression, different sensing matrices are utilized in compressed sensing. There are random, deterministic, structural, and optimized sensing matrices are used in compressed sensing