FACTA UNIVERSITATIS Series: Electronics and Energetics Vol. 27, N o 3, September 2014, pp. 359 - 373 DOI: 10.2298/FUEE1403359S NOISES IN RANDOMLY SAMPLED SPARSE SIGNALS  Ljubiša Stanković University of Montenegro, Podgorica, Montenegro Abstract. Sparse signals can be recovered from a reduced set of randomly positioned samples by using compressive sensing algorithms. Two main reconstruction directions are in the sparse transformation domain analysis of signals and the gradient based algorithms. In the transformation domain analysis, that will be considered here, the estimation of nonzero signal coefficients is based on the signal transform calculated using available samples only. The missing samples manifest themselves as a noise. This kind of noise is analyzed in the case of random sampling, when the sampling instants do not coincide with the sampling theorem instants. Analysis of the external noise influence to the results, with randomly sampled sparse signals, is done as well. Theory is illustrated and checked on statistical examples. Key words: sparse signals, compressive sensing, noise, Fourier transform 1. INTRODUCTION A signal can be transformed from one domain into another in various ways. Some signals that cover whole considered interval in one domain (dense in that domain) could be located within much smaller regions in another domain. We say that signals are sparse in a transformation domain if the number of nonzero coefficients is much fewer that the total number of signal samples. For example, a sum of discrete-time complex sinusoidal signals, with a number of components being much lower than the number of signal samples in the time domain, is a sparse signal in the discrete Fourier transform (DFT) domain. Sparse signals could be reconstructed from much fewer samples than the sampling theorem requires. Compressive sensing is a field dealing with the problem of signal recovery from a reduced set of samples [1]-[21]. This research area intensively develops in the last decade. It provides solutions that differ from the classical signal theory approach. Two main directions in the signal recovery are present. One is based on the signal transform analysis (orthogonal matching pursuit methods) and the other is based on the gradient methods. The samples could be missing due to a desire to represent a signal with the lowest possible number of samples or due their physical or measurement unavailability. In applications it could happen that some arbitrarily positioned samples of the signal are so heavily corrupted by disturbances that it is better to omit them and consider as unavailable in the analysis.  Received March 23, 2014 Corresponding author: Ljubiša Stanković University of Montenegro, Podgorica, Montenegro (e-mail: ljubisa@ac.me) 360 LJ. STANKOVIĆ This is especially true for the impulsive noise [4], [23]. As a study case, in this paper we will consider signals that are sparse in the Fourier transform domain. Signal sparsity in the discrete Fourier domain imposes some restrictions on the signal. One of them is that the frequencies of the signal components are on the frequency grid. Otherwise even one component complex sinusoidal signal will not be sparse in the DFT domain. Reducing the number of samples in the analysis manifests as a noise, whose properties are studied in [13] and used in [24] to define a reconstruction algorithm. The input noise influence is also an important topic in this analysis since the reduced number of available samples could increase the sensitivity of the recovery results to this noise [8], [24]. In this paper sparse signals with available samples at the random positions, that do not correspond to the sampling theorem defined positions, will be analyzed. It will be shown that the noise due to random sampling exists even in the case of large number of available samples. In the case on nonuniformly sampled signals a possibility to recalculate the signal samples values to the sampling theorem positions is exploited [25]. Efficiency of this recalculation in the signal recovery is studied for various numbers of available signal values. An analysis of the additive input noise is done as well. Theoretical results are statistically checked. 2. RECONSTRUCTION ALGORITHM 2.1. Definitions Consider a discrete-time signal x(n) obtained by sampling a continuous-time signal x(t). Since the DFT will be used in the analysis then we can assume that the continuous- time signal is periodically extended with a period T. The period T is related to the number of samples N, the sampling interval t, and the maximal frequency m as m =  / t = N / T . The continuous-time signal can be written as an inverse Fourier series ( 1) / 2 2 / = ( 1) / 2 ( ) = . N j kt T k k N x t X e      (1) with the Fourier series coefficients being related to the DFT as = ( ) = { ( )} k X N X k DFT x n and x(n) =x(nt). Frequency indices { ( 1) / 2,... 1, 0,1,..., ( 1) / 2}k N N     corresponds to the frequencies 2 / ( 1) m k N  in the analog domain. This signal can be reconstructed from its samples taken according to the sampling theorem as 1 = 0 sin[( ) ] ( ) = ( ) . sin[( ) / ] N n t n t x t x n t t N n N t          (2) This relation holds for an odd N. Slightly corrected relation holds for an even N, [5], [25]. The signal x(t) is sparse in the Fourier transform domain if the number of nonzero transform coefficients K is much lower than the number of the original signal samples N within T , K N , i.e., = 0 k X for 1 {k k , 2 k , ..., } K k . A signal Noises in Randomly Sampled Sparse Signals 361 2 / { , ,..., } 1 2 ( ) = . j kt T k k k k k K x t X e    (3) of sparsity K can be reconstructed from M samples, where M  N. 2.2. Known frequency positions In the case of signal that is sparse in the Fourier domain there are K unknown values Xk1, Xk2,..., XkK . If the frequency positions {k1, k2, ..., kK} are known then the minimal number of equations to find the unknown coefficients (and to calculate (3) for any t) is K. The equations are written for at least K time instants ti, i = 1,2,...,M  K, where the signal should be available, 2 / =1 = ( ), for = 1, 2,..., . K j k t T m i k i m m X e x t i M K   (4) In a matrix form this system is K AX = y , (5) where Xk is the vector of unknown nonzero coefficients and y is the vector of the available signal samples, defined as 1 2 = [ ... ] T K k k k K X X XX (6) 1 2 = [ ( ) ( ) ... ( )] T M x t x t x ty with 2 / 2 / 2 / 1 1 2 1 1 2 / 2 / 2 / 1 2 2 2 2 2 / 2 / 2 / 1 2 ... ... = ... ... ... ... ... j k t T j k t T j k t T K j k t T j k t T j k t T K j k t T j k t T j k t T M M K M e e e e e e e e e                        A . (7) The coefficients reconstruction condition can be easily formulated as the condition that the system (5) has a unique solution, i.e.,.that det( ) 0A for the time instants ti where the signal is available and for the known frequency indices ki, i = 1,2,...,K, for M = K. In general, for M > K, the condition is that there are K independent equations, rank( ) = .KA Special case 1: Consider a sparse signal with frequencies k1, k2, ..., kK. Assume that the available signal samples are a random subset of the full set of signal samples taken according to the sampling theorem ti = nit. The set {k1, k2, ..., kK} in the DFT analysis can be considered as a subset of all frequency coefficients {0,1,2,..., N1}, having in mind that frequency indices in the second half of the DFT correspond to the negative frequencies in the Fourier series. Then 362 LJ. STANKOVIĆ 2 / 2 / 2 / 1 1 2 1 1 2 / 2 / 2 / 1 2 2 2 2 2 / 2 / 2 / 1 2 ... ... = ... ... ... ... ... j k n N j k n N j k n N K j k n N j k n N j k n N K j k n N j k n N j k n N M M K M e e e e e e e e e                        A . (8) This matrix is related to the IDFT matrix W with N samples in such a way that the rows corresponding to the time instants where the signal is not available are removed. The columns corresponding to the signal frequencies {k1, k2, ..., kK} are kept, while the other IDFT columns are removed. Thus, the matrix A of order M  K is obtained from the IDFT of order N  N by removing row for time instants of unavailable signal samples and columns where the signal transform is zero-valued. If signal samples are chosen randomly then the reconstruction condition rank (A) = K could be satisfied if at least M = K. However it can happen that some instants, for given frequencies, produce dependent observations and that the full recovery is not possible. Probability that we have sufficient number of independent equations is increased if the number of instants is increased. System (4) is used with K M N . Therefore, by assuming that the positions of the nonzero coefficients in transformation domain are known, a system of M linear equations AXK = y, (5), for available signal samples x(ti), i = 1,2,...,M, is solved for K unknowns Xk, k  {k1, k2, ..., kK}. Its solution, in the mean squared sense, follows from = H H K A AX A y 1 ( ) H K H X = A A A y. (9) If the DFT values X(k) are used in vector XK instead of the Fourier series coefficients Xk then, using the relations Xk N = X(k), the system of equations (5) reads 1 . K N AX = y Special case 2 (Oversampled signal): Consider now a signal sampled with = / m t   but whose maximal frequency is = /K m t   . Then, according to the sampling theorem, this is an oversampled signal. It is a special case of a sparse signal with ordered nonzero coefficients as 1 2 1 1 = { , ,..., } = {0,1,..., , ,... 2, 1}. 2 2 K K K k k k N N N     K In order to recover this signal it is sufficient to have a reduced set of samples. If the samples are not taken randomly (as it is done in compressive sensing) but at the instants ti = itN / K, where N / K is an integer, then the sampling step is tN / K. This corresponds to the signal downsampling with factor / 1N K , since K N . Then with M = K and ni = iN / K we get a special form of (8), relating the DFT values and the discrete-time signal samples, as Noises in Randomly Sampled Sparse Signals 363 2 / 2 ( 1) / 2 ( 1) / 2 ( 1)( 1) / 1 1 ... 1 1 ...1 = . ... ... ... ... 1 ... j K j K K K j K K j K K K e e K e e                     X y This is an IDFT matrix with K samples. Since this is an IDFT matrix of order K it satisfies the condition det(A)  0. In practice, excluding the sampling theorem cases with oversampled signals, the positions of the frequencies in a sparse signal are rarely known. Two groups of the methods are derived to solve the problem. One is based on concentration measures [15] that are used to measure the signal sparsity. The problem is solved by minimizing the concentration measures subject to the condition that the signal values are known at some time instants. In this group the gradient based algorithms are commonly used, [7, 21]. The other group, that will be used here, is directly related to the presented theory of the system solution with known frequencies in the sparse signal. The first step in this class of methods is to estimate the positions of the signal frequencies and then in the next step to apply the presented simple approach to find the Fourier transform coefficients at {k1, k2, ..., kK}. By finding the nonzero Fourier transom coefficient values the signal recovery is achieved. 3. FREQUENCY POSITIONS ESTIMATION 3.1. Random subset of uniformly sampling signal Consider a sparse signal whose values are known at some of the possible sampling theorem defined positions tni = nit = niT /N with ni  {n1, n2, ..., nM}. The first step is to estimate the DFT coefficients positions, using the available samples. It is done as 2 / { , ,..., } 1 2 ( ) = ( ) . j kn N n n n n M X k x n e    (10) With K M N the DFT, calculated with M samples, is a random variable. For a sparse signal of the form =1 ( ) = exp( 2 / ), K p p p x n A j nk N the mean value of (10) is =1 { ( )} = ( ), K p p p E X k M A k k  while its variance is [13] 2 2 =1 ( ) = [1 ( )]. 1 K N p p p N M k A M k k N        (11) The variance is derived [13] in by using the condition that the sum (10) for =M N is =1 ( ) = ( ), K p p p X k M A k k  with 2 ( ) = 0 N k . Example: Consider a three component signal 1 1 2 2 3 3 ( ) = exp( 2 / ) exp( 2 / ) exp( 2 / )x t A j k t N A j k t N A j k t N    (12) 364 LJ. STANKOVIĆ with A1 = 1, A2 = 0.75, A3 = 0.25, , {k1, k2, k3} = {58,117,21}, within 0 256t  . With t = 1 and N = 257 the signal is sparse in the Fourier domain. Random realizations of the initial DFT (10) are given in Fig.1, for several values of the number of available samples M. We can see that a low value of M does not provide possibility to estimate the signal component positions. All three components are visible for larger values of M. When signal frequencies are detected then the signal is recovered using (9) with known time instants ti  {t1, t2,..., tM} (or in discrete-time domain ni  {n1, n2,..., nM}) and detected frequencies {k1, k2,..., kK}. Obviously from a noisy observation of the DFT we can distinguish two cases: 1) When the number of available samples is large and all components are above a threshold that can be calculated based on (11). Then all signal frequencies will be distinguishable as peaks in the DFT. 2) If the number of available samples is low or there are components with much lower amplitudes then the iterative procedure should be used. The largest component is detected and estimated first. It is subtracted from the signal. The next one is detected and the signal is estimated using the frequency from this and the previous step(s). The estimated two components are subtracted from the original signal. The frequency of next components is detected, and the process with estimation and subtraction is continued until the energy is negligible. Both of these reconstruction cases are studied and described in [24]. 3.2. Random subset of randomly sampled signal Now consider the case when randomly positioned samples of a continuous-time signal within 0  t  T are available. The positions of the observations ti are not related to the sampling theorem positions in any way. An estimate of the initial DFT can be calculated using the available signal values, as 2 / { , ,..., } 1 2 ( ) = ( ) . j kt T i i t t t t i M X k x t e    (13) Fig. 1 DFT of a signal with various number of available samples M. Available M samples are a random subset of N samples taken according to the sampling theorem interval. Red dots represent the original signal DFT values, scaled with M / N to match the mean value of the DFT calculated using a reduced set of samples signal. The DFT values are presented as a function of the frequency index. Noises in Randomly Sampled Sparse Signals 365 We will again assume that the signal is sparse with unknown number and positions of the frequencies {k1, k2, ..., kK}, K M N . For a frequency k = kp and the signal component exp( 2 / ) p p A j k t T all values in (13) will be 2 /2 / = = .p i j kt Tj k t T i p p k k p A e e A   Therefore, the mean value of estimator (13) is =1 { ( )} = ( ). K p p p E X k M A k k  The variance of this estimator is different from the case when the available signal samples are at the sampling interval positions [13]. The condition that the value of the DFT coefficient is zero (with zero variance) if all N samples are used, does not hold any more. The total variance is 2 2 =1 ( ) = 1 ( ) . K N p p p k A M k k     (14) For small M we have (N  M) / (N  1)  1. Then expressions (11) and (14) give similar result. Some of the random realizations of the initial DFT (13) are given in Fig. 2. In contrast to the previous case, the variance of the estimator (13) does not tend to zero as M approaches to N. However, we can see that the signal frequencies can be detected and used to recover the signal using (5) and (7) with known time instants ti  {t1, t2, ..., tM} and detected frequencies {k1, k2, ..., kK}. Fig. 2 DFT of a signal with various number of available samples M. Available M samples are taken at random positions within 0  ti  T. Red dots represent the original signal DFT values, scaled with M / N to match the mean value of the DFT calculated using a reduced set of samples signal. 366 LJ. STANKOVIĆ 3.3. Random subset of nonuniformly sampled signals Consider now a random set of possible sampling instants {t1, t2, ..., tN}, = , i i t i t   where vi is a uniform random variable t / 2  vi  t/2. With  = 1 any position of the signal sample within it  t / 2  ti < it + t / 2 is equally probable. With   1 the sampling positions are random, but within one sampling interval only one signal sample can occur. This case will be referred to as nonuniform sampling. Assume that only M < N signal samples are available at ti  {t1, t2, ..., tM}. In the nonuniform sampling case the initial DFT estimate can be calculated using (13). This transform may be used to estimate the frequency positions. Note that as in the random sampling case, even if we use M = N the resulting signal will not be sparse. This fact will degrade the recovery performance. The problem with nonuniform sampling can be reformulated to produce a uniformly sampled signal. If the signal values at ti are known then (2) can be used to recover the signal samples at the sampling theorem adjusted instants. This relation reads 1 = 0 sin[( ) ] ( ) = ( ) . sin[( ) / ] N i n t n t x t x n t t N n N t          The transformation matrix relating samples taken at ti with the signal values at sampling theorem positions, is 1 11 12 1 2 21 22 2 1 2 ( ) ... (0) ( ) ... ( ) = ... ... ... ... ... ... ( ) ... (( 1) ) N N N N N NN x t b b b x x t b b b x t x t b a b x N t                                      x̂ = Bx with sin[( ) ] = sin[( ) / ] i ij i t j t b t N j N t       An additional problem here is that we know just M  N of signal samples. The values at unavailable positions ti  {t1, t2, ..., tM} are assumed to be zero. Their positions are assumed at the sampling theorem instants, ti = it for ti  {t1, t2, ..., tM}, since they are not known anyway. The uniform (sampling interval) signal values are then 1 11 12 1 1 21 22 2 2 1 2 ... ( )(0) ... ( )( ) = . ... ... ... ... ...... ... ( )(( 1) ) N N N N NN N b b b x tx b b b x tx t b a b x tx N t                                   (15) Noises in Randomly Sampled Sparse Signals 367 The matrix B 1 is inverted only once for given signal sample positions. Note that there is a direct relation to calculate the values x(nt) based on randomly sampled values x(ti) as [25]     11 =0=0 sin ( ) / ( ) = ( ) . sin ( ) / NN q p qp p p q p n t t N x n t x t t t N           Here the inversion is not needed. However, in our calculation, this was not computationally more efficient approach. The results for several random realization and the nonuniform signal sampling, with recalculated signal values at the sampling theorem positions, are shown in Fig. 3. As the number of available samples approaches to the total number of samples N the reconstructed DFT is noise-free, Fig. 3. Fig. 3 DFT of a signal with various number of available samples M. Available M samples are a random subset of N nonuniform samples taken at random positions within the sampling theorem interval. Red dots represent the original signal DFT values, scaled with M / N to match the mean value of the DFT calculated using a reduced set of samples signal. For all previous reconstruction cases and the signal defined by (12) the variance is calculated in 100 random realizations of the sets of available samples. The results for the variance is presented in Fig. 4. The ratio of signal and noise energies is calculated as well and presented in Fig.5. Agreement of the theory and the statistical results is high. From Fig.4 we can conclude that the recalculation is not efficient for a small number of available samples, when M N . In that case even worse results are obtained than without recalculation, what could be expected. For a large number of available samples (in Fig.4 for M > 5N / 8) the recalculation produces better results, approaching to the sparse signal without any deviation, for N = M. 368 LJ. STANKOVIĆ Fig. 4 Variance of the DFT for all previous methods of sampling and various number of available samples M. (1)-line with marks "x": Available samples are a subset of all samples taken at the sampling theorem grid (solid line-theory, marks "x"-statistics). (2)-line with marks "o": Randomly positioned M samples taken within 0  ti  T (solid line-theory, marks "o"-statistics). (3)-marks "+": Nonuniform randomly shifted samples from the sampling theorem grid. (4)-marks "*": Nonuniform randomly shifted available samples being recalculated on the sampling theorem grid. Fig. 5 Ratio of the signal and DFT noise energies for all previous methods of sampling and various number of available samples M. (1)-line with marks "x": Available samples are a subset of all samples taken at the sampling theorem grid (solid line-theory, marks "x"-statistics). (2)-line with marks "o": Randomly positioned M samples taken within 0  ti  T (solid line-theory, marks "o"-statistics). (3)-marks "+": Nonuniform randomly shifted samples from the sampling theorem grid. (4)-marks "*": Nonuniform randomly shifted available samples being recalculated on the sampling theorem grid. Noises in Randomly Sampled Sparse Signals 369 4. ADDITIVE NOISE INFLUENCE Next we will analyze the case when input noise exists in the sparse signal to be reconstructed. It has been shown that this kind of noise increases the variance caused by missing samples. A formula how to increase the number of available samples in order to compensate the influence of input noise is derived as well [24]. It is important to note that once the reconstruction conditions are meet and the reconstruction is achieved, the noise due to missing samples does not influence the results in a direct way. It influences the possibility to recover signal at all. The accuracy of the recovery results is related to the input noise. The input noise is transformed by the recovery algorithm into a new noise depending on the signal sparsity and the number of available samples. A simple analysis of this form of noise will be presented next. Assume an additive noise  (t) in the input signal. The reconstruction equations (4) are 2 / ={ , ,..., } 1 2 ( ) ( ) = ,for = 1, 2,..., j kt T i i i k k k k k K x t t X e i M    at the available instants ti, i = 1,2,...,M, for detected frequencies k = {k1, k2, ..., kK}. In a matrix form this system of M linear equations with K unknowns reads = K y AX The solution follows form ( ) = H H K A y A AX 1 = ( ) ( ) H H K   X A A A y = K KS KN X X X (16) where 1 = ( ) H H KS  X A A A y are the true signal coefficient values and 1 = ( ) H H KN   X A A A is the noise influence to the reconstructed signal coefficients. The input signal-to-noise (SNR) ratio, if all signal samples were available, is 1 2 = 0 1 2 = 0 ( ) = 10 log = 10 log . ( ) N n n x i N n n x t E SNR E t      Assume the noise energy in M samples used in reconstruction is 2 { , ,..., } 1 2 = ( ) . M A i t t t t i M E t     (17) Using (10) in calculation is the same as assuming that the values of unavailable samples is zero. This kind of calculation corresponds to the result that would be achieved for the signal transform if the norm-two, i.e., min 1 2 =0 ( ) N k X k   , is used in minimization, [21, 370 LJ. STANKOVIĆ 3, 6, 23]. The correct amplitude in the signal transform at the frequency kp, in the case if all signal samples were used, would be NAp. To compensate the resulting transform for the known bias in amplitude when only M available samples are used we should multiply the coefficient by N / M. It means that is a full recovery, a signal transform coefficient should correspond to the coefficient of the original signal with all signal samples being used. The noise in the transform coefficients will also be multiplied by the same factor. Therefore, its energy would be increased to EA N 2 / M 2 . The signal-to-noise ratio in the recovered signal would be 1 2 = 0 2 2 2 { , ,..., } 1 2 ( ) = 10 log ( ) N n n i t t t t i M x t SNR N t M      (18) If the distribution of noise in the samples used for reconstruction is the same as in other signal samples then 2 2 { , ,..., } 1 2 | ( ) | = i t t t t i M t M      and 1 2 = 0 2 2 2 ( ) = 10 log N n n x t SNR N M M     (19) = 10 log . i N SNR M        (20) Therefore, a signal reconstruction that would be based on the initial estimate (10) would worsen SNR, since N > M. An improvement can be expected only if we were able to remove the noisy samples in a selective manner so that the samples used in reconstruction are less noisy than the other samples, [23]. If such a criterion is used to selectively remove the noise samples then the reconstruction is improved if 2 1 2 2 2 { , ,..., } =0 1 2 ( ) < ( ) . N i n t t t t n i M N t t M       Since only K out of N DFT coefficients are used in the reconstruction the energy of the reconstruction error is reduced for the factor of K / N as well. Therefore, the energy of noise in the reconstructed signal is 2 2 2 { , ,..., } 1 2 = ( ) . R i t t t t i M K N E t N M     The final signal to noise ratio in the reconstructed signal is 1 2 = 0 2 2 { , ,..., } 1 2 ( ) = 10 log . ( ) N n n i t t t t i M x t SNR KN t M      (21) Noises in Randomly Sampled Sparse Signals 371 If a criterion of selection the noisy samples is used then the variance in the remaining samples is lower than the average variance of all samples, i.e., 2 { , ,..., } 1 2 1 2 = 0 1 ( ) = 1 ( ) i t t t t i M QN n n t M C t N       (22) where 0 1 Q C  is the criterion selection efficiency:  If there is no any criterion CQ = 1.  In an ideal case when the noise does not exists in the remaining samples (removed by a criterion or L-statistics as in [3]) then CQ = 0. With this factor the SNR is = 10 log . i Q K SNR SNR C M        (23) This simple theoretical result is tested on signal (12) with additive noise of variance  2  = 1. For a random set of M available samples the initial DFT is calculated using (10). Since a large number of available samples M is used in these simulations the signal components {k1, k2, k3} are easily detected in one step. The signal is reconstructed by (9) for the set of available signal samples y = [x(t1) x(t2) ... x(tM)] T and the detected frequencies {k1, k2, k3}. For statistical check of the results, 100 random realizations of the available sample positions are used. The results are summarized in Table 1 for a different number of available sampels M, with CQ = 1. The theory agreement with statistics is very high. For smaller values of M the iterative procedure (described in the last paragraph of subsection 3.1) should be used since all components can not be detected in a single realization of (10). Similar results would be obtained as far the value of available sample is sufficient for signal recovery. Table 1 Signal to noise ratio: In the input signal (SNRi), obtained by theory (SNRT) and by statistics (SNRS) for various number of available samples M with N=257. SNR in [dB] = 128M = 160M = 192M = 224M SNRi 2.6383 2.6215 2.5663 2.5811 SNRT 18.8837 19.8519 20.6446 21.3140 SNRS 18.8709 19.8528 20.6415 21.3887 In order to test the change of ,K the theory is illustrated on a four component signal 1 1 2 2 3 3 4 4 ( ) = exp( 2 / ) exp( 2 / ) exp( 2 / ) exp( 2 / ) ( ) x t A j k t N A j k t N A j k t N A j k t N n          as well. The amplitudes in this case where A1 = 1, A2 = 0.75, A3 = 0.5, A4 = 0.67, and the frequency indices {k1, k2, k3 k4} = {58,117,21,45}. The results are presented in Table 2. 372 LJ. STANKOVIĆ Table 2 Signal to noise ratio: In the input signal (SNRi), obtained by theory (SNRT) and by statistics (SNRS) for various number of available samples M with N=257. SNR in [dB] = 128M = 160M = 192M = 224M SNRi 3.5360 3.5326 3.5788 3.5385 SNRT 18.5953 19.5644 20.3562 21.0257 SNRS 18.7203 19.5139 20.2869 21.7302 The agreement of the numerical statistical results with this simple theory in analysis of noise influence to the reconstruction of sparse signals is high. 5. CONCLUSION Analysis of random samples sparse signals is preformed. It has been shown that random sampling increases noise in the reconstructed caused by unavailable samples. For a relatively large number of available samples the signal recalculation of nonuniformly sampled signals to the sampling theorem grid can improve the results. The input noise can degrade the reconstruction limit. However as far as the reconstruction is possible the noise caused by missing samples manifests its influence to the results accuracy in simple and direct way trough the number of missing samples and signal sparsity. The accuracy of the final result is related to the input noise intensity, number of available samples and the signal sparsity. The theory is checked and illustrated on numerical examples. REFERENCES [1] D. L. Donoho, “Compressed sensing,” IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1289–1306, 2006. [2] E. J. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,” IEEE Transactions on Information Theory, vol. 52, no. 2, pp. 489–509, 2006. [3] L. Stanković, I. Orović, S. Stanković, and M. G. Amin, “Robust Time-Frequency Analysis based on the L- estimation and Compressive Sensing,” IEEE Signal Processing Letters, May 2013, pp. 499–502. [4] R. E. Carrillo, K. E. Barner, and T. C. Aysal, “Robust sampling and reconstruction methods for sparse signals in the presence of impulsive noise,” IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2), pp. 392–408. [5] L. Stanković, M. Daković, and T. Thayaparan, Time–Frequency Signal Analysis with Application, Artech House, 2013. [6] L. Stanković, S. Stanković, I. Orović, and M. G. Amin, “Compressive Sensing Based Separation of Non- Stationary and Stationary Signals Overlapping in Time-Frequency, ”IEEE Transactions on Signal Processing, vol. 61, no. 18, pp. 4562–4572, Sept. 2013 [7] M. A. Figueiredo, R. D. Nowak, and S. J. Wright, “Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems,”IEEE Journal of Selected Topics in Signal Processing,, vol. 1, no. 4, pp. 586–597, 2007. [8] D. Donoho, M. Elad, and V. Temlyakov, “Stable recovery of sparse overcomplete representations in the presence of noise,” IEEE Transactions on Information Theory, vol. 52, pp. 6–18, 2006. [9] B. Turlach, “On algorithms for solving least squares problems under an L1 penalty or an L1 constraint,” Proc. of the American Statistical Association; Statistical Computing Section, pp. 2572–2577, Alexandria, VA, 2005. [10] R. Baraniuk, “Compressive sensing,” IEEE Signal Processing Magazine, vol. 24, no. 4, 2007, pp. 118–121. [11] P. Flandrin and P. Borgnat, “Time-Frequency Energy Distributions Meet Compressed Sensing,” IEEE Transactions on Signal Processing, vol. 58, no. 6, 2010, pp. 2974–2982. Noises in Randomly Sampled Sparse Signals 373 [12] Y. D. Zhang and M. G. Amin, “Compressive sensing in nonstationary array processing using bilinear transforms," in Proc. IEEE Sensor Array and Multichannel Signal Processing Workshop, Hoboken, NJ, June 2012. [13] L. Stanković, S. Stanković, and M. G. Amin, “Missing Samples Analysis in Signals for Applications to L- Estimation and Compressive Sensing”, Signal Processing, Elsevier, Volume 94, Jan. 2014, Pages 401–408. [14] S. Aviyente, “Compressed Sensing Framework for EEG Compression”, in Proc. Stat. Sig. Processing, 2007, Aug. 2007. [15] L. Stanković, “A measure of some time–frequency distributions concentration,” Signal Processing, vol. 81, pp. 621–631, 2001 [16] N.B. Karahanoglu and H. Erdogan, ” Compressed sensing signal recovery via forward–backward pursuit”, Digital Signal Processing, Vol.23, Issue 5, Sept. 2013, Pages 1539–1548. [17] S. Stanković, I. Orović, and E. Sejdić, Multimedia signals and Systems, Springer, 2012. [18] E. Sejdić, A. Cam, L. F. Chaparro, C. M. Steele, and T. Chau, “Compressive sampling of swallowing accelerometry signals using TF dictionaries based on modulated discrete prolate spheroidal sequences,” EURASIP Journal on Advances in Signal Processing, 2012:101 doi:10.1186/1687–6180–2012–101. [19] S. G. Mallat and Z. Zhang, “Matching pursuits with time-frequency dictionaries,” IEEE Transactions on Signal Processing, vol. 41, no. 12, pp. 3397–3415, 1993. [20] I. Daubechies, M. Defrise, and C. De Mol, “An iterative thresholding algorithm for linear inverse problems with a sparsity constraint,” Communications on pure and applied mathematics, vol. 57, no. 11, pp. 1413– 1457, 2004. [21] L. Stanković, M. Daković, and S. Vujović, “Adaptive Variable Step Algorithm for Missing Samples Recovery in Sparse Signals,”IET Signal Processing, in print, 2014 (first version available on arxiv.org/abs/1309.5749). [22] L. Stanković, M. Daković, and S. Vujović, “Concentration Measures with an Adaptive Algorithm for Processing Sparse Signals,” in Proceedings of ISPA 2013, Sept. 4–6, 2013, Trieste, Italy, pp. 418–423. [23] L. Stanković, M. Daković, and S. Vujović, “Reconstruction of Sparse Signals in Impulsive Noise", IEEE Transactions on Signal Processing, submitted (first version available on arxiv.org) [24] S. Stanković, I. Orović, and L. Stanković, "An Automated Signal Reconstruction Method based on Analysis of Compressive Sensed Signals in Noisy Environment", Signal Processing, Elsevier, Volume 94, in print. [25] E. Margolis and Y.C. Eldar, "Nonuniform Sampling of Periodic Bandlimited Signals," IEEE Transactions on Signal Processing, vol.56, no.7, pp.2728,2745, July 2008.