# Exact CS Reconstruction Condition of Undersampled Spectrum-Sparse Signals

Authors: Ying Luo; Qun Zhang; Guozheng Wang; Youqing Bai
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Compressive sensing (CS) reconstruction of a spectrum-sparse signal from undersampled data is, in fact, an ill-posed problem. In this paper, we mathematically prove that, in certain cases, the exact CS reconstruction of a spectrum-sparse signal from undersampled data is impossible. Then we present the exact CS reconstruction condition of undersampled spectrum-sparse signals, which is valuable for digital signal compression.


---

## Body

## 1. Introduction

In digital signal processing, the Nyquist sampling theorem indicates that the sampling rate must be twice as large as the bandwidth of the analog signal at least for acquiring the intact information of the signal. Restricted by the theorem, it is a challenge to digitize ultrawide bandwidth (UWB) signals because of the unfeasible high sampling rate requirement for the analog-to-digital converter (ADC). On the other hand, the mass sampling data have to be compressed to save the storage, which means that many data are abandoned in the compression processing. Hence, why not to obtain the compressed data of signals directly rather than to sample signal with ultrahigh rate and then abandon most of the samplings?The emergingcompressive sensing (CS) theory [1] provides an effective approach to solve this problem, which has attracted much attention recently [2–7]. Consider a signal x∈CN×1 and assume it is sparse on an orthogonal basis Ψ={ψi} with K-sparse representation (K≪N) as x=Ψθ, where θ is an N×1 column vector with K nonzero elements. Let Φ denote a measurement matrix and let y be the measurements vector of signal x; it can be expressed as y=Φx=ΦΨθ, where Φ is a M×N matrix, M denotes the number of measurements, and K<M≪N. Therefore, the sampling rate is reduced significantly compared with Nyquist rate. Generally, recovery of the signal x from the measurements y is ill-posed because M≪N [8]. However, the CS theory demonstrates that if ΦΨ has the Restricted Isometry Property (RIP), then it is indeed possible to recover the K largest θx(i) when M is large enough [3, 9]. It is difficult to validate if a measurement matrix satisfies the RIP constraints given in [9] directly, but fortunately, the RIP is closely related to an incoherency between Φ and Ψ, where the rows of Φ do not provide a sparse representation of the columns of Ψ and vice versa [4]. Furthermore, to ensure exact reconstruction, two different K-sparse signals may not be projected by a measurement matrix into the same sampling ensemble [1, 2, 10].Whenx is sparse in spectrum, the N-dimensional inverse discrete Fourier transform (IDFT) matrix (DN-1) can be chosen as the sparse representation matrix (Ψ). In this case, an easy way to obtain the compressed data of the signal is to undersample the signal with lower sampling rate than the Nyquist rate [2]. Therefore the measurement matrix is in fact a partial unit matrix [11]. It is important to investigate the mathematical properties of compressive sensing reconstruction for this kind of undersampled spectrum-sparse signal. In the following, we mathematically prove that the exact CS reconstruction of a spectrum-sparse signal from undersampled data is impossible under certain conditions. In order to reconstruct a spectrum-sparse signal from undersampled data exactly, the corresponding exact CS reconstruction condition is presented, which is valuable for digital signal compression.


## 2. Inexact CS Reconstruction Cases

