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}$ .

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}$ . 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\}$ . 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 .

$(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, and Tao