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 $x$ for the same set of compressive measurements $y$. As a result, additional information is necessary for $x$ to recover from $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 way 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in \mathbb{R}^{N}} is a signal vector with at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} sparse entries, which means Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} has Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} non-zero entries, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [ N ] = \{ 1, \dots , N \} } be an index set, $y\in \mathbb {R} ^{M}$ is a compressed measurement vector, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [ M ] = \{ 1, \dots , M \} } , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e \in \mathbb{R}^{M}} is a noise vector, and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M \ll N} .

The goal of compressed sensing is to being with the under determined linear system Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y = \Phi x + e} , Where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi \in \mathbb{R}^{M \times N}} for $M\ll N$ How can we reconstruct x from The goal is to reconstruct Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in \mathbb{R}^N} given Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi} Considerably fewer random measurements and reconstruct the original Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [ N ] = \{ 1, \dots , N \} } be an index set $[N]$ enumerates the columns of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} . Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi} is an under determined systems with infinite solutions since Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M \ll N} . Why Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell_2} norm won't give sparse solutions, where asl $\ell _{1}$ norm will return a sparse solution.

Notation =

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in \mathbb{R}^N} often not really sparse but approximately sparse

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{x} \in \mathbb{R}^{N}}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi \in \mathbb{R}^{M \times N}} for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M \ll N} Sensing matrix a Random Gaussian or Bernoulli matrix

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y \in \mathbb{R}^M} are the observed y samples

$e\in \mathbb {R} ^{M}$noise vector Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \| e \|_2 \leq \eta}

put defn of p norm here

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = \Psi \alpha} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Psi} is the sparsifying matrix and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} are coeficients

sub module sparsity

A vector Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} is said to be $k$ sparse in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}^N} if it has at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} nonzero coefficients.

The support of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{x}} is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle supp(\mathbf{x}) = \{i \in [N] : \mathbf{x}_i \neq 0 \}} , and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{x}} is a $k$-sparse signal when $|supp(x)|\leq k$

The set of all k-sparse vectors is denoted by $\Sigma _{k}=\{x:\|x\|_{0}\leq k\}$.

Consequently there is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \binom{N}{k}} different subsets of k-sparse vectors. If we draw uniformaly a random k-sparse $x$ from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma_k} has the entropy Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log \binom{N}{k} \approx k \log (N/k)} bits are needed for compression of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma_k} ~cite(Measurements vs Bits)

The goal is to search for the sparsest Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in \Sigma_k} given the meassurment Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} and the constraint matrix Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi} .

This is antiquated to find the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \min \|x\|_0} in the set $\{x\in \mathbb {R} ^{N}:\Phi x=y\}$

This searching problem can be formulated to the following $\ell _{0}$ program

Another words we are interested in the smallest $supp(x)$ , i.e. $min(supp(x))$

sub module

Let $\Phi \in \mathbb {R} ^{M\times N}$ satisfy RIP, Let $[N]$ be an index set For $s$ is a restriction on $\mathbf {x}$ denoted by $x_{|s}$ $x\in \mathbb {R} ^{N}$ to $s$ k-sparse $\mathbf {x}$ s.t. RIP is satisfied the $s=supp(\mathbf {x} )$ i.e. $s\subseteq [N]$and $\Phi _{|s}\subseteq \Phi$ where the columns of $\Phi _{|s}$ is indexed by $i\in S$

In search for a unique solution we have the following $\ell _{0}=|supp(x)|$ optimization problem.

sub module zero norm program

$\mathbf {\hat {x}} ={\underset {s}{argmin}}\|\mathbf {x} \|_{0}\quad s.t.\quad \mathbf {y} =\Phi \mathbf {x}$, 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

$\Phi$ satisfies RIP of order $k$ if for $\forall x\in \Sigma _{k}$ $\delta _{k}\in [0,1)$ satisfies for inequalaty

1. TODO switch s to k

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

If $\Phi$ satisfies RIP then $\Phi$ doesn't send two distinct k-sparse Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in \Sigma_k} to the same measurment vector Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} . Anothers words Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} is a unique solution under RIP.

sub module RIP matracies

If a sensing matrix Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi} must satisfy RIP, then the number of measurements Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M = \mathcal{O}(K/log(N/K))} is required recover Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} with high probability.

sub module RIC

Restricted Isometry Constant (RIC) is the smallest $\delta _{|s}$ in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{\delta_k \in [0, 1): (1 - \delta_s) \| x \|_2 ^2 \leq \| \Phi x \|_2^2 \leq (1 + \delta_s) \| x \|_2 ^2\}}

