# Can compressed sensing be used instead of intepolation for missing values?

Consider a signal that is sparse in frequency, but it measured in the time domain, for example (in matlab):

t=linspace(0,4,2^8);
x=sin(2*pi*t)+sin(2*pi*3*sqrt(2)*t+pi/4);


let's say that some fraction of the signal is missing, for example the 120-130 measurement:

x(120:130)= NaN;


using standard interpolation methods (nearest neighbors, spline, etc) will fail to reproduce the missing signal, because these methods do not make use of frequency information of the signal.

I thought that by using compressed sensing (L1-magic for example) and random sampling of the signal outside the missing part I'll be able to recover the signal and the missing part, but looking into it I saw that I still need the full signal to create a measurement vector via y=Ax, where A is the sensing matrix.

If x has NaN values then y will be all NaNs, and the entire process is compromised.

So how can I "compress" my sampling by not having the full signal even though it has the information needed? (assuming the sparsity above)...

I'm aware I may use other techniques but I'm curious how to use CS.

Yes, at least in the above case it is possible. Though it might not be computationally as cheap as other methods such as least squares based curve fitting methods.

I do not think injecting NaN gonna help, instead let's look at the ignored data as dimension reduction feature of CS. Here, the measurement matrix is basically an identity matrix that some of its row (120:130) have been removed:

A = eye(256);
A(120:130) = [];


Just be aware, for the case of measurement matrix you posed in your question, it might violate coherence requirement. If we apply the above matrix, we cut away samples of 120 to 130. Now assume the resultant as measurement vector $$y$$ and $$A$$ as measurement matrix. This is how CS recovery algorithms work, e.g. in case of Fourier sparse signals, we have an incomplete set of measurements $$y$$ ,the goal is to find sparsest set $$a$$ such that if we apply A matrix, yields something close enough to $$y$$.

N = 2^8;
t=linspace(0,16,N);
x=sin(2*pi*t)+sin(2*pi*3*sqrt(2)*t+pi/4);
x=x';
Phi = eye(256);
Phi(10:17,:)=[];
y = Phi * x;
Psi=dctmtx(N)';  % Transposed DCT matrix is like inverted DCT
recovered=SolveOMP(Phi*Psi,y); % any solver available!
CS_intepolate=idct(recovered);
plot(CS_intepolate,'*'); hold on; plot(x,'r')


(blue line is CS interpolated and red is original signal)

BTW, as far as I understood, you suggest to mix the remaining data. See it as system of equations, blending the current equations into new ones, does not add any new information or constraint to the system, so it is not helping.

Also I believe there is connection with CS and data completion. You might find it interesting also.

• Hi MimSaad. So instead of injecting NaN, i can place just a dummy value (because NaNs behavior is a bit problematic) , delete the relevant rows of A and that it. You mentioned cheaper methods to for this spectral interpolation, i'd appreciate what you had in mind? – bla Jan 30 '20 at 18:35
• stackoverflow.com/questions/38832474/… – MimSaad Jan 30 '20 at 22:59
• this works when you know your model, the sin function in my question is just an example. What if I know that my signal is sparse but in a different basis? say bessel functions instead of sin? – bla Jan 31 '20 at 7:08
• There are methods for non-linear and arbitrary function basis, interpolation however, this is a good question, I think a research on that could be useful and I am interested in – MimSaad Jan 31 '20 at 12:45