RANSAC-Based Signal Denoising Using Compressive Sensing
Ljubisa Stankovic Milos Brajovic Isidora Stankovic Jonatan Lerga Milos Dakovic
cs.IT eess.SP math.IT


	




L. Stankovic, M. Brajovic, I. Stankovic, and M. Dakovic are with the University of Montenegro, J. Lerga is with the Faculty of Engineering  and Center for Artificial Intelligence and Cybersecurity, University of Rijeka, Croatia. 
	  




RANSAC-Based Signal Denoising  
 Using
	Compressive Sensing
    Ljubiša Stanković, 
	 Miloš Brajović, 

 Isidora Stanković,
Jonatan Lerga, 

Miloš Daković

    December 30, 2023
===============================================================================================




















In this paper, we present an approach to the reconstruction of signals exhibiting sparsity in a transformation domain, having  some heavily disturbed samples. This sparsity-driven signal recovery exploits a carefully suited random sampling consensus (RANSAC) methodology for the selection of an inlier subset of samples. To this aim, two fundamental properties are used: a signal sample represents a linear combination of the sparse coefficients, whereas the  disturbance degrade original  signal sparsity. The properly selected samples are further used as measurements in the sparse signal reconstruction, performed using algorithms from the compressive sensing framework. Besides the fact that the disturbance degrades signal sparsity in the transformation domain, no other disturbance-related assumptions are made – there are no special requirements regarding its statistical behavior or the range of its values. As a case study, the discrete Fourier transform (DFT) is considered as a domain of signal sparsity, owing to its significance in signal processing theory and applications. Numerical results strongly support the presented theory. In addition, exact relation for the signal-to-noise ratio (SNR) of the reconstructed signal is also presented. This simple result, which conveniently characterizes the RANSAC-based reconstruction performance, is numerically confirmed by a set of statistical examples.

Keywords— Sparse signals, Robust signal
processing, RANSAC, Impulsive noise, Compressive sensing, Sample selection, DFT 





§ INTRODUCTION




In recent years, the reconstruction of sparse signals, based on a reduced set of random measurements, attracted significant research interest <cit.>. Within the compressive sensing (CS) framework, a rigorous mathematical foundation has been established to support this type of reconstruction, including the conditions that  guarantee a successful and unique reconstruction result  <cit.>. The most important requirement imposed by this theory is that the signal must be sparse in a particular transformation domain. Such signals are characterized by a small number of non-zero elements in the sparsity domain as compared to the full signal length, and do appear in various applications <cit.>.







Signal samples in the time-domain, being linear combinations of the sparsity domain coefficients, can be considered as the measurements within the CS framework. The number of samples required for the reconstruction is closely related to the number of nonzero coefficients in the sparse domain
<cit.>. It has been repeatedly confirmed that in the case of heavily disturbed samples, it is preferable to omit these samples (outliers) in both  signal analysis and  processing <cit.>.
 In the CS and sparse signal processing context, this means that the uncorrupted or low-corrupted samples (inliers) are considered as available measurements, whereas the heavily corrupted samples are considered as unavailable, and are reconstructed by applying some of the CS-based recovery algorithms. This further implies that  a detection method shall be applied to identify the highly corrupted samples prior to their reconstruction <cit.>. One such  methodology, based on the signal sparsity principles, is presented in this paper.
In contrast to the methods that combine the robust estimation and the CS
based signal recovery, the proposed method can provide an exact reconstruction if the reduced set of inliers is noise-free, rather than to obtain a filtered approximation of the original signal   <cit.>.



The proposed algorithm  is based on a random selection of subsets of signal samples (random sampling consensus - RANSAC) and a detection of the event when a disturbance-free (or low-corrupted) subset is selected. The RANSAC-based approach improves our detection and reconstruction based on sparsity measures, reported in <cit.>, in the way that it provides a criterion to properly choose the best and largest possible set of adequate measurements – inliers, which are suitable for the CS-based reconstruction of corrupted samples – outliers. The SNR analysis in the CS-based reconstruction  <cit.> shows that  the quality of the reconstruction is directly influenced by the number of available samples. The presented RANSAC-based methodology is  additionally equipped with the analysis of noise influence to  the reconstructed signal, using an exact and simple relation for the SNR in the resulting signal.

The paper is organized as follows. After the introduction, the background of the compressive sensing theory and the RANSAC overview are  presented in Section <ref>. The denoising procedure based on the RANSAC is presented in  Section <ref>, which also includes the discussion regarding the numerical complexity. The presented theory is verified numerically in Section <ref>, while the paper ends with some concluding remarks.






§ DEFINITIONS



