>> Can non-uniform sampled signal be used to perfectly reconstruct the
>> original continuous time signal?

Theoratically speakig i.e. with an infinite number of signals samples, yes
you can perfectly reconstruct the nonuniformly sampled signal using for
exampe Lagrange interpolation formula instead of Shannon's.

However, with a finite ;i.e. a truncated set of samples perfect;
reconstruction is not feasible in a similar manner to that with the
conventional uniform sampling. There are plenty of publications on
trucation errors i.e. using a finite set of signal samples for uniform and
nonuniform samples. In general reconstructing a nonuniformly sampled data
is more computionally demanding in comparison to that of the uniform case.
One of the most popular nonuniform sampling reconstruction methods is
Minimum Energy Reconstruction (MER) by Yen which involves matrix
inversion.


>> What is the Nyquist sampling rate in the non-uniform case?

There is no Nyquist notion in nonuniform sampling as such. However if you
want to perfectly reconstruct the signal ; again theoratically; your
nonuniform sampling rate should be higher than that of the "Landau rate"
which is twice the actual bandwidth of the processed signal NOT the highest
frequency of present in the signal as in Nyquist rate. For Lowpass signals
Landua and Nyquist rates are identical whilst for bandpass or multiband
signals "Landau rate" can be "Significantely" lower than that of the
Nyquist.

Bashar

Rob Johnson wrote:

(snip)

> As has been discussed in the thread titled "how do you prove a signal
> that is time-limited cannot be bandlimited?", a band-limited function
> is entire, and an entire function is totally determined by its value
> on any open interval.  Therefore, if you can reconstruct a band-limited
> function for even a small interval of time, you can reconstruct it for
> all time.

The physics solution is a periodic function that goes to zero at the 
ends.  If the requirement is that it have the specified values over a 
finite range, with no requirement outside that range then a periodic 
solution works.  That is what the Fourier series does.  Some people 
don't like that solution, though it seems to be the favorite for car
CD players.

>>However, unlike the uniformly-sampled case, in which the signal
>>outside the interval does not affect the samples, we must assume
>>that the signal is zero* outside our interval of interest.

Why must we assume that?  If I want to record a CD I only care that
the signal is right for the length of the CD.  What happens before or 
after doesn't matter to my CD player.

> In the uniformly-sampled case, the same band-limited assumption is
> made.  It is the limit on the band of the signal that allows us to
> reconstruct it exactly from the samples.  How can we assume that the
> signal is zero outside our interval of interest?  This would mean we
> are assuming a signal that is band limited can also be time limited.

>>Consider the case of a signal of finite bandwidth constructed
>>by applying random scaling coefficients to a regular sequence
>>of sinc pulses. In the uniformly-sampled case, the pulses
>>outside our interval won't affect our samples. But in the
>>nonuniform case, we can't make that same argument.

> Why won't the sinc pulses outside the interval affect the samples? 
> sinc functions, being entire, effect the whole real line, except for
> isolated zeroes.  If sinc functions cancel, even on a small open set,
> they cancel everywhere.

Sinc are the solution when it is not time limited.  The solution will
be (slightly) different for the time limited case, closer to sinc as the 
time gets longer.

>>>Certainly it is possible to construct a band-limited function
>>>that agrees with the sampled function at finitely many sampled
>>>points. There are infinitely many functions with the same band
>>>limit that agree with the sampled function at the same sample
>>>points.  However, this is different than reconstructing the
>>>sampled signal.

>>Not quite. There's only one function with the exact same band
>>limits. There are infinitely many functions with the same
>>bandwidth. As in the uniformly-sampled case, they are called
>>images. As long as you know which image you're interested in,
>>you can select the correct interpolation function to reconstruct
>>the original signal exactly.

> This would imply that there is a finite dimensional set of functions
> whose Fourier Transform are supported in the given band.  This is
> definitely not true.

For time limited signals, use the Fourier series instead.

> Suppose we add one more sample point (x,y).  Since we are dealing with
> non-uniform samples, this should be no problem.  Using the same method
> to reconstruct the original signal, we can find a signal that matches
> the original signal at the other sample points and at (x,y) which has
> the same band limits.  Since we can do this for any y, we can find
> infinitely many functions with the same band limits which match the
> original signal at the other sample points.

Remember that infinity+1 and infinity-1 are still equal to infinity.

-- glen

Rob Johnson wrote:
> However, if the signal is band-limited, it cannot be time-limited,
> and so even though the coefficients of the sinc functions can be
> assumed 0 outside the time of the symphony, the actual signal of
> the symphony does not vanish.  It may be that to minimize the
> energy outside the time of the symphony, the coefficients of the
> sinc functions outside the time of the symphony need to be something
> other than 0.