if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M \geq 2k} i.e. twise the sparsity, then there exists an unique Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y = \Phi x} .

for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} is k-sparse and and $\Phi$ satisfies RIP of order Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2k} RIC $\delta _{2k}<{\sqrt {2}}-1$ then the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle l_0} program can have to relaxed convex form Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell_1} program.

If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi} satisfies RIP and $\mathbf {y}$ is sparse the $\ell _{0}$ gives sparse solutions and is a unique. It is equivalent to the following $\ell _{1}$ convex optimization problem and can solve by Linear Program.

sub problem 1 norm program

From Results of Candes, Romberg, Tao, and Donoho

$\mathbf {\hat {x}} ={\underset {s}{argmin}}\|\mathbf {x} \|_{1}\quad s.t.\quad \mathbf {y} =\Phi \mathbf {x}$

Theory

Two things need to be considered when recovering $x$

• (1) The design of the sensing matrix

• (2) The recovery algorithm

Sensing Matrix

Check if $\Phi$ satisfies RIP Checking $\Phi$ 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 $x$ 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi \in R^{M \times N}} , the mutual coherence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_\Phi} is defined by:</math>

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_{\Phi} = \underset{i \neq j} {\frac{| \langle a_i, a_j \rangle |}{ \| a_i \| \| a_j \|}}}

Welch bound Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_\Phi \geq \sqrt{\frac{n}{m(n-m)}}} > Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu \geq \sqrt{\frac{N -M}{M(N-1)}}} > is the coherence between Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Psi} We want a small Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_{\Phi}} because it will be close to the normal matrix, which satisfies RIP. Also, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_{\Phi}} will be needed for the step size for the following IHT.

Need to make the connection of Coherence to RIP and RIC.

Algorithms

Three big groups of algorithms are:

• Optimization methods: includes Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell_1} minimization i.e. Basis Pursuit, and quadratically constraint Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell_1}

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. So IHT seems like the ideal place to start. If everything compliment with RIP, then IHT has fast convergence.

Algorithm IHT

The Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell_1} convex program mentioned in introduction has an equivalent nonconstraint optimization program.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \underset{y}{min} \| \mathbf{y} - \Phi \mathbf{x} \|_2^2 + \lambda \| \mathbf{y} \|_0} (cite IT for sparse approximations)  ??? Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{\mathbf{x}} = arg \underset{s}{min} \frac{1}{n} \| \mathbf{y} - \Phi \mathbf{x}\|_2^2 + \lambda \| \mathbf{x}\|_1} . In statistics we call the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle l_1} regularization LASSO with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda} as the regularization parameter. This is the closest convex relaxation to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle l_0} the first program menttioned in the introduction.[The Benefit of Group Sparsity]

$z_{v}^{(n)}=\nabla f_{v}(x^{(n)})=-\Phi _{v}^{T}(\mathbf {y} -\Phi \mathbf {x} )$ Then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^{n+1} = \mathcal{H}\left( \mathbf{x}^{(n)} - \tau \sum_{j \in N}^{N} z_v^{(n)}\right)}

sub modual

Define the threashholding operators as: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{H}_s[\mathbf{x}] = \underset{z \in \sum_s}{argmin} \| x - \Phi \mathbf{x}\|_2} selects the best-k term approximation for some k

Stopping criterion is $\|y-\Phi \mathbf {x} ^{(n)}\|_{2}\leq \epsilon$ iff RIC $\delta _{3s}<{\frac {1}{\sqrt {32}}}$

• Input Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi, \mathbf{y}, \mathbf{e} \ \mbox{with} \ \mathbf{y} = \mathbf{\Phi} \mathbf{x} | \mathbf{e} and \mathfrak{M}}
• output $IHT(\mathbf {y} ,\mathbf {\Phi } ,{\mathcal {S}})$
• Set $x^{(0)}=\mathbf {0}$
• While Stopping criterion false do

• • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^{(n+1)} \leftarrow \mathcal{H}_{|s} \left[ x^{(n)} + \Phi^* (\mathbf{y} - \mathbf{\Phi x}^{(n)}) \right]}

• • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \leftarrow n + 1 }
  • end while
• return: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle IHT(\mathbf{y}, \mathbf{\Phi}, \mathfrak{M}) \leftarrow \mathbf{x}^{(n)}}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi^*} is a Adjoint matrix i.e. the transpost of it's cofactor.

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.