Consider a signal x(n) with N samples in the discrete-time domain. Assume
that the sparsity domain of the signal is the discrete Fourier transform (DFT)
domain. The signal and the DFT coefficients are related via

    X(k)=DFT{x(n)}     =∑_n=0^N-1x(n)φ_k^∗(n),
    
    x(n)=IDFT{X(k)}     =1/N∑_k=0^N-1X(k)φ_k(n)

or 𝐗=𝐖𝐱 and 𝐱=𝐖^-1𝐗, where the basis functions take the form φ_k(n)=exp(j2π nk/N). In  the matrix notation,
the N-dimensional vector 𝐗 has elements X(k), vector
𝐱 has elements x(n), and the N× N matrix 𝐖 is
with elements φ_k^∗(n), k=0,1,…,N-1, n=0,1,…,N-1. 

The time-domain representation of a signal which
is sparse in the DFT domain reads

    x(n)=∑_i=1^KA_iφ_k(i)(n) ,

where A_i, i=1,2…,K, represent the nonzero elements at the transformation  domain positions k(i),  i=1,2,…,K. The sparsity of this signal is K, (K≪ N).

Assume that there are M available (inlier) samples at the instants
n_i, i=1,2,…, M. In the CS theory, the linear combinations of the sparsity coefficients are referred to as the measurements. Therefore, the available signal samples can be considered as the CS measurements, y(i)=x(n_i). The measurement vector
 is denoted by
𝐲. Its elements are

    y(i)=x(n_i)=1/N∑_k=0^N-1X(k)φ_k(n_i) ,  i=1,2,…,M.

The matrix notation for this system of M linear
equations is 

    𝐲=𝐀𝐗.
 
The measurement matrix 𝐀 is obtained from the inverse DFT matrix
𝐖^-1, by eliminating the rows corresponding to the
unavailable/outlier samples.

The goal of the CS approach is to reconstruct the complete signal x(n), n=0,1,2,…,N-1, from the reduced (compressively sensed) subset of (inlier) samples at the instants n_i, i=1,2,…,M, with M<N. 
 This problem cannot be solved in a direct way, since there are M<N equations for N unknown transformation domain elements of X(k). When the signal sparsity is assumed, the sparsity measure minimization is added.  Among an infinite number of solutions for the underdetermined system (<ref>),  𝐲=𝐀𝐗, we look for the one with the sparsest possible representation in the transformation domain while satisfying the measurement equations. The constrained minimization problem formulation is, 

    min‖𝐗‖ _0 subject to 𝐲=𝐀𝐗.

The solution to this problem exists (if some conditions are met) and it produces the signal transformation elements X(k) and the signal samples at all instants. 
 
Simple counting of the nonzero values of X(k) is achieved using the so-called
ℓ_0-norm ‖𝐗‖ _0. However, the solution based on the ℓ_0-norm is an NP-hard optimization problem. Its
calculation complexity is of order NK. In theory, the NP-hard
problems can be solved by an exhaustive search. However, as the problem
parameters N and K increase, the computational time increases and the problem
becomes unsolvable in a realistic time frame. 

Many methods are recently developed for the CS-based reconstruction, by solving the minimization problem (<ref>) or its various equivalent forms (a review of some of them can be found in <cit.>). In this paper,
will use a very simple and efficient algorithm that belongs to the class of matching pursuit algorithms. This algorithm will be described in Section <ref>. 



 §.§ RANSAC Review


The random sample consensus (RANSAC) is used for linear regression when the outliers in the data are expected. Consider a set of data x(n_i) sampled at random instants n_i. Assume that the true data values fit a linear model, x=an+b. Since a large number of  outliers is expected, most of the data samples can be far from the linear model. In the RANSAC approach, we will:

	
  * Assume a small subset 𝕊 with S randomly selected samples x(n_i) at n_i ∈𝕊. 
	
  *  The samples with indices in 𝕊 are used to estimate the linear regression model parameters,
	
    a ∑_n_i∈𝕊n^2_i+b ∑_n_i∈𝕊n_i=∑_n_i∈𝕊n_ix(n_i)   and     
    	a ∑_n_i∈𝕊n_i+b N=∑_n_i∈𝕊x(n_i).
 
	
  * After the parameters a and b are determined,
	the line 
    x=an+b
 is plotted.  
	The distances d_n of all data points (n,x(n)), n=0,1,…,N-1, from this line are calculated, d_n=|an+b-x(n)|/√(1+a^2).
	
  * If a sufficient number of data points is such that their distance from the model line is lower than an assumed distance threshold d, then all these points are included into a new set of data 
    𝔻={(n_i,x(n_i))|    d_n_i≤ d },

	and the final parameters a and b (for machine learning or prediction) are calculated with all data from 𝔻. 
	
  * If there was no sufficient number of data points within the distance d, a new random small set  of data, 𝕊, is taken and the procedure is repeated from point <ref>.
	
  * The procedure ends when the desired number of data points within 𝔻 is achieved or the maximum number of trials is reached.
  



