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


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.


1 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;
Phi = eye(256);
y = Phi * x;
Psi=dctmtx(N)';  % Transposed DCT matrix is like inverted DCT
recovered=SolveOMP(Phi*Psi,y); % any solver available!
plot(CS_intepolate,'*'); hold on; plot(x,'r')

enter image description here (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.

  • $\begingroup$ 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? $\endgroup$
    – bla
    Jan 30, 2020 at 18:35
  • $\begingroup$ stackoverflow.com/questions/38832474/… $\endgroup$
    – MimSaad
    Jan 30, 2020 at 22:59
  • $\begingroup$ 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? $\endgroup$
    – bla
    Jan 31, 2020 at 7:08
  • $\begingroup$ 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 $\endgroup$
    – MimSaad
    Jan 31, 2020 at 12:45
  • $\begingroup$ @MimSaad, The link to the course doesn't work. It is always better link with a description which in case the links is dead will assist searching for it (In that case, name of the course, name of the lecture note, etc...). $\endgroup$
    – Royi
    Dec 12, 2021 at 2:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.