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

Question

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.

Answer 1

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.

I do not think injecting NaN gonna help, instead let's see the ignored data as dimension reduction property in CS measurements. 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) = [];

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$. (as a side note just be aware, for the case of measurement matrix you posed in your question, it can violate coherence requirement.)

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 may find it interesting.