[Easy-to-understand communication] What is compressed sensing (CS)?
[Copy link]
[Repost] [Easy-to-understand Communications] What is compressed sensing (CS)?
Author: Meatball Source: Breadboard
1. What is Compressed Sensing (CS)?
Compressed sensing is also called compressed sampling, and the latter seems to be more intuitive. Yes, CS is a technology for signal sampling. It achieves "compressed sampling" through some means, or more precisely, it completes the process of data compression during the sampling process.
So we first start with signal sampling:
1. We know that converting analog signals into digital signals that can be processed by computers must go through the sampling process. The question is, what sampling frequency should be used, that is, how dense or sparse should the sampling points be, in order to fully preserve the information in the original signal?
---------------------------------------
2. Nyquist gave the answer - twice the highest frequency of the signal. Nyquist sampling theorem has always been regarded as the golden rule in the field of digital signal processing.
---------------------------------------
3. As for why it is twice, students who have studied signal processing should know that the time domain is sampled at intervals of τ, and the frequency domain will be periodically extended at a period of 1/τ. So if the sampling frequency is lower than twice the highest frequency of the signal, aliasing will occur after the signal is moved in the frequency domain spectrum.
---------------------------------------
4. However, this seemingly indisputable law has been challenged by several great people. Candes was the first to realize the possibility of a breakthrough, and with the assistance of the extraordinary mathematical genius Terence Tao and Candes' teacher Donoho, he proposed the theory of compressed sensing, which states that if the signal is sparse, it can be reconstructed and recovered from sampling points far below the requirements of the sampling theorem.
---------------------------------------
5. The key to the breakthrough lies in the sampling method. When we say "sampling frequency", it means that we are doing equal-spaced sampling. The digital signal field usually does equal-spaced sampling and also obeys the Nyquist sampling theorem.
But what if the sampling intervals are unequal? Do we still have to obey the sampling theorem?
---------------------------------------
6. The answer is that random subsampling gives us the possibility to recover the original signal.
The above figure is very important, as it can simply and intuitively describe the idea of compressed sensing. As shown in Figures b and d, the signal is composed of three cosine function signals superimposed, and there are only three lines in the frequency domain (Figure a). If it is subjected to equal-spaced sub-sampling of 8 times the full sampling (the red dots below Figure b), aliasing will occur after the frequency domain signal period is extended (Figure c), and the original signal cannot be restored from the result.
---------------------------------------
7. If random subsampling is used (the red dot above Figure b), the frequency domain will no longer be extended with a fixed period, but will generate a large number of incoherent interference values. As shown in Figure c, the largest peaks are still vaguely visible, but are covered by interference values to a certain extent. These interference values look very much like random noise, but are actually caused by energy leakage of the non-zero values of the three original signals (interference values of different colors indicate that they are caused by the leakage of non-zero values of the original signals of the corresponding colors)
PS: Why does random subsampling have such an effect?
This can be understood as random sampling, which makes the spectrum no longer move neatly, but move small parts randomly. The frequency leakage is evenly distributed in the entire frequency domain, so the leakage values are relatively small, making recovery possible.
---------------------------------------
8. The next key is how to recover the signal? Here is a typical algorithm (matching pursuit):
(1) Since the non-zero frequency values of the original signal still retain larger values in the frequency domain after subsampling, the two larger ones can be detected by setting a threshold (Figure a).
(2) Then, assuming that the signal only has these two non-zero values (Figure b), the interference caused by these two non-zero values can be calculated (Figure c).
(3) Subtract c from a to get the blue non-zero value and the interference value caused by it (Figure d). Then set the threshold to detect it and get the final restored frequency domain (Figure e).
(4) If the original signal has more non-zero values in the frequency domain, they can be solved one by one through iteration.
The above is the core idea of compressed sensing theory - randomly sub-sampling the signal at a density sparser than the sampling density required by the Nyquist sampling frequency. Since the spectrum is leaked evenly rather than extended as a whole, the original signal can be restored through a special tracking method.
2. Prerequisites for Compressed Sensing
Next, let’s summarize what the key to achieving compressed sensing is, that is, what prerequisites are needed.
9.
From the description just now, you can feel that the reason why this example can achieve the final signal recovery is that it meets two prerequisites:
1. This signal has only 3 non-zero values in the frequency domain, so they can be recovered relatively easily.
2. A random subsampling mechanism is adopted, so that the frequency leakage is evenly distributed in the entire frequency domain.
These two points correspond to the two prerequisites of CS - sparsity and incoherence.
---------------------------------------
10. Sparsity can be understood simply and intuitively as follows: if a signal has only a few non-zero values in a certain domain, then it is sparse in that domain, and this domain is also called the sparse domain of the signal.
Therefore, the first prerequisite requires that the signal must be sparse in a certain transform domain. For example, in the example, the signal is sparse in the frequency domain, so the original signal can be easily restored in the sparse domain (frequency domain) through the reconstruction method described above.
---------------------------------------
However, signals usually do not show complete sparsity in the transform domain. In fact, as long as it approximately satisfies sparsity, that is, most values tend to zero and there are only a few large non-zero values, it can be considered a compressible signal and can be subjected to CS subsampling.
For the previous example, if it is not sparse in the frequency domain, we can do DWT, DCT, etc. to find its sparse transform.
---------------------------------------
11. Here is an additional supplement on signal sparsity and signal compression: In fact, signal sparsity has been widely used in the field of image compression. Signal sparsity can be used to compress signals. For example, the JPEG format in the field of image compression transforms the image into the discrete cosine domain to obtain an approximate sparse matrix, retaining only the larger values to achieve compression.
---------------------------------------
12. For example, in this example, only 6.9% of the points in the original image are used to restore an image that is basically the same as the original image. We can also use wavelet transform, that is, JPEG-2000, which has a better compression effect.
---------------------------------------
13. It should be pointed out here that the concepts of image compression and compressed sensing are easily confused, so everyone must distinguish them clearly.
They are actually fundamentally different. Image compression is done by first performing full sampling, then discarding small coefficients in the transform domain to complete the compression;
Compressed sensing is different. Its idea actually borrows a lot from image compression: since we have to discard the full sampling, why can't we just sample less points? Therefore, compressed sensing directly performs sub-sampling, and then uses algorithms to eliminate the artifacts caused by sub-sampling. It can be said that compressed sensing completes compression directly during sampling.
---------------------------------------
14. Next, before the second premise, it is necessary to introduce necessary mathematical expressions. The above picture is a schematic diagram that you often see in books and literature related to compressed sensing. Many articles try to use this picture to explain to you what compressed sensing is, but the result is that everyone is confused and confused in various "matrices". . But I believe that with my previous explanation, this picture will be much easier to understand now. This picture just expresses the subsampling process in a matrix way:
As shown in the figure, x is a one-dimensional signal of length N, that is, the original signal, with sparsity k. It is unknown at this moment.
Φ is the observation matrix, which corresponds to the subsampling process. It projects the high-dimensional signal x into a low-dimensional space and is known.
y = Φx is the one-dimensional measurement of length M, which is the result after subsampling. Obviously, it is also known.
Therefore, the compressed sensing problem is to solve the underdetermined equation system y=Φx based on the known measurement value y and the measurement matrix Φ to obtain the original signal x.
However, the general natural signal x itself is not sparse and needs to be sparsely represented on some sparse basis. Let x = Ψs, where Ψ is the sparse basis matrix and s is the sparse coefficient.
So the final equation becomes: y = ΦΨs. Given y, Φ, and Ψ, solve for s.
---------------------------------------
15. Everyone can understand the corresponding example at the beginning: x is the original signal of three sinusoidal signals superimposed on each other; the sparse matrix Ψ is the Fourier transform, which transforms the signal into the frequency domain S; and the observation matrix Φ corresponds to the random subsampling method we use; y is the final sampling result.
---------------------------------------
16. y=ΦΨs is a bit long, so we combine ΦΨ into a matrix, called the sensing matrix. Let Θ=ΦΨ
, then y=ΘS.
The problem is, given y and Θ, solve for S.
After solving S, the restored original signal x can be obtained by x=Ψs.
However, under normal circumstances, the number of equations is much smaller than the number of unknowns, the equations have no definite solution, and the signal cannot be reconstructed. However, since the signal is K-sparse, if Φ in the above equation satisfies the finite isometry property (RIP), then the K coefficients can be accurately reconstructed from the M measurements (obtaining an optimal solution).
---------------------------------------
17. The following mathematical content can be briefly skipped: Tao and Candès proved that RIP is the exact requirement that the measurement matrix must meet. However, it is very complicated to confirm whether a matrix satisfies RIP. So Baraniuk proved that the equivalent condition of RIP is that the measurement matrix and the sparse representation basis are incoherent.
This is the second prerequisite for compressed sensing.
---------------------------------------
18. How to find uncorrelated measurement matrices? Tao and Candès proved that independent and identically distributed Gaussian random measurement matrices can become universal compressed sensing measurement matrices.
Therefore, the random measurement matrix that satisfies the Gaussian distribution becomes the most commonly used observation matrix in CS.
For two-dimensional signals, the image is often sub-sampled using a sampling matrix as shown in the upper right figure.
For one-dimensional signals, the random unequally spaced sub-sampling mentioned above can be used.
-------------------------------------------------- ----------------------------
At this point, we can use one sentence to describe what compressed sensing is:
If a signal is sparse in a certain transform domain, then the high-dimensional signal obtained by the transform can be projected into a low-dimensional space using a measurement matrix that is unrelated to the transform basis. Then, by solving an optimization problem, the original signal can be reconstructed with high probability from these small number of projections.
The above can be regarded as the definition of compressed sensing. But what if we want to be more concise?
In my opinion, compressed sensing can be described in this sentence:
Directly capture a JPEG
——The previous method of image compression was to compress after full sampling, discarding some small coefficients in the sparse transform domain; CS directly reduces the sampling points. After collection and reconstruction, the image is a compressed image that is sparse in a certain transform domain, such as JPEG.
So what are the advantages of doing this?
For many situations, such as when a camera takes a photo, there is no advantage in reducing the number of sampling points, because all pixels are collected in an instant.
However, for some situations where acquisition is slow, such as magnetic resonance imaging, CS can play a huge role. Originally, it often took dozens of seconds to acquire an MRI image, and the slow speed is also a major drawback of MRI. After applying CS technology, only a fraction of the full sampling data is needed to reconstruct the original image. In this way, the imaging speed can be increased several times, while the image quality is not greatly affected.
Another application is the single-pixel camera developed by Rice University, which is a very interesting camera that only needs one pixel. Interested friends can investigate it themselves.
3. Compressed Sensing Reconstruction Method
As mentioned above, the reconstruction of CS is a method to solve the underdetermined system of equations y=ΘS. This is a zero-norm (l0) minimization problem, which is an NP-complete problem (a problem with no fast solution), so it is often converted into a one-norm (l1) minimization solution, or some approximate estimation algorithm. The specific content of this part will not be described in detail here.
| 
提升卡
变色卡
千斤顶