I'm not interested in minimizing the energy, only the information
content (the number of unknowns). The simplest way to do that is
to make them zero. If you want to assign nonzero values to meet
some additional criterion, as long as they're derived from what
you know about the interval in question, I guess that doesn't
change the overall information content.

-- Dave Tweed

In article <438B0344.815A671@acm.org>,
David Tweed <dtweed@acm.org> wrote:
>robert bristow-johnson wrote:
>> David Tweed wrote:
>> > robert bristow-johnson wrote:
>> > > it seems to me that you need to solve a system of an infinite
>> > > number of equations that have an infinite number of unknowns,
>> >
>> > No, you only have one equation for each nonuniform sample you took.
>> 
>> yeah, you're right, but i keep imagining the premise of the OP was that
>> many, or all of the samples are, in general, not lying at uniformly
>> spaced times.
>> 
>> > The solution is the corresponding set (same number) of uniform samples.
>> > You have to evaluate the sinc function N^2 times to get the coefficients
>> > for the equations.
>> 
>> whereas you don't have more than one equation for only one out-of-step
>> sample, you still have to (if you're math is gonna be perfect) evaluate
>> an infinite number of sinc(.) functions.  of course, we would say only
>> a certain finite number of neighboring samples can affect the sole
>> out-of-step sample, but if one is hoping to extrapolate the first
>> movement of Beethoven's Ninth into even the second movement (my fav
>> since the Huntley-Brinkley Report on NBC), i think that person would
>> need all infinity sinc(.) functions.  and would need infinite
>> precision.
>
>In order to make this tractable, you have to assume that the all of
>the sinc coefficients outside of some interval (before the beginning
>and after the end of the symphony) are all zero. I thought that was
>implicit.

However, if the signal is band-limited, it cannot be time-limited, and
so even though the coefficients of the sinc functions can be assumed 0
outside the time of the symphony, the actual signal of the symphony
does not vanish.  It may be that to minimize the energy outside the
time of the symphony, the coefficients of the sinc functions outside
the time of the symphony need to be something other than 0.

Rob Johnson <rob@trash.whim.org>
take out the trash before replying

David Tweed <dtweed@acm.org> writes:

> I think we're all violently in agreement.

Don't ya hate that? :-)

Ciao,

Peter K.

robert bristow-johnson wrote:
> David Tweed wrote:
> > robert bristow-johnson wrote:
> > > it seems to me that you need to solve a system of an infinite
> > > number of equations that have an infinite number of unknowns,
> >
> > No, you only have one equation for each nonuniform sample you took.
> 
> yeah, you're right, but i keep imagining the premise of the OP was that
> many, or all of the samples are, in general, not lying at uniformly
> spaced times.
> 
> > The solution is the corresponding set (same number) of uniform samples.
> > You have to evaluate the sinc function N^2 times to get the coefficients
> > for the equations.
> 
> whereas you don't have more than one equation for only one out-of-step
> sample, you still have to (if you're math is gonna be perfect) evaluate
> an infinite number of sinc(.) functions.  of course, we would say only
> a certain finite number of neighboring samples can affect the sole
> out-of-step sample, but if one is hoping to extrapolate the first
> movement of Beethoven's Ninth into even the second movement (my fav
> since the Huntley-Brinkley Report on NBC), i think that person would
> need all infinity sinc(.) functions.  and would need infinite
> precision.

In order to make this tractable, you have to assume that the all of
the sinc coefficients outside of some interval (before the beginning
and after the end of the symphony) are all zero. I thought that was
implicit.

-- Dave Tweed

Rob Johnson wrote:
> You mean an infinite sum of regularly spaced sinc functions with random
> coefficients?  It depends on how you select the random coefficients as
> to whether the sum even converges.  However, if your sum converges,
> then yes, if you know the sum over a non-empty open interval, you know
> the sum over the whole real line.

I finally realized what you were trying to tell me. Sorry for being
slow.

Yes, when you look at the intervals between uniform samples, they are
affected by the samples outside our sampling interval, so there are
indeed an infinite number of continuous functions that can fit our
samples. It's pretty implicit that when reconstructing from uniform
samples that you want the simplest one, which assumes that those
other samples are zero, and I was making the same assumption about
nonuniform sampling. I think we're all violently in agreement.

-- Dave Tweed

