Brief introduction to compressed sensing

---

Preface

When you just touch compressed sensing , In the face of its concept is very vague , But I really appreciate its function . In unremitting study , I have a certain understanding of compressed sensing , Share the basic knowledge here , Help everyone learn compressed sensing ~

---

One 、 What is compressed sensing ？

   Compress perception （Compressed Sensing,CS） It is a breakthrough theory for information acquisition proposed by Tao Zhexian and others . The theory points out that ： For sparse signals or compressible signals , Data can be sampled in a way lower than Nyquist sampling frequency , Reduce the amount of data transfer , And can accurately reconstruct the signal with high probability .（ A sentence in the graduation thesis ）
Here you want to trace the source , You can refer to the following literature ：

D. L. Donoh, Compressed sensing, IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.

Two 、 Introduction to compressed sensing

1、 Compressed sensing process

Compressed sensing is mainly divided into three steps ：
  1、 Sparse representation of signals , Realize signal compression ;
  2、 Design of observation matrix , Get the observed value ;
  3、 Signal reconstruction , Get the recovery signal .

2、 Signal sparse representation

   Sparse signal definition ： Let one-dimensional discrete signal $x$, The length is $N$, Can be seen as $N$ Dimensional space $N\times 1$ The column vector , If this column vector contains $K$ It's not for 0 Elements , And $K<<N$, The signal $x$ yes $K$- Sparse signal , Have sparsity .$K$ It's called a signal $x$ The sparsity of . Keep in mind , The signal is sparse （ In this domain or other transform domains ） Is the premise that compressed sensing can be used ！
   If the signal is sparse , Then signal $x$ It can be expressed as ：
$$x={\sum }_{k=1}^N{\psi }_k{s}_k=\Psi s$$
among ,$s$ Sparse coefficient , It is also the new reconstruction number recovered by using the algorithm , Its size and signal $x$ identical ;$\Psi$ It is known as sparse matrix , Its size is $N\times N$, This is the process of signal sparsity .

3、 Observation matrix design

   The main function of the observation matrix is to enable people to see the observed values obtained by the instrument $y$, among , How much do you want to see , This is the well-known sampling rate . The requirements for the observation matrix are , From the observed value $y$ The reconstructed length with medium and high accuracy is $N$ The original signal $s$, Or reconstruct the equivalent signal under the sparse matrix . The concrete expression is ：
$$y=\Phi x$$ In style ,$\Phi$ Is the observation matrix （ Also known as measurement matrix ）, Its dimension is $M\times N$;$s$ For the original signal , Its dimension is $N\times 1$;$y$ For observation signal , Its dimension is $M\times 1$. Bring this formula into 2 Formula in section , Then you can get the formula you often see ：
$$y=\Phi x=\Phi \Psi s=\Theta s$$ among ,$\Theta =\Phi \Psi$ by $M\times N$ Order matrix , Also known as sensing matrix .
   In this step , The most important thing is to construct an appropriate observation matrix , So that the observed value obtained from the sparse signal can be collected by the instrument , And when solving in reverse , Reconstruct sparse signals from observations , That is, construct a solution M×K System of linear equations . Keep in mind , During the above process , The observation matrix must be RIP Property Analysis , To put it bluntly, the correlation between the observation matrix and the sparse matrix is very small, very small ！

4、 Signal reconstruction

   Signal reconstruction is right $y=\Phi x=\Phi \Psi s=\Theta s$ Formula to find the optimal solution , It is the solution problem in compressed sensing theory , How to get the optimal solution is the main content of the study , It is also the last key step . The current reconstruction algorithms of compressed sensing are mainly divided into two categories ： Greedy algorithm and convex optimization algorithm . The greedy algorithm is mainly to select the appropriate column vector and add it step by step for many times to realize the approximation of the signal , Among them, matching pursuit algorithm 、 Orthogonal matching pursuit and other algorithms are greedy algorithms ; Convex optimization algorithm is to put the solution of norm into norm to solve linear programming , This algorithm includes base tracking algorithm 、 Gradient projection algorithm .

summary

   Here is a flow chart of my graduation thesis , Help you understand ：

   So to conclude ： When performing compressed sensing recovery and reconstruction on the signal , The signal should be mapped to the sparse domain , That is, the signal is sparse in a certain transform domain . When compressing and sampling the measurement matrix , The measurement matrix shall meet RIP Conditions , Or it should satisfy the condition that the observation matrix is not related to the sparse basis . On the basis of two conditions , Compressed sensing algorithm can be used for recovery and reconstruction . Master the basic knowledge of compressed sensing , Then use it quickly ~