When a signalx is sparse in spectrum, the IDFT matrix DN-1 and partial unit matrix can be chosen as the sparse representation matrix and the measurement matrix, respectively. By defining the downsampling rate r to be the ratio between the Nyquist rate and the undersampling rate, an inexact CS reconstruction case can be depicted as the following theorem.Theorem 1.
Supposex∈CN×1 with Nyquist sampling rate fs is K-sparse in spectrum domain; y={xmr+b∣mr+b≤N,m>0,m∈ℕ} is an arbitrary subset of x, where r is the downsampling rate, r≥2,  and  r∈ℕ, b is a constant and b∈ℕ, and ℕ is the set of all natural numbers. x cannot be exactly reconstructed from y by CS.Proof.
According to the expression ofy, we have
(1)yM×1=ΦM×NxN×1=ΦM×NΨN×NθN×1,
where θ is K-sparse; Φ is the measurement matrix with size M×N:
(2)
Equation (1) is equivalent to
(3)θM×1′=DMyM×1=DMΦM×NDN-1θN×1,
where DM is the M-dimensional DFT matrix. Because y is isometrically downsampled from x, θ′ is also sparse. In (3), we define a new measurement matrix Φ1=DMΦM×N and it can be expressed as(4)
According to CS theory, ifΦ1DN-1 satisfies the RIP, θ can be exactly reconstructed. Let ϕ1a be the ath row of Φ1; we have
(5)ϕ1aT=DN-1DNϕ1aT=DN-1(DNϕ1aT)=DN-1[0,1-WNMr1-WMa-1WNr,…,1-WN(N-1)Mr1-WMa-1WN(N-1)r]T,
where  WM=exp(-j2π/M). Because Rank(DN-1)=N, according to Cramer’s Rule, the equation DN-1α=ϕ1aT has unique solution; that is,
(6)α=[0,1-WNMr1-WMa-1WNr,…,1-WN(N-1)Mr1-WMa-1WN(N-1)r]T.
Letαn be the nth element of α; it can be obtained
(7)|αn|=|1-WN(n-1)Mr1-WMa-1WN(n-1)r|=1-cos((2π/N)(n-1)Mr)1-cos(2π((a-1)/M+((n-1)r)/N)).
It peaks at(8)(n-1)rN=-a-1M+l,l∈ℤ,
where ℤ is set of all nonnegative integers. Because N=(M-1)r+1, we have
(9)n=-a+2+(r-1)(a-1)Mr+l(M-1+1r)
and n is a natural number; hence
(10)n=[-a+2+(r-1)(a-1)Mr+l(M-1+1r)],
where [(·)] returns the round of (·). When n does not satisfy (10), |αn| is relatively quite small. It indicates that {|αn|} is sparse. Similarly, it can be proved that both {real(αn)} and {imag(αn)} are also sparse. Therefore, ϕ1a can be sparsely represented by the columns of DN-1; that is, Φ1DN-1 does not satisfy the RIP, and θ cannot be exactly reconstructed.Figure1 shows the values of {|αn|}, {real(αn)}, and {imag(αn)} when N=1024,  M=64,  r=16,  and a=40. It is obvious that {|αn|}, {real(αn)}, and {imag(αn)} are sparse and the locations of peaks agree well with the theoretical values determined by (10).The sparsity ofαn when N=1024, M=64, r=16, and a=40. (a) {|αn|}; (b) {real(αn)}; (c) {imag(αn)}.
(a)
(b)
(c)By Theorem1 and its proof, we can also obtain the following corollary.Corollary 2.
Supposex∈CN×1 with Nyquist sampling rate fs is K-sparse in spectrum domain; x′={xmr+b∣mr+b≤N,m>0,m∈ℕ} is an arbitrary subset of x, where r is the downsampling rate, r≥2, and  r∈ℕ and b is a constant and b∈ℕ. Let y be an arbitrary subset of x′; then x cannot be exactly reconstructed from y by CS.Proof.
Assume the length ofx′ is M and we have
(11)y=Φ2x′=Φ2ΦDN-1θ,
where Φ2 is a partial unit matrix. Assuming the size of Φ2 is L×M  (L≤M), the solution set of (1) is a subset of the solution set of (11). According to Theorem 1, the solutions of (1) are not determined; therefore, θ in (11) cannot be determined and x cannot be exactly reconstructed.Corollary2 indicates that, if the set of undersamplings is only a subset of the set of signals’ samplings with sampling rate lower than the Nyquist rate, the signal cannot be exactly reconstructed from these undersamplings by CS. Therefore, when designing the ADC with random sampling space, the ADC should better possess the capability with the minimum sampling space of 1/fs, where fs is the Nyquist rate. Taken in this sense, the high sampling rate requirement for ADC is indeed not suppressed even though the CS theory is utilized.


## 3. Exact CS Reconstruction Condition