Joseph Fagan wrote:
> "Michel Rouzic" <Michel0528@yahoo.fr> wrote in message
> news:1131784415.779792.104570@g14g2000cwa.googlegroups.com...
> >
> > lucy wrote:
> >> What is the Nyquist sampling rate in the non-uniform case?
> >
> > um.. i'll take the risk of trying to answer and say that it must be the
> > same one as if you had an uniform sampling rate matching to the
> > shortest distance between two samples in your non-uniformly sampled
> > signal. but i wouldnt be surprised if my answer was wrong or off-topic
> > (i'm a newbie kinda)
> >
> "shortest distance" - do you mean "longest"?

yup I think. the only confusing thing with that is that the signal
would contain frequencies about the nyquist frequency.... i think..

David Tweed wrote:
> robert bristow-johnson wrote:
> > it seems to me that you need to solve a system of an infinite
> > number of equations that have an infinite number of unknowns,
>
> No, you only have one equation for each nonuniform sample you took.

yeah, you're right, but i keep imagining the premise of the OP was that
many, or all of the samples are, in general, not lying at uniformly
spaced times.

> The solution is the corresponding set (same number) of uniform samples.
> You have to evaluate the sinc function N^2 times to get the coefficients
> for the equations.

whereas you don't have more than one equation for only one out-of-step
sample, you still have to (if you're math is gonna be perfect) evaluate
an infinite number of sinc(.) functions.  of course, we would say only
a certain finite number of neighboring samples can affect the sole
out-of-step sample, but if one is hoping to extrapolate the first
movement of Beethoven's Ninth into even the second movement (my fav
since the Huntley-Brinkley Report on NBC), i think that person would
need all infinity sinc(.) functions.  and would need infinite
precision.

i didn't want to get sucked into this thread too much.

--

r b-j

"Life's a bitch... "






























"... and then you die."

In article <43831847.FD673EF7@acm.org>,
David Tweed <dtweed@acm.org> wrote:
>Rob Johnson wrote:
>> As has been discussed in the thread titled "how do you prove a signal
>> that is time-limited cannot be bandlimited?", a band-limited function
>> is entire, and an entire function is totally determined by its value
>> on any open interval.  Therefore, if you can reconstruct a band-limited
>> function for even a small interval of time, you can reconstruct it for
>> all time.
>
>Sorry, I haven't been following that thread. I'll have to take a
>closer look at it. How does my bandlimited signal representing an
>infinite series of random numbers fit into that argument?

You mean an infinite sum of regularly spaced sinc functions with random
coefficients?  It depends on how you select the random coefficients as
to whether the sum even converges.  However, if your sum converges,
then yes, if you know the sum over a non-empty open interval, you know
the sum over the whole real line.

>> Why won't the sinc pulses outside the interval affect the samples?
>> sinc functions, being entire, effect the whole real line, except for
>> isolated zeroes.  If sinc functions cancel, even on a small open set,
>> they cancel everywhere.
>
>Because the uniform samples are taken at those isolated zeros.

This is true if the samples are taken at the same frequency as the
sinc functions are placed.  I was not sure that this was assumed.

>A set of uniform samples can't tell you anything about the function
>outside the interval they cover; I don't see why a set of nonuniform
>samples would have any greater power.

When I had asked

|| Are you saying that you can exctly reproduce any band-limited
|| signal with finitely many samples?

you replied

|Not for all time; only for the finite interval defined by N/BW.
|If you want to reconstruct it for all time, the bandwidth would
|have to be zero for any finite number of samples.

This indicated that you could exactly reproduce a band-limited signal
over a limited time, with finitely many samples.  However, if you can
exactly reproduce a band-limited function over a non-empty open
interval, you can reproduce it over the whole real line.  To exactly
determine any point in the signal other than at the sampled points,
we must know the values at all the uniformly spaced sample points.
However, with some restrictions on the size of the signal away from
the interval of interest, we can approximate the signal inside the
interval of interest.

>Remember, I didn't say that the signal must be assumed to be time
>limited (did you read my footnote?). I said that the uniform samples
>outside the interval must be assumed to be zero.

How does assuming this have any bearing on the original signal?

>In uniform sampling, the samples outside our interval can't affect
>our samples, so they can be anything. In nonuniform sampling, they
>do affect our samples, so if they are not zero, then our samples
>represent a different function within the interval.

Yes, I totally agree, but why does assuming they are zero reproduce
the original signal any better than other assumptions?

Even with uniform samples, we cannot exactly reproduce the original
signal without the entire time history of samples (both forward and
back).  Why should we be able to do better with non-uniform samples?

Rob Johnson <rob@trash.whim.org>
take out the trash before replying