Compressive Sensing Reconstruction for Sparse Signals with Convex Optimization

Compressive Sensing Reconstruction for Sparse Signals with Convex Optimization

Ahmed M. Awadallah, Guangming Shi, Guanghui Zhao

School of Electronic Engineering Xidian University

Xian, P.R. China

AbstractThe theory of compressive sampling (CS), also known as compressed sensing. It is a modern sensing scheme that goes against the common theory in data acquisition. The CS theory claims that one can recover images or signals from fewer samples or measurements than the traditional methods use. To achieve this recovery, CS theory depends on two basic principles: the first is the sparsity of signal, which relates to the signals of interest, and the incoherence, which relates to the sensing method. In this paper we will give a simple review on the CS theory and the analog to information (AIC) system will be discussed briefly supported with two examples of signal reconstruction from undersampled signals. Simulation results show the powerful of the CS reconstruction for both sparse in time and spars in frequency signals.

Index TermsCompressed Sensing (CS); Convex Model; Spares Signal Reconstruction.

I. INTRODUCTION

Traditional methodologies to sampling images or other signal forms follow the Shannons Nyquist theorem: the sampled signal rate must be at least two times the maximum existed frequency in the original signal. Almost all the signal acquisition systems is basically based on this principle and is used in many applications of electronics, medical imaging, audio and visual systems, and so on. The traditional analog-to-digital converter (ADC) usually performs quantization under the Shannons theorem, which samples the signals at or above the Nyquist rate.

Candès, Tao and Romberg [1] and Donoho [2] have proposed the methodology, known as compressed sensing (CS), in this method the random linear projection is used to obtain efficient representations of the compressible signals directly. The CS theory states that it is possible to reconstruct sparse images or signals from a small number of random measurements, even in the presence of noise [3].

Because of the CS sampling compressing ability, the compressed sensing has found effective approaches in many fields. Applications in the field of radar in the field of radar imaging were developed based on the CS theory. The new systems were able to construct high resolution images with a significant reduction in the recorded raw data, moreover low cost of production and compact system size which enables the system to be used in different fields and applications.

In the field of synthetic aperture radar, the CS theory has a great effect in the development and improvement of performance of such systems.

A novel CS-based ISAR reconstruction model deducted from the Meridian prior (MCS) is proposed in [4]. With the reduction of number of pulses and signal-to-noise ratio (SNR), this model exhibits better performance in terms of resolution and amplitude error than that of the Laplace- prior-based CS (LCS) model.

XIAO Peng et al. [5] proposed a CS range compression method for imaging SAR based on the chirp scaling principle, namely compressed sensing with chirp scaling (CS-CS). The proposed algorithm can achieve the same range resolution as the conventional SAR approach, while using fewer range data samples. Experiments showed that this algorithm is capable of image reconstruction from few sampling returns.

Other SAR imaging methods were also used to achieve high resolution imaging. A radar imaging method which combines stepped frequency chirp signal (SFCS) processing and chirp scaling imaging algorithm (CSA) to achieve a high resolution image was introduced in [6]. This approach was verified by the simulation and experimental results.

R.Baraniuk et al. [7] proposed the radar imaging system based on CS for the first time. Papers [8, 9] use CS in along- track interferometric SAR imaging and moving target velocity estimation. Some major open questions related with the application of CS to SAR and ISAR are listed in [10].

In [11], Li introduces a novel two-dimensional (2-D) SAR imaging algorithm based on CS theory to reconstruct 2-D targets in the range and azimuth dimension, respectively. This algorithm provides the approach of receiving the echo data via 2-D random sparse sampling beyond the rate required by Nyquist theorem. This radar system transmits randomly fewer pulses in the azimuth direction and fewer samples data than traditional systems at random intervals in range direction.

In this paper we review the basic concept of the CS theory and give an example of the reconstruction of the undersampled output signal from systems like the analog to information AIC system [12], the examples contains two cases for signal waveforms, the first case is using a sparse in time signal, and the second is a sparse in frequency signal.

The reminder of this paper is organized as follows. Section II reviews the main principles required for CS recovery. Section III presents the basics of the CS theory. Section IV presents the CS based analog-to-information

conversion. The experimental results are shown in section