In the following, we present the exact CS reconstruction condition of undersampled spectrum-sparse signals.Theorem 3.
Supposex∈CN×1 with Nyquist sampling rate fs is K-sparse in spectrum domain; and the frequency indexes of K nonzero points in spectrum are fh  (h=1,2,…,K). Undersampling x with rate fs/r1,fs/r2,…,fs/ri,…,fs/rI (i=1,2,…,I, ri≥2, and ri∈ℕ), respectively, all the samples consist of yM×1. The necessary and sufficient condition for x exactly reconstructed from y by CS is
(12){fh+k1fsr1∣h=1,2,…,K;k1∈ℤ;|fh+k1fsr1|≤fs2}∩{fh+k2fsr2∣h=1,2,…,K;k2∈ℤ;|fh+k2fsr2|≤fs2}∩⋯∩{fh+kIfsrI∣h=1,2,…,K;kI∈ℤ;|fh+kIfsrI|≤fs2}={fh∣h=1,2,…,K}.Proof.
Reconstructingx from y is in fact to solve the following underdetermined equation system:
(13)y1=Φ1x=Φ1DN-1θ,y2=Φ2x=Φ2DN-1θ,⋮yI=ΦIx=ΦIDN-1θ,
where Φi is the measurement matrix according to the undersampling rate fs/ri;  yi is composed of the undersamplings of x with rate fs/ri. Assume the frequency indexes of the solution set of the ith equation are {f^hi}; because yi is the isometric downsampling from x, we have
(14){f^hi}⊆{fh+kifsri∣h=1,2,…,K;ki∈ℤ;|fh+kifsri|≤fs2}.
Hence, the solution set of (13) is
(15)∩{f^hi}⊆∩{fh+kifsri∣h=1,2,⋯,K;ki∈ℤ;|fh+kifsri|≤fs2}.
Only if (12) holds true, under the constraint of K-sparse, it yields ∩{f^hi}={fh∣h=1,2,…,K}; therefore, x is exactly reconstructed.Theorem3 indicates that it is possible to reconstruct a spectrum-sparse signal exactly from its multirate downsamplings. It means that, when condition (12) is satisfied, the multirate downsampling can be used to compress the data of digital signals. The conclusion is valuable to the design of the ADC when the analog signal is a priori known sparse in spectrum.In order to validate Theorem3, an experiment is given as follows. In the experiment, the signal x(t) with Nyquist sampling rate fs=1Hz is expressed as x(t)=exp(0.2×2πt)+0.8exp(0.45×2πt)+0.6exp(0.3×2πt), t∈[0,1023]. The sparsity of x(t) in spectrum domain is 3 and fh={0.2,0.45,0.3}. The spectrum of x(t) is shown in Figure 2(a). Let r1=7 and r2=10. Therefore, we have
(16){fh+k1fsr1∣h=1,2,⋯,K;k1∈ℤ;|fh+k1fsr1|≤fs2}={0.2+k17∣k1∈ℤ;|0.2+k17|≤12}∩{0.45+k17∣k1∈ℤ;|0.45+k17|≤12}∩{0.3+k17∣k1∈ℤ;|0.3+k17|≤12}={0.2,0.2+17,0.2+27,0.2-17,0.2-27,iiiiiiiiiiiii0.2-37,0.2-47,0.45,0.45-17,iiiiiiiiiiiii0.45-27,0.45-37,0.45-47,0.45-57,iiiiiiiiiiiii0.45-67,0.3,0.3+17,0.3-17,0.3-27,iiiiiiiiiiiii0.3-37,0.3-47,0.3-57},{fh+k2fsr2∣h=1,2,…,K;k2∈ℤ;|fh+k2fsr2|≤fs2}={0.2+k210∣k2∈ℤ;|0.2+k210|≤12}∩{0.45+k210∣k2∈ℤ;|0.45+k210|≤12}∩{0.3+k210∣k2∈ℤ;|0.3+k210|≤12}={-0.5,-0.4,-0.3,-0.2,-0.1,0,0.1,0.2,0.3,iiiiiiiiiiiii0.4,0.5,0.45,0.35,0.25,0.15,0.05,-0.05,iiiiiiiiiiiii-0.15,-0.25,-0.35,-0.45}.Experiment for validation of Theorem3. (a) The spectrum of the signal x(t) with Nyquist sampling rate; (b) the spectrum of the reconstructed signal by CS; (c) the comparison of x(t) and the reconstructed signal in time domain.
(a)
(b)
(c)Obviously, the intersection of (16) is fh={0.2,0.45,0.3}. Hence, x(t) can be exactly reconstructed from the downsamplings. In the experiment, we choose the orthogonal matching pursuit (OMP) algorithm [12] to reconstruct x(t) from the downsamplings. The spectrum of the reconstructed signal by CS is shown in Figure 2(b), which is very close to that in Figure 2(a). The comparison of the original signal x(t) with Nyquist sampling rate and the reconstructed signal in time domain is also given in Figure 2(c). From the figure, it can be found that the reconstructed signal is close to the original signal, which validates the correctness of Theorem 3.



---

*Source: 715848-2013-12-31.xml*