§ RECONSTRUCTION OF SPARSE SIGNAL WITH OUTLIERS


Consider a signal x(n), 0≤ n≤ N-1, that is sparse in a transformation
domain with a sparsity K≪ N. Assume that the signal is noisy with a small noise ε(n) (causing inliers) in all samples. Assume that I samples of the signal x(n),
at unknown positions n∈ℕ_I, are corrupted with an impulsive disturbance
ν(n). The disturbing signal ν(n) can be modeled, for example, as
ν(n)=0 for n∉ℕ_I and ν(n) assumes
arbitrary high values for n∈ℕ_I. The original signal can be 
recovered if a sufficient number of the inlier samples exists.

The sufficient number of inliers is directly related to the full
recovery conditions studied in the CS theory
<cit.>. A rough estimation of the smallest number of samples that should be used in the reconstruction of K sparse signal can be
made based on the statistical results presented in <cit.>.
The exact reconstruction conditions are commonly defined by the restricted isometry property (RIP), using the spark, or the coherence  of the measurement matrix <cit.>. However, these 
	conditions are either computationally unfeasible or too pessimistic. In numerical tests, we followed   the set of practical guidelines from <cit.> for situations when one could expect perfect recovery from a partial Fourier matrix using convex optimization. It is suggested that in the case when  K ≤ M/5, the recovery rate is highly reliable.  It is worth mentioning that computationally feasible results for the reconstruction uniqueness of signals sparse in the DFT domain  are presented in <cit.>, <cit.>.
	
	 It is important to emphasize that the use of lower values for M, when some unsuccessful reconstructions are expected to happen, will not be problematic for the RANSAC, since this methodology, by definition, searches for successful reconstruction, as it will be shown in the next section.
 




 §.§ Concentration Measure-Based  Denoising


To solve the stated problem,   in our previous work <cit.>, we exploited the idea of
eliminating random subsets of samples and performing the reconstruction using
the remaining samples. For each realization, the sparsity measure of the
recovered signal is used for the detection of the full recovery event. By using a
sparsity measure close to the l_0-norm, all realizations containing disturbed
samples will produce a sparsity measure close to the total number of
samples N. This is expected, since a disturbance at any signal sample, will affect all coefficients in the sparsity domain <cit.>. As an illustration, consider a disturbance at n_i, of the form ν(n)=ν_0δ(n-n_i), which is added to the signal sample x(n) at n_i. Its DFT, X_ν(k)=ν_0exp(j2π n_i k/N), k=0,1,…, N-1, is spread over all DFT coefficients of the original signal. In many CS approaches, ℓ_1-norm is used as a measure of signal sparsity <cit.>. Noise influence on sparsity measures has also been investigated in <cit.>.

In the case when only the uncorrupted samples are used in the
reconstruction, the sparsity measure is of order K. It is much lower than the
total number of samples N. Therefore, by setting a threshold T_μ within
K<T_μ<N, we can detect a full recovery event.

 The main idea behind this approach can be significantly improved, with respect to the detection criterion and the final signal estimation, using  an increased number of samples provided by the RANSAC method, a classical method which has been extensively applied in machine learning <cit.> and  signal processing as well <cit.>.



 §.§ RANSAC-based CS Signal Denoising

In this section, we present the RANSAC-based CS denoising approach. The considered  signal model is

    y(n)=x(n)+ε(n)+ν(n)

where x(n) is a signal sparse in the DFT domain, ε(n) is Gaussian noise with variance σ^2_ε, and ν is the impulsive noise. The Gaussian noise is considered as a small noise and the samples with this kind of noise as inliers.  The impulsive noise causes outliers in the signal samples.

For the RANSAC-based denoising, we will use the following algorithm:

	
  * The considered signal is K-sparse. Select a small subset 𝕊 with S randomly selected samples x(n) at n ∈𝕊, such that the reconstruction for K-sparse signal is possible. 
	
  * The samples with indices in 𝕊 are used to reconstruct the signal, x_R(n), at all instants n=0,1,…,N-1.
	An approach to solve the CS reconstruction problem is  a two-step strategy as follows <cit.>: 
	
		
   Step 1: Detect the positions of nonzero elements in the sparsity domain,
		
   Step 2: Apply an algorithm for reconstruction with known positions of nonzero elements (use the positions from Step 1).
		
	