1. Finally, Conclusions are given in section VI.

   1. MAIN PRINCIPLES REQUIRED FOR CS RECOVERY The CS theory claims that one can recover images or

      signals from fewer samples or measurements than the traditional methods use. To achieve this recovery, CS theory depends on two basic principles: the first is the sparsity of signal, which relates to the signals of interest, and incoherence, which relates to the sensing method.

      Sparsity represents the idea that the sampling rate of continuous time signals may be much fewer than the rate suggested by its bandwidth. The CS theory uses the fact that most natural signals are compressible or sparse in the sense and that they have concise representations if expressed in a proper basis .

      where M cK c 1 denotes to the number of measurements. The measurements amount for exact signal reconstruction is depending on the structure of measurement matrix and the sparsity level of the signal representation . If all entries of are drawn from a standard Gaussian distribution, then the signal can be exactly reconstructed with a high probability when c is between 3 to 5 [13]. Measurements that obtained by uniform random matrix may contain more information of the signal than that obtained by sparse matrix. The achievement of same performance for signal recovery usually needs more measurements with sparse matrix than that with uniform random matrix.

      The sparse representation of the signal x can be reconstructed through solving the following minimization problem:

      Incoherence extends duality between the time and

      P1 min

      1

      subject to

      y

      (3)

      frequency and give expression to the idea that the objects having sparse representation in , then it must be spread out in that domain in which they are acquired.

      Compressive sampling is basically concerned with the low coherence pairs. Examples of low coherence pairs such as the canonical or spike basis , where k t t k

      This problem is known as Basis Pursuit [14], and is a convex problem which can be solved by linear programming techniques for real signals.

      In most practical situations, signals are corrupted by noise. Assuming that the noise M is additive, then the random measurement for a noisy signal is

      j

      and the Fourier basis , where t n1/ 2ei ?2 ? jt / n as in Fig.1. Further, the spikes and sinusoids are maximally

      y

      (4)

      icoherent not only in one dimension but also incoherent in any dimension, (two dimensions, and three dimensions, etc.)

      The coefficients vector can be reconstructed through

      solving l1-regularized least squares problems (LSP)

      LSP min y 2 +

      (5)

      2 1

      Figure 1, The spike basis , and the Fourier basis

   2. BASICS OF THE CS THEORY

      Suppose that x L and represents a real signal. Assume the signal x is a sparse or compressible in redundant dictionary or known transform domain , where

      1 2 N

      , ,…, , the signal x can be approximated by

      linear combination of K (KN) atom components (or basis functions), i.e.,

      where 0 is a regularization parameter. This is quadratic programming problem in which the parameter controls the tradeoff between sparsity of solution and noise energy.

   3. 2.5.3 CS ANALOG-TO-INFORMATION CONVERSION Analog to information converter (AIC) is one of the

      most important applications of the CS theory in the field of signal processing. It offers feasible technique to implement the low-rate information sampling. Figure 2 shows the AIC structure and it consists of three basic components: the first is a wideband pseudorandom demodulator pc(t), the second is a filter h(t), and the third is a low-rate analog to digital converter (ADC). The pseudorandom sequence function is to spread the frequency of the signal and to provide randomness necessary for a successful signal recovery [12].

      n

      where

      i

      x ni ni i 1

      K

      i

      , ni 1, 2,…, N . Let n

      1 ,2 ,…,N

      (1)

      T be

      the coefficients vector of the signal x in . Let denote to a uniform random measurement matrix and y be the measurements vector of the signal x. The random measurement for signal x can be expressed as

      y , : M N , K < M N (2)

      Figure 2, Main components of AIC

      For a sparse analog signal xt , there exist a continues basis dictionary n t , n 1, 2,…, N such that

      N

      x t n n t , n, t (6)

      n 1

      With just few elements of vector are nonzero. If xt

      1.5

      1

      is the input of the AIC, then the output y m can be expressed as

      0.5

      0

      y m

      x p h t d |

      (7)

      -0.5

      c t mt

      -1

      where t is sampling interval of the low-rate ADC and

      -1.5

      m 1, 2,…, M . From (6) and (7), y(m) can be written as

      0 20 40 60 80 100 120

      Atom Signal

      N

      Figure 3, The atom signal

      y m n n

      n 1

      pc h mt d

      (8)

      The function in (10) is for the signal shown in Fig. 3.

      The measurement matrix deduced from (8)

      m,n

      of the AIC can

      This signal is called the atom signal and it will be used with the information about the object location and the signal amplitude at these locations to generate the input signal.

      p hm d

      (9)

      The generated input signal xt is a sinusoidal signal

      m,n n c t

      Then using the measurements y and the matrix , the coefficients vector of the input signal x can be reconstructed by solving the convex optimization problem

      (P1).

      with length of 1024 as shown in Fig. 4. This signal waveform will be used as the AIC input signal.

      1.5

      1

   4. SIMULATION EXAMPLES FOR SPARSE SIGNALS RECONSTRUCTION

      This section the performance of signal reconstruction will be investigated through two simple simulations. The AIC system shown in Fig.2 will be used in the performance test, and two cases for the input signal will be used: 1) the input signal is sparse in time, 2) the input signal is sparse is frequency.

      1. First Case: The signal is sparse in time

         In this section the input signal to the AIC will be a sparse in time signal. The signal can be generated using the function (10) and the parameters in Table I.

         Assume the function for the input signal is as follows:

         0.5

         0

         -0.5

         -1

         -1.5

         0 200 400 600 800 1000

         input signal x(T)

         Figure 4, The input signal x(t)

         In the next step for the AIC, the input signal is multiplied by the random sequence pc(t) (pseudorandom demodulator), which will have the same length of 1024 as

         x t sin 2* pi * f 1*t .*sin 2* pi * f 2*t

         (10)

         the input signal xt . Figure. 5 shows the random sequence

         pc(t) with length of 1024.

         where the simulation parameters for the sparse in time signal are shown in the table below.

         TABLE I. SPARSE IN TIME SIGNAL SIMULATION PARAMETERS

         1.5

         1

         0.5

         0

         -0.5

         Parameter	Value
         Signal length (samples)	1024
         Objects locations	100 , 450, 800
         amplitudes	0.5, 0.9, 0.5
         ADC rate (mt)	30
         f1	0.5Hz
         f2	10 Hz

         -1

         -1.5

         0 100 200 300 400 500 600 700 800 900 1000

         random +1/-1 sequence Pc(T)

         Figure 5, The random sequence pc(t)

         The resulting signal waveform after the multiplication with the random sequence is shown in Fig. 6.

         1.5

         1

         0.5

         0

         -0.5

         -1

         The main reconstruction process is basically depending on the recovery of the input signal coefficients . First, we use the output signal y(m) and the basis matrix for this system to solve a the convex optimization problem shown in Eq.5. The matlab CVX toolbox [15] were used to reconstruct the input signal coefficients , the reconstructed coefficients are shown in Fig.9.

         1

         0.8

         0.6

         -1.5

         0 100 200 300 400 500 600 700 800 900 1000 x(T) Pc(T)

         Figure 6, Signal x(t).pc(t)

         0.4

         0.2

         Then a filter h(t) is applied to the signal in Fig.6. In this simulation the filter is a low pass filter with order of 199 (coefficients length is 200).The signal after the filtering process is shown in Fig. 7.

         1.5

         1

         0.5

         0

         -0.5

         -1

         -1.5

         0 200 400 600 800 1000 1200

         x(T) Pc(T) h(t-T)

         Figure 7, Signal x(t).pc(t).h(t)

         The final processing step in the AIC system sequence is the analog to digital conversion ADC. The signal is then sampled with the ADC rate of mt. The final output downsampled signal y(m) after AIC process completed is shown in Fig. 8.

         1.5

         1

         Amplitude

         0.5

         0

         -0.5

         -1

         -1.5

         0 200 400 600 800 1000

         time samples

         Figure 8, Output signal y(m) after AIC with ADC rate mt=1:30

         0

         0 200 400 600 800 1000

         the reconstructed alfa n

         Figure 9, The reconstructed Time coefficient

         The reconstructed input signal coefficients are then used with the atom signal in Fig.3 to reconstruct the input signal xt . The input signal after reconstruction is shown in Fig.10

         In Fig.11 we show the l2-norm error signal between the original and recovered signals. Table II shows The l2-norm of error for different ADC rates mt between the original input and reconstructed input at a fixed random sequence.

         1.5

         1

         Amplitude

         0.5

         0

         -0.5

         -1

         -1.5

         0 200 400 600 800 1000

         the recovered signal

         Figure 10, The reconstructed signal xt

         0.5

         Error amplitude

         0

         The CS theory will show its magic capability of reconstructing the input signal again from the output signal of the AIC system.

         -0.5

         0 200 400 600 800 1000

         Error signal (time Samples)

         Figure 11, The l2-norm error signal

         TABLE II. THE L2-NORM OF ERROR FOR DIFFERENT DOWNSAMPLING RATES

         ADC rae mt	The l2-norm of error
         5	0
         10	7.702e-16
         15	8.8908e-15
         20	2.1667e-15
         25	4.8225e-15
         30	1.2107e-14
         35	5.0371e-15
         40	2.0541
         45	4.697

      2. Second Case: The signal is sparse in frequency

      This section is very much similar to the previous one except that the input signal to the AIC system will be a sparse in frequency signal. The signal can be generated using the function (11), which is as follows:

      x t A1sin 2 pi * f 1*t A2sin 2 pi * f 2 *t

      (11)

      • A3sin 2 pi * f 3*t

      where the frequencies: f1=50, f2=300, f3=600 Hz, and the amplitude coefficients: A1=2, A2=7, A3=5

      The same processing steps of the AIC are performed, starting from the input signal (sparse in frequency) reaching to the final step of the output downsampled signal. And then the same reconstruction process is performed. The main difference is the use of signal which is sparse in frequency. The frequency coefficients will first be recovered, and then used to rebuild the original input signal. The following figures will shows the simulation results

      Figure (12) shows the input sparse in frequency signal.

      Figure (13) shows the output signal after AIC with ADC rate mt =1:50.

      Figure (14) shows the reconstructed input signal frequency coefficients .

      Figure (15) shows the reconstructed input signal xt .

      Figure (16) shows the l2-norm error signal.

      8

      6

      4

      Amplitude

      2

      0

      -2

      -4

      -6

      -8

      -10

      0 200 400 600 800 1000

      Time Samples

      Figure 13, Output signal (sparse in frequency) after AIC with ADC rate mt =1:50

      4.5

      4

      3.5

      3

      2.5

      2

      1.5

      1

      0.5

      0

      0 200 400 600 800 1000

      Reconstructed Alfa

      Figure 14, Reconstructed frequency coefficients

      15

      10

      Amplitude

      5

      0

      -5

      -10

      -15

      0 200 400 600 800 1000

      Time Samples

      Figure 15, Recovered signal (sparse in frequency)

      0.5

      Amplitude

      0

      15

      -0.5

      10

      Amplitude

      5

      0

      -5

      0 200 400 600 800 1000

      Time Samples

      Figure 16, Error signal ("The l2-norm of error = 1.7414e-08", "ADC rate mt = 1:50")

   5. CONCLUSION

