| Author |
Message |
William Hughes
Guest
|
 Posted:
Tue Nov 22, 2005 1:16 am Post subject:
Re: question about non-uniform sampling? |
|
|
Jerry Avins wrote:
| Quote: | William Hughes wrote:
... Do you have another argument?
[assume the first second was silence. Will the samples
obtained be 0. No Are they too small for practical
work. Yes.]
Another argument: you can talk about it, but you can't do it.
|
In other words it is possible in theory but not in practice.
-William Hughes |
|
| Back to top |
|
 |
David Tweed
Guest
|
| Posted:
Tue Nov 22, 2005 1:16 am Post subject:
Re: question about non-uniform sampling? |
|
|
Rob Johnson wrote:
| Quote: | Dave Tweed wrote:
No, you only have one equation for each nonuniform sample you
took. 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.
Are you saying that you can exctly reproduce any band-limited
signal with finitely many samples?
|
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.
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.
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.
| Quote: | 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.
All my system of equations shows is that a set of nonuniform
samples can be directly transformed into a set of uniform
samples, to which all of the usual constraints apply. It isn't
fundamentally different from any other form of resampling.
-- Dave Tweed
* More precisely, the uniform samples of the signal are zero
outside the interval. Obviously, the interpolation "tails"
from within the interval will extend beyond it. If we're
extrapolating rather than interpolating, we must also make
sure that none of our nonuniform samples occur at the same
instants as any of those zero-valued uniform samples. |
|
| Back to top |
|
|
Ron N.
Guest
|
| Posted:
Tue Nov 22, 2005 7:45 am Post subject:
Re: question about non-uniform sampling? |
|
|
Jerry Avins wrote:
| Quote: | Careful preparation of the signal before it's sampled is really a
red herring. The usual case is something like a log of recorded
measurements, each with time of measurement noted. Suppose them to be
the level of a river or the speed of a ship. On most days, there are two
measurements, some have three or more, and for a few days there are
none. Given these data, How well can the continuous function be
deduced?
|
Theory says nothing about deducing the continuous function
unless that function is bandlimited (or otherwise similarly
constrained in derivatives and such for other interpolation
methods).
Often "good enough" approximations can be made if the function
is "close enough" to bandlimited. In audio one typically uses
a pre-sampling physical or analog low pass filter, and then only
attempts to reconstruct the post low pass filtered function to
within some bits of precision. If the filter is perfect, one
shouldn't be able to make *any* deductions about the
continuous signal prior to filtering and outside the filters
passband.
So I think it makes sense to talk about reconstruction of
only signals from samples taken after the filter process (even
if that filter is a multi-hour wide infinite precision FIR or
FFT/IFFT in the symphony reconstruction example).
IMHO. YMMV.
--
rhn A.T nicholson d.O.t C-o-M |
|
| Back to top |
|
|
Guest
|
| Posted:
Tue Nov 22, 2005 8:15 am Post subject:
Re: question about non-uniform sampling? |
|
|
The AES paper I wrote in the 80's that RBJ referenced showed that if
you have a "periodically-missing" sample, you can recover a bandlimited
signal from the non-uniform samples as long as the bandwidth is less
that 1/2 of the AVERAGE sampling rate. It's a pretty simple idea based
on M-band filters (as opposed to half-band filters) where every Mth
sample is 0. You can show that the missing sample point can be
completely interpolated from surrounding points with no error.
I have been looking recently at the Reimann Zeta function (sum of
(1/N^s), evaluated with S = 0.5 +/- jw; the inverse Laplace transform
gives a log-time sequence) as a sampling function where the samples
fall on log(N) time points. I'm pretty sure buried deep in the math is
a theorem that states that certain functions can be recovered full from
a log(N) sampling sequence. Of course this is of no practical use
whatsoever other than pure intellectual stimulation.
Bob Adams
Analog Devices Inc |
|
| Back to top |
|
|
robert bristow-johnson
Guest
|
| Posted:
Tue Nov 22, 2005 8:59 am Post subject:
Re: question about non-uniform sampling? |
|
|
nice to see your phosphors again, Bob. do you have that paper in PDF?
because i can't find the AES preprint i used to have of it.
r b-j
in article 1132625749.539998.277620@g43g2000cwa.googlegroups.com,
robert.w.adams@verizon.net at robert.w.adams@verizon.net wrote on 11/21/2005
21:15:
| Quote: | The AES paper I wrote in the 80's that RBJ referenced showed that if
you have a "periodically-missing" sample, you can recover a bandlimited
signal from the non-uniform samples as long as the bandwidth is less
that 1/2 of the AVERAGE sampling rate. It's a pretty simple idea based
on M-band filters (as opposed to half-band filters) where every Mth
sample is 0. You can show that the missing sample point can be
completely interpolated from surrounding points with no error.
I have been looking recently at the Reimann Zeta function (sum of
(1/N^s), evaluated with S = 0.5 +/- jw; the inverse Laplace transform
gives a log-time sequence) as a sampling function where the samples
fall on log(N) time points. I'm pretty sure buried deep in the math is
a theorem that states that certain functions can be recovered full from
a log(N) sampling sequence. Of course this is of no practical use
whatsoever other than pure intellectual stimulation.
Bob Adams
Analog Devices Inc
|
--
r b-j rbj@audioimagination.com
"Imagination is more important than knowledge." |
|
| Back to top |
|
|
Rob Johnson
Guest
|
| Posted:
Tue Nov 22, 2005 5:16 pm Post subject:
Re: question about non-uniform sampling? |
|
|
In article <438224E3.C71FCF04@acm.org>,
David Tweed <dtweed@acm.org> wrote:
| Quote: | Rob Johnson wrote:
Dave Tweed wrote:
No, you only have one equation for each nonuniform sample you
took. 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.
Are you saying that you can exctly reproduce any band-limited
signal with finitely many samples?
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.
|
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.
| Quote: | 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.
|
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.
| Quote: | 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.
| Quote: | 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.
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.
Rob Johnson <rob@trash.whim.org>
take out the trash before replying |
|
| Back to top |
|
|
David Tweed
Guest
|
| Posted:
Tue Nov 22, 2005 5:16 pm Post subject:
Re: question about non-uniform sampling? |
|
|
Rob Johnson wrote:
| Quote: | 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?
| Quote: | 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.
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.
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.
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.
-- Dave Tweed |
|
| Back to top |
|
|
Rob Johnson
Guest
|
| Posted:
Wed Nov 23, 2005 1:16 am Post subject:
Re: question about non-uniform sampling? |
|
|
In article <43831847.FD673EF7@acm.org>,
David Tweed <dtweed@acm.org> wrote:
| Quote: | 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.
| Quote: | 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.
| Quote: | 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.
| Quote: | 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?
| Quote: | 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 |
|
| Back to top |
|
|
Ron N.
Guest
|
| Posted:
Wed Nov 23, 2005 1:16 am Post subject:
Re: question about non-uniform sampling? |
|
|
David Tweed wrote:
| Quote: | Because the uniform samples are taken at those isolated zeros.
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.
|
A set of uniform samples can't tell you everything about the
function inside the interval either, because they are taken at
the zeros of all possible sinc function tails related to samples
outside the interval. A nonuniform sampling would be taken
at points which are not zero for samples/sinc functions outside
the interval, so would be controlled by those outside samples
I think.
In terms of information, perhaps the location in time of each
non-uniform sample conveys more information about the total
signal/function that would only the sample order and rate in
the uniform sampling case.
IMHO. YMMV.
--
rhn A.T nicholson d.O.t C-o-M |
|
| Back to top |
|
|
Ron N.
Guest
|
| Posted:
Wed Nov 23, 2005 1:16 am Post subject:
Re: question about non-uniform sampling? |
|
|
David Tweed wrote:
| Quote: | 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.
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.
|
They can't be zero if the signal is bandlimited. Even if the signal
is only low pass filtered but with a roll-off somewhere below the
Nyquist frequency, this may not allow a few of the adjacent and
post filtered samples to be zero and still be possible legal outputs
of the low pass filter.
| Quote: | 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.
|
They can't be anything. Bandlimited means that the possible
legal values outside the inverval are restricted by the values
inside the interval. Often, in the real world, the quantization
of the samples and the ripple in the filter allow a near infinite
degree of freedom more than a few samples away from the edges
of the sampling interval, but this isn't true in the theoretical
case of perfect bandlimiting and infinite precision sampling.
IMHO. YMMV.
--
rhn A.T nicholson d.O.t C-o-M |
|
| Back to top |
|
|
robert bristow-johnson
Guest
|
| Posted:
Thu Nov 24, 2005 9:16 am Post subject:
Re: question about non-uniform sampling? |
|
|
David Tweed wrote:
| Quote: | 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.
| Quote: | 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." |
|
| Back to top |
|
|
Michel Rouzic
Guest
|
| Posted:
Mon Nov 28, 2005 1:16 am Post subject:
Re: question about non-uniform sampling? |
|
|
Joseph Fagan wrote:
| Quote: | "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.. |
|
| Back to top |
|
|
glen herrmannsfeldt
Guest
|
| Posted:
Mon Nov 28, 2005 4:16 pm Post subject:
Re: question about non-uniform sampling? |
|
|
Jerry Avins wrote:
| Quote: | William Hughes wrote:
In other words it is possible in theory but not in practice.
OK. We agree on that.
Lucy, in beginning this thread, asked,
|
###################
| Quote: | Can non-uniform sampled signal be used to perfectly reconstruct the
original continuous time signal?
What is the Nyquist sampling rate in the non-uniform case?
How would you answer her?
|
The word perfectly, to me, asks for the theoretical answer.
Practically, it is very close but not perfect.
-- glen |
|
| Back to top |
|
|
David Tweed
Guest
|
| Posted:
Mon Nov 28, 2005 5:16 pm Post subject:
Re: question about non-uniform sampling? |
|
|
Rob Johnson wrote:
| Quote: | 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 |
|
| Back to top |
|
|
David Tweed
Guest
|
| Posted:
Mon Nov 28, 2005 5:16 pm Post subject:
Re: question about non-uniform sampling? |
|
|
robert bristow-johnson wrote:
| Quote: | 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 |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in