The measurements, x(n), are characterized by a linear nature: they are obtained as linear combinations of the sparsity domain elements, X(k), with the corresponding rows of the measurement matrix, 𝐀, acting as weights. This further implies that a back-projection of the measurements, 𝐲, to the measurement matrix, 𝐀, defined by
	
    𝐗_0=𝐀^H 𝐲=𝐀^H 𝐀𝐗

	can be used to estimate the positions of nonzero elements in 𝐗.  
	
	In an ideal case, the matrix 𝐀^H 𝐀 should ensure that the initial estimate, 𝐗_0, contains exactly K elements at positions {k_1,k_2,…,k_K}, for which the magnitudes are larger than the largest magnitude at the remaining positions. Under such condition, by taking the positions of these largest magnitude elements in 𝐗_0 as the set {k_1,k_2,…,k_K}, the algorithm for the known nonzero element positions, can be applied to reconstruct the signal using the pseudo-inversion as
	
    𝐗_K=(𝐀^H_K𝐀_K)^-1𝐀_K^H𝐲=pinv(𝐀_K)𝐲,
 
	where 𝐀_K is the matrix obtained from the measurement matrix 𝐀, by keeping the columns which correspond to the indices {k_1,k_2,…,k_K}.
	
	The reconstructed signal is 
	
    x_R(n)=IDFT{X_K0(k)}

	where X_K0(k) are zero-valued at all k except k∈{k_1,k_2,…,k_K}, where X_K0(k_i)=X_K(i).
	
	 The procedure can be iteratively implemented <cit.>. In the iterative procedure, the largest signal component is detected and estimated first (as it were K=1). The reconstructed component is subtracted from the available measurements, and the modified measurements are used to detect the position of the second-largest component. The two largest components are re-estimated together and subtracted from the available measurements. The procedure is continued until the subtraction of the estimated components from the available measurements does not produce sufficiently small (stopping criterion) value or until an assumed sparsity, K, is reached. 
	 
	 The iterative implementation is particularly suitable in the  case when the nonzero coefficient values significantly  differ. By reconstructing the detected large components, during the iterations, and removing their influence on the previously non-detected  components, smaller components will emerge <cit.>.

	
  * After the signal is reconstructed, the distance d_n of all signal samples (n,x(n)), n=0,1,…,N-1, from the estimated signal x_R(n) are calculated, d_n=|x_R(n)-x(n)|.
	
  * If a sufficient number of signal values is such that their distance from the reconstructed signal (model) is lower than an assumed threshold, for example, for the Gaussian distributed inliers d=2.5σ_ε, then all these points are included in the new set of signal values 
    𝔻={(n,x(n))  |    d_n≤ d },

	and the final reconstruction is calculated with all data from 𝔻. Note that the robust estimation of the standard deviation can be done using  the median absolute deviation (MAD), defined by
	
    MAD_x=m=0,1,…,N-1median{|x(m)-n=0,1,…,N-1median{x(n)}|}.

	The MAD value is related to the sample standard deviation as MAD_x=0.6745σ_x (for the Gaussian random variable). The real and imaginary parts are considered separately, for complex valued signals. 
	
  * If there was no sufficient number of signal values within the distance d, that is, card{𝔻}<T=3N/4, a new random small set  of signal samples, 𝕊, is taken and the procedure is repeated from Step 2. The value T is assumed based on the expected number of outliers. The assuming T=3N/4 means that we do not expect more than N/4 outliers. 
	
	
  * The procedure is stopped when the desired number of data points within 𝔻 is achieved, card{𝔻}≥ T=3N/4 or the maximum number of trials N_max is reached.
  

The previously described denoising approach is summarized in Algorithm 1. It exploits a matching pursuit CS reconstruction procedure, CSrec·, summarized in Algorithm 2. 

 The presented RANSAC-based denoising algorithm will produce the same results if other CS reconstruction methodologies are used, such as, for instance, the Bayesian CS reconstruction or the iterative hard thresholding (IHT). An overview of these procedures, along with their algorithmic presentation, suitable for implementation, can be found in <cit.>.







 §.§ Calculation Complexity

 The main difference between RANSAC and the standard CS methods is in the iterative procedure with random subsets of samples. Since this  is the main factor in
the computational complexity of this method, we will find the probability that
within M randomly selected observation samples, there are no outliers.

The probability that the first randomly chosen sample is not affected by an outlier is (N-I)/N since there are N samples in total and N-I of
them are inliers. We continue the process of random sample selection, and the probability that both the first and the second chosen samples are not outliers is N-I/NN-I-1/N-1. In this way, we can
calculate the probability that all of M randomly chosen samples x(n) at the 
positions n∈𝕊 are not outliers. This
probability is


    P(M,N,I)=∏_i=0^M-1N-I-i/N-i.

Since N-I-i/N-i<1, we can see that the probability P(M,N,I) decreases
as the number of terms in the product increases. Thus, in this kind of
reconstruction it is important to keep the number of samples M in the
observation set as low as possible, while satisfying the CS reconstruction conditions. 