-10

-15

0 200 400 600 800 1000

Time Samples

Figure 12, The input signal (sparse in frequency)

Using the compressed sensing (CS) based methods enable the exact recovery of sparse signals from a significant few number of measurement samples. This gives the ability to reduce the hardware needed in the systems based on CS theory and hence reduce the cost. This work

gives a brief review on the basics of the CS theory and gives simple simulation examples for sparse signal reconstruction. The results show the high performance of the CS in the exact recovery of sparse signals from a few numbers of samples.

REFERENCES

1. E. J. Candès, J. Romberg, and T. Tao, "Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information," Information Theory, IEEE Transactions on, vol. 52, pp. 489-509, 2006.

2. D. L. Donoho, "Compressed sensing," IEEE Transactions on Information Theory, vol. 52, pp. 1289-1306, 2006.

3. J. Romberg, "Imaging via compressive sampling [introduction to compressive sampling and recovery via convex programming]," IEEE Signal Processing Magazine, vol. 25, pp. 14-20, 2008.

4. G. Zhao, Z. Wang, Q. Wang, G. Shi, and F. Shen, "Robust ISAR imaging based on compressive sensing from noisy measurements," Signal Processing, vol. 92, pp. 120-129, 2012.

5. P. Xiao, Z. Yu, and C. Li, "Compressive sensing SAR range compression with chirp scaling principle," Science China Information Sciences, vol. 55, pp. 2292-2300, 2012.

