Non-Uniform Sampling

[3iMaJ]

Has anyone ever thought about non-uniform sampling? Forget the obvious hardware problems and think about it mathematically. Sampling is used as a spectral estimation process, however if you note the Nyquist-Shannon theorem you'll see that the sampling time-width (the time you sample over) is allowed to go to infinity. Allowing the timewidth to go to infinity asymptotically drives the spectral estimation error to zero. However, if we limit the timewidth to T, and uniform sample, our estimation is inherently biased to multiples of the sampling frequency, but not samples in between, DPS guys will say that the timewidth T sets the frequency resolution.

So, what if we non-uniformly sample? What is the best way to do so? What I mean by this is if I'm going to take N samples over a timewidth T where is the best place to take my samples? I would bet its non-uniformly. The only thing that our good friend Nyquist demands is that two samples be spaced close enough so that we don't alias, but he says nothing about how this is to be achieved.

I think uniform sampling is very easy and obviously works well, but I've not seen much work done where we ask ourselves if uniform sampling is really the best way to estimate a spectrum.

 

[dknguyen]

THe term non-causal system comes to mind I think. Isn't it a catch 22 problem? You're sampling to read the signal but in order to know when to sample you have to know the signal, so you have to read it?

For a periodic signal this would work (it'd be like a type of undersampling almost). But for a unpredictable signal, I think that above.

 

[3iMaJ]

I don't have a specific signal in mind, what I think of is that I have a signal with a bandwidth B, and I'd like to estimate that signal with N samples over a time width T. The question is where do I sample in order to minimize the spectral estimation error.

Let me relate this to uniform sampling analog. If you wanted to know what a spectrum of a signal looked like, you'd sample it and take the fourier transform. We would call the fourier transform you're estimator, you're correlating all possible frequencies with your signal in order to estimate what frequencies you're signal has.

Non-uniform sampling might work much the same way, although I don't think we'd want to use the fourier transform for our spectral estimation (well the DFT) since the primary assumption of the DFT is uniform sampling, so we'd have to come up with some other spectral estimator tool, perhaps an MMSE or maximum liklihood estimator.

 

[dknguyen]

Well I think there would need to be some very fast real time analysis going on between samples to make the next sample spaced appropriately in time. As a result, I think there would be almost a lag/transient response time that would occur when the ADC would change to the increased bandwidth for that instance of the signal.

 

[3iMaJ]

I think generally speaking you know the bandwidth of the signal before hand, so I think the entire estimation process could be done a priori, and as such you'd know when to sample, w/o having to do any predictions. I'm not sure, I'm working on an algorithm to find out though, I'll post some results when I feel I have something meaningful.

 

[Papabravo]

I would try Chebyshev knots to see if they offer any advantage. If should be a fairly simple MATLAB experiment. In approximating functions it leads to polynomials which minimize the absolute error over the interval of interest.

 

[Roff]

Do you mean like random sampling? Google for more info. I know nothing about it myself.

 

[3iMaJ]

Sort of. The type of sampling that I have in mind would be non-uniform, but not random either. There is probably a ton of research on random sampling, but that isn't what I had in mind. I want to sample in such a way as to minimize the estimation error of a spectral estimation. What I envision is a filter matrix that would be multiplied by a time domain function that will estimate the spectrum with as little error as possible.

There is a ton of DPS research in the area of spectral estimation. The music algorithm for example is a good way of estimating the location of discrete frequencies in a spectrum, but does nothing for estimating the amplitude. Now there are a myriad of ways to estimate the amplitude and what not, but the common assumption to most methods is uniform sampling.

If you relate this to the spatial analog of a linear array. There is plenty of research to show that the side lobes in the beam pattern of a linear array can be reduced by placing spatial elements in a non linear fashion. Temporal sampling is exactly the same thing as the spatial analog. They're not similar problems, they're identical. I'd just like to use some of that non-uniform stuff they use for linear arrays for temporal sampling.

Consider for a moment Shannon's sampling theorem where he shows that a continuous time domain function can be reconstructed using sinc functions and discrete samples. But one important assumption to this theorem is the infinite time width. Why is that important? Because as the time width goes to infinity the sinc functions become mutually orthogonal. If you assume a finite time width, they are no longer orthogonal and introduce an error in the reconstructed continuous time signal.

I just think by sampling in a non-uniform way this error can be reduced more than it can be by uniform sampling.

 

[3iMaJ]

I finished my algorithm, and I've posted my results. The first picture shows the expected mean squared error of the spectral estimation, and the second shows the actual spectral estimation compared to the FFT. Certainly there are better ways to estimate a spectrum than the FFT but I haven't put the time into searching out these methods let alone implement them since its such a quick example. The time domain signal iss(t) = sin(2*pi*10t) + sin(2*pi*8t + phi), sampled at 25 Hz with a time width of 3 seconds. So the fourier transform would be delta functions at +-10 hz and +-8 hz, but note I've not assumed an infinite timewidth or bandwidth, so they're not going to be that exactly.