In general, for an expected number of pulses I, the expected number of
random realizations to achieve at least one outlier-free reconstruction
using a subset of M samples is 

    N_it=1/P(M,N,I).


In classic literature dealing with the RANSAC, it is common to use the following calculation for the expected number of the iterations to get an outlier-free realization. The probability that one randomly selected sample is inlier is (N-I)/N. It is then assumed that this probability can be used for M samples. The probability that there is at least one outlier  in M samples is [1-((N-I)/N))^M]. Finally, the probability of an outlier-free realization in N_it such trials is      

    P=1-[1-((N-I)/N))^M ]^N_it

where

    N_it=ln(1-P)/ln(1-((N-I)/N))^M),
  with the given probability P.
This calculation is correct if the approximation 

    N-I-M/N-M≈N-I/N,
 holds, otherwise instead of ((N-I)/N))^M we should use P(M,N,I)=∏_i=0^M-1(N-I-i)/(N-i) to get the correct result.



 §.§ Expected Signal-to-Noise Ratio


Assume that the RANSAC has produced the correct result, that is, the reconstruction which is not influenced by the outliers.  This means that the final reconstruction is done using all consensus samples in the set 𝔻. This set of samples contains only inliers (with the Gaussian noise). Then, we can use a simple formula for the output SNR in the K-sparse signal, reconstructed from D samples,
 SNR_out, derived in <cit.>

    SNR_out=SNR_in0+10log(D/K).
 
Since the outliers are eliminated before the reconstruction, the input SNR is denoted by SNR_in0 and it includes the noise in inliers only. For reference, we will provide the total input SNR in notation SNR_in, which includes outliers as well. We will also provide the value of the SNR in the  mid-result, when the sample consensus is reached in a small subset 𝕊 with M samples. This SNR is denoted by SNR_out0 and its relation to the input SNR is 

    SNR_out0=SNR_in0+10log(M/K).
 
The improvement achieved by the RANSAC-based approach with respect to the random selection of the subsets and the concentration measure-based selection of the reconstruction set, is equal to 

    SNR_out-SNR_out0=10log(D/K)-10log(M/K)=10log(D/M).
    
This improvement can be significant, having in mind that we have to keep M as small as possible, in order to reduce the expected number of iterations N_it, which is crucial for the calculation complexity, for both the measure-based denoising and the RANSAC based denoising. The number of consensus samples, D, can be as high as the number of inliers, meaning that the ratio D/M could be very large. 



§ NUMERICAL AND STATISTICAL EXAMPLES


The results from the last two sections will now be illustrated on  numerical and statistical examples with  sparse noisy signals, containing inliers and outliers, reconstructed using the CS version of the RANSAC.



















































































Example 1:  
A general form of a noisy signal, sparse in the DFT domain, is considered
 
    y(n)=x(n)+ε(n)+ν(n),

where 
    x(n)=∑_i=1^KA_ke^j(2π k_i/N+ϕ_1)

is a signal sparse in the DFT domain with  K randomly positioned nonzero amplitudes and random phases. The Gaussian complex-valued noise ε(n) is with σ_ε=0.5. The impulsive Cauchy noise ν(n) is formed as ν=3ε_1(n)/ε_2(n)+j3ε_3(n)/ε_4(n), where ε_i(n), i=1,2,3,4 are unit variance, zero-mean, Gaussian noises. The impulsive noise is added in I signal samples. In the denoising of this signal, the CS form of the RANSAC is applied with random subsets of M samples, where M is small enough to keep the lowest possible calculation complexity, but sufficient to provide the correct reconstruction of a K sparse signal with acceptable probability.   

Several cases, for specific values of the total number of samples, N, sparsity, K, number of outliers, I, and the size of the RANSAC subset, M, are considered.











The case for N=128, K=5, I=16, and M=32 is presented in detail with illustrations in Fig. <ref>, Fig. <ref>,  Fig. <ref>, and Fig. <ref>.
This experiment is performed 100 times with different random realizations of signals, x(n), and noises, ε(n) and ν(n). The values of the number of iterations, N_it, in every realization is calculated and shown in Fig. <ref>. The final number of signal samples in the sample consensus, D, that is used in the final signal reconstruction is given in  Fig. <ref>. One of the realizations of the noisy signal, original signal, and the reconstructed signal is shown in Fig. <ref>. The noisy signal is marked by the red crosses, the reconstructed signal is denoted by the green circles, while the original signal is shown with the black dots. The SNR for the input signal x(n)+ε(n)+ν(n), SNR_in, for the input signal without impulsive noise x(n)+ε(n), SNR_in0, and for the reconstructed signal x_R(n),  SNR_out, for every realization, is given in  Fig. <ref>.

The statistical results averaged over all considered realizations are given in Table <ref>.