6. W. Zhai and Y. Zhang, "A stepped frequency chirp scaling algorithm for high resolution SAR imaging," in Synthetic Aperture Radar (APSAR), 2011 3rd International Asia-Pacific Conference on, 2011, pp. 1-4.

7. R. Baraniuk and P. Steeghs, "Compressive radar imaging," in Radar Conference, 2007 IEEE, 2007, pp. 128-133.

8. Y. Lin, B. Zhang, W. Hong, and Y. Wu, "Along-track interferometric SAR imaging based on distributed compressed sensing," Electronics letters, vol. 46, pp. 858-860, 2010.

9. A. S. Khwaja and J. Ma, "Applications of compressed sensing for SAR moving-target velocity estimation and image compression," IEEE Transactions on Instrumentation and Measurement, vol. 60, pp. 2848-2860, 2011.

10. J. H. Ender, "On compressive sensing applied to radar," Signal Processing, vol. 90, pp. 1402-1414, 2010.

11. J. Li, S. Zhang, and J. Chang, "Two-dimensional random sparse sampling for high resolution SAR imaging based on compressed sensing," in Radar Conference (RADAR), 2012 IEEE, 2012, pp. 0001-0005.

12. G. Shi, J. Lin, X. Chen, F. Qi, D. Liu, and L. Zhang, "UWB echo signal detection with ultra-low rate sampling based on compressed sensing," IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 55, pp. 379-383, 2008.

13. E. Candes and J. Romberg, "Signal recovery from random projections," in Proc. SPIE, 2005, pp. 76-86.

14. S. S. Chen, D. L. Donoho, and M. A. Saunders, "Atomic decomposition by basis pursuit," SIAM journal on scientific computing, vol. 20, pp. 33-61, 1998.

15. M. Grant and S. Boyd, "CVX: Matlab software for disciplined convex programming, version 2.0 bet a. http://cvxr. com/cvx," September, 2013.