The theoretically expected improvement (Section <ref>) in the SNR (omitting the impulsive noise in the input signal) for the  case I=8, in Table <ref>, is 

    SNR_out-SNR_in0=10log(D/K)=10log(119.46/5)=13.77  dB

For other two cases, I=16 and I=24, we get 
    SNR_out-SNR_in0=13.46  dB

 and SNR_out-SNR_in0=13.14 dB, respectively. This is in high agreement with the statistical data in Table <ref>.

Example 2:  
Since the impulsive Cauchy noise may take some small values as well (some of the assumed I outliers may happen to be inliers, in reality), the expected number of iterations is smaller than the theoretically obtained result given by (<ref>). In order to check the expected number of iterations, N_it, against its theoretical value, avoiding the ambiguity of possible Cauchy noise inliers, we will provide that all I signal samples are certainly outliers. The impulsive noise is modified as ν(n) →ν(n)+100, to be sure that all of these samples are the outliers. Then, we have repeated the same experiment with 100 realizations and obtained N_it=10.74, while the theory in (<ref>) predicts P=0.0927 with N_it=1/P=10.78, for I=8. The same numerical experiment as in Example 1 is performed for I=16, and we get P=0.0071 with N_it=1/P=140.95, while the statistics for this case produced N_it=139.78. The same holds for I=24. The complete results of the experiment, with the modified impulsive noise, are given in Table <ref>.





In this case (of the modified impulsive noise), we can also check the result for the SNR ratio in the final RANSAC mid-result, when the consensus is detected on a small subset with M samples. Then,  
    SNR_out0-SNR_in0=10log(M/K)=10log(32/5)=8.06   dB

for all three considered cases, I=8, I=16, and I=24. This result is in complete agreement with the statistical results for these SNR values in Table <ref>. 

Example 3:  
The experiment form Example 1 is repeated with some other numbers of the available samples, N, sparsites, K, the number of impulsive disturbances, I, and the  samples used in the RANSAC-based CS reconstruction. The results are given in Tables <ref> and <ref> and further prove the efficiency of the proposed method and accuracy of the proposed SNR descriptors. 





Example 4:  
The experiment from Example 1 is repeated with the impulsive noise only, that is, when y(n)=x(n)+ν(n). As expected, for all considered numbers of outliers, the obtained results are within the computer precision accuracy.  They are given in Table <ref>. In this case, the value of d should very small. We  used d=10^-6, for this experiment.









§ CONCLUSION

Inspired by recent advances in compressive sensing and sparse signal processing, we have developed a RANSAC-based methodology for the detection of disturbances. Upon detecting disturbance-free samples, a compressive sensing algorithm is used for the recovery of the disturbed samples, which are considered as unavailable. The presented methodology is general – no specific assumptions have been made regarding the range of values or statistical behavior of the disturbance. The presented approach exploits the fact that disturbances degrade signal sparsity. It has been only assumed that the signals of interest exhibit sparsity in a known transformation domain. The theory has been verified on numerical examples.



§ ACKNOWLEDGMENT

This work was supported by the Croatian Science Foundation under the project IP-2020-02-4358.

































































10
        
              donoho2006
        D.L. Donoho, Compressed sensing.
        IEEE Transactions on Information Theory 52(4), 1289–1306
        (2006)
        
         candes2006
        E.J. Candès, J. Romberg, T. Tao, Robust uncertainty principles: Exact
        signal reconstruction from highly incomplete frequency information.
        IEEE Transactions on Information Theory 52(2), 489–509
        (2006)
        
        
        flandrin
        Flandrin, P., Borgnat, P.: Time-frequency energy distributions meet compressed
        sensing.
        IEEE Transactions on Signal Processing 58(6), 2974–2982
        (2010)
        
        
        
        cosamp
        D. Needell, J.A. Tropp, CoSaMP: Iterative signal recovery from
        incomplete and inaccurate samples.
        Applied and Computational Harmonic Analysis 26(3), 301–321
        (2009)
        
        
        LJSTut
        L. Stanković, E. Sejdić, S. Stanković, M. Daković, I. Orović, A Tutorial on Sparse Signal Reconstruction and Its Applications in Signal Processing. Circuits, Systems, and Signal Processing, 38, 1206–1263 (2019), https://doi.org/10.1007/s00034-018-0909-2
        
        LJSTdems
        L. Stanković, D. P. Mandić, M. Daković, I. Kisil, Demystifying the Coherence Index in Compressive Sensing. IEEE Signal Processing Magazine, 37(1), 152–162 (2020)
        
        impulsiveCS L. Stanković, M. Daković, S. Vujović, Reconstruction of Sparse Signals in Impulsive Disturbance Environments. Circuits, Systems and Signal Processing,  36,  767–794 (2016), DOI: 10.1007/s00034-016-0334-3.
        
        
               
        ImpulsiveHT M. Brajović, S. Stanković, I. Orović, M. Daković, and L. Stanković, Sparsity-Driven Impulsive Noise Removal: A Discrete Hermite Transform Case Study, in 27th Telecommunications Forum (TELFOR 2019), Belgrade, Serbia, (2019)
        
      impulsiveAudio M. Brajović, I. Stanković, L. Stanković, M. Daković, The DCT Domain Sparsity-Assisted Detection and         Recovery of Impulsively Disturbed Samples, submitted to Signal Processing, (2020).
        
                Zhao
        L. Zhao, Y. Hu, Y. Liu. Stochastic Gradient Matching Pursuit Algorithm Based on Sparse Estimation. Electronics 8(2), 165 (2019)
        
        Rui
        R. Hu,  Y. Fu , Z. Chen , Y.Xiang,  J. Tang. A Lorentzian IHT for Complex-Valued Sparse Signal Recovery. Circuits, Systems, and Signal Processing 37(2), 862–872 (2018)
        
        
        
       AccessCSquant I. Stanković, M. Brajović, M. Daković, C. Ioana, L. Stanković,  Quantization in Compressive Sensing: A Signal Processing Approach, IEEE Access, 8, 50611–50625 (2020), doi: 10.1109/ACCESS.2020.2979935
       
       nonuniformCS_geo L. Stanković, M. Brajović, I. Stanković, C. Ioana, M. Daković, Reconstruction Error in Nonuniformly Sampled Approximately Sparse Signals. IEEE Geoscience and Remote Sensing Letters, 17, (2020), in print, doi: 10.1109/LGRS.2020.2968137
       
	
        
      
        
        
        D1
        T. Blumensath: Sampling and reconstructing signals from a union of linear
        subspaces.
        IEEE Transactions on Information Theory 57(7), 4660–4671 
        (2011)
        
       
     
        
        Imp R.E. Carrillo, K.E. Barner, 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 4(2), 392–408 (2010)


      
        
        
        Machinparsuit1
        G. Davis, S. Mallat, M. Avellaneda, Adaptive greedy approximations.
        Constructive approximation 13(1), 57–98 (1997)
        
        djurovic2014quasi
        I. Djurović, V.V. Lukin, M. Simeunović, B. Barkat, Quasi maximum
        likelihood estimator of polynomial phase signals for compressed sensed data.
        AEU-International Journal of Electronics and Communications
        68(7), 631–636 (2014)
        
  	
        
        MJF
        Fadili, M.J., Starck, J.L., Murtagh, F.: Inpainting and zooming using sparse
        representations.
        The Computer Journal 52(1), 64–79 (2009)
        
        
      
        
     
        
        20
        E. Sejdić,  A. Cam, L. Chaparro, C. Steele, T. Chau,  Compressive
        sampling of swallowing accelerometry signals using time-frequency
        dictionaries based on modulated discrete prolate spheroidal sequences.
        EURASIP Journal on Advances in Signal Processing 101,
        1–14 (2012)
        
       
        
        LJTSP
        L. Stanković, I. Orović, S. Stanković, M.G. Amin,  Compressive
        sensing based separation of nonstationary and stationary signals overlapping
        in time-frequency.
        IEEE Transactions on Signal Processing 61(18), 4562–4572
        (2013).
        doi.10.1109/TSP.2013.2271752
        
        16a
        L. Stanković, S. Stanković, M.G. Amin,  Missing samples analysis in
        signals for applications to L-estimation and compressive sensing.
        Signal Processing 94, 401–408 (2014)
        
         
        CSC. Studer, P. Kuppinger, G. Pope, H. Bolcskei,  Recovery of sparsely corrupted signals.
        IEEE Transactions on Information Theory 58(5), 3115–3130 (2012)
        
        
               LJSAut
        S. Stanković, I. Orović, L. Stanković, An automated signal reconstruction method based on analysis of compressive sensed signals in noisy environment. Signal Processing 104, 43–50 (2014)
        
        LJSaudio L. Stanković, M. Brajović, Analysis of the Reconstruction of Sparse Signals in the DCT Domain Applied to Audio Signals, IEEE/ACM Transactions on Audio, Speech, and Language Processing, 26(7),  1216–1231 (2018)
          Isi
        I. Stanković, Recovery of images with missing pixels using a gradient
        compressive sensing algorithm.
        arXiv preprint arXiv:1407.3695  (2014)
            
            
            
            
            
            Orovic
            I. Orović, V. Papić, C. Ioana, X. Li,  S. Stanković, Compressive sensing in signal processing: algorithms and transform domain formulations. Mathematical Problems in Engineering (2016), (2016).
            
            Toroko
            A. Torokhti, P. Howlett, H. Laga, Estimation of stochastic signals under partially missing information. Signal Processing, 111, 199–209 (2015)
            
            Khan
            N. A. Khan, M. Mohammadi, Reconstruction of non-stationary signals with missing samples using time–frequency filtering. Circuits, Systems, and Signal Processing, 37 (8), 3175–3190 (2018)
            
            
            
            
            
            
        7a
        L. Stanković, S. Stanković, I. Orović, M.G. Amin, Robust
        time-frequency analysis based on the L-estimation and compressive sensing.
        IEEE Signal Processing Letters 20(5), 499–502 (2013)
        
        
      
        
          ramadan2012efficient
        Z.M. Ramadan, Efficient restoration method for images corrupted with impulse
        noise.
        Circuits, Systems, and Signal Processing 31(4), 1397–1406
        (2012)
        
        
        
        
           RoenkoLukin
        A.A. Roenko, V.V. Lukin, I. Djurović, Two approaches to adaptation of
        sample myriad to characteristics of SαS distribution data.
        Signal Processing 90(7), 2113–2123 (2010)
        
             SVV
        S.V. Vaseghi, Advanced digital signal processing and noise reduction
        (John Wiley & Sons, 2008)
        
          
        dadouchi2013automated
        F. Dadouchi, C. Gervaise, C. Ioana, J. Huillery, J.I. Mars, Automated
        segmentation of linear time-frequency representations of marine-mammal
        sounds.
        The Journal of the Acoustical Society of America 134(3),
        2546–2555 (2013)
        
        ahmad2012robust
        M.S. Ahmad, O. Kukrer, A. Hocanin, Robust recursive inverse adaptive
        algorithm in impulsive noise.
        Circuits, Systems, and Signal Processing 31(2), 703–710 (2012)
        
        
                you2013novel
        G.H. You, T.S. Qiu, A.M. Song, Novel direction findings for cyclostationary
        signals in impulsive noise environments.
        Circuits, Systems, and Signal Processing 32(6), 2939–2956
        (2013)
        
    
        
        Uniq
        L. Stanković, M. Daković,  On the uniqueness of the sparse signals
        reconstruction based on the missing samples variation analysis.
        Mathematical Problems in Engineering, Article ID 629759, 14 pages
        2015 (2015).
        doi.10.1155/2015/629759
        
     
        LJSBOOK
        L. Stanković, Digital Signal Processing with Selected Topics,
        (CreateSpace Independent Publishing Platform, An Amazon.com Company, 2015)
        
              
        ISTdems
        I. Stanković, I. Orović, M. Daković,  S. Stanković, Denoising of sparse images in impulsive disturbance environment. Multimedia Tools and Applications 77 (5), 5885–5905 (2018) 
        
                
        LJSTerr
        L. Stanković, M. Daković, I. Stanković,  S. Vujović, On the errors in randomly sampled nonsparse signals reconstructed with a sparsity assumption. IEEE Geoscience and Remote Sensing Letters, 14(12), 2453–2456 (2017) 
       
   Ljubisa
   L. Stanković, A measure of some time-frequency distributions
   concentration.
   Signal Processing 81(3), 621–631 (2001)
   
   
   Jokanovic B. Jokanović, M. G. Amin, Y. D. Zhang,  Reducing noise in the time-frequency representation using sparsity promoting kernel design, in Proc. SPIE 9109, Compressive Sensing III (91090B), (2014), doi: https://doi.org/10.1117/12.2050894
   
   
   
   viktor_impulsive  I. Volaric, V. Sucic, “On the noise impact in the L1 based reconstruction of the sparse time-frequency distributions,” 2016 International Conference on Broadband Communications for Next Generation Networks and Multimedia Applications (CoBCom), Gratz, 1–6 (2016)
   
              
      ML1  	 J. Matas, O. Chum, Randomized RANSAC with T(d,d) test, in David Marshall and Paul L. Rosin, editors, Proceedings of the British Machine Conference, 43.1–43.10,(BMVA Press 2002), doi:10.5244/C.16.43.   
      
      ML2 D. Nister, Preemptive RANSAC for live structure and motion estimation, in Proceedings Ninth IEEE International Conference on Computer Vision  Nice, France, 199–206 (2003), 
      doi: 10.1109/ICCV.2003.1238341
      
      ML3 H. Wang,  D. Suter,  Robust adaptive-scale parametric model estimation for computer vision. IEEE Transactions on Pattern Analysis and Machine Intelligence,  26(11) 1459–1474, (2004),
      doi: 10.1109/TPAMI.2004.109
      
      
      igorRANSAC I. Djurović, A WD-RANSAC Instantaneous Frequency Estimator,  IEEE Signal Processing Letters, 23(5), 757–761 (2016)
        






