question about non-uniform sampling?

Carlos Moreno wrote:
> Jerry Avins wrote:
> 
>>>  [...]
>>> The reasoning can be extended to any number N, no matter how
>>> large.
>>>
>>> I know this is not rigurous -- in particular, this shows that
>>> the trick works for N samples taken at positions other than
>>> the corresponding positions, no matter how large;  but this
>>> proves nothing about an "infinity" of samples taken non-
>>> uniformly...  Still, the result does suggest that you still
>>> need the amount of samples that totals the same amount of
>>> samples required in uniform sampling  (suggesting that your
>>> Nyquist condition is given by the average sampling rate).
>>
>>
>> It doesn't. There's a limit to how non-uniform the sampling can be 
>> allowed to be. The example given above, of an hour's worth of music 
>> sampled for half an hour at twice the minimum rate for the bandwidth, 
>> is an adequate counterexample 
> 
> 
> No it's not.  Not only is it not an *adequate* counterexample;
> it's not even a counterexample.
> 
> The above reasoning has nothing to do with practical applicability
> of the issue.  The above reasoning is purely mathematical -- or
> I should rather say, it works purely at the mathematical level.
> 
> If the music you're talking about is truly *band-limited*, then
> it spans from time -infinity to +infinity.  So, assuming that
> the signal is *strictly bandlimited* between DC and 20kHz, then
> yes, taking one hour worth of samples (at least 1 + 40000*3600
> samples) in an interval of 1 microsecond right before the hour
> of music began *is* enough to fully, completely, and perfectly
> (i.e., 100% accurately) reconstruct the whole hour of music;
> provided that the remaining infinity of samples before and
> after the sampleless hour is there, and provided that the
> 1+40000*3600 samples are distinct, and at times different from
> all the remaining uniform samples).
> 
> Again:  *mathematically* speaking, the signal is fully recoverable
> (analytically;  or numerically, if we could count on "infinite
> precision" representation of real numbers).

Wonderful! If I've composed two movements of a symphony, how many more 
can I deduce using the principles of DSP without actually composing any 
more music? Id you did the same deducing, would you arrive at the same 
score?

In the real world, we sample time-limited signals and reconstruct them 
as if they were bandlimited. Don't knock it: not only does it work, 
nothing else is possible,

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

cs_post...@hotmail.com wrote:
> > Ron N. wrote:
> > > For this counterexample to work, the response of the lowpass filter
> > > for each sample would have to be over an hours worth of samples wide
...
> to which Jerry Avins replied:
> > What if it's a request show and the second half-hour's music isn't known
> > until after the sampling stops? Suppose even that the program is known
> > in advance. Do you suggest that it might be possible to reconstruct the
> > last movement of Beethoven s 9th Symphony from a gross oversampling of
> > the first three?
>
> Yes, provided you pass the samples through the anti-causal low pass
> filter that Ron postulated.

It wouldn't have to be anti-causal.  A symmetric low-pass FIR filter
with enough taps and bits of precision would work.  Of course there
would be a significant filter delay (roughly the length of the entire
symphony) before you would see the first output samples.


-- 
rhn A.T nicholson d.O.t C-o-M

cs_post...@hotmail.com wrote:
> > Ron N. wrote:
> > > For this counterexample to work, the response of the lowpass filter
> > > for each sample would have to be over an hours worth of samples wide
...
> to which Jerry Avins replied:
> > What if it's a request show and the second half-hour's music isn't known
> > until after the sampling stops? Suppose even that the program is known
> > in advance. Do you suggest that it might be possible to reconstruct the
> > last movement of Beethoven s 9th Symphony from a gross oversampling of
> > the first three?
>
> Yes, provided you pass the samples through the anti-causal low pass
> filter that Ron postulated.

It wouldn't have to be anti-causal.  A symmetric low-pass FIR filter
with enough taps and bits of precision would work.  Of course there
would be a significant filter delay (roughly the length of the entire
symphony) before you would see the first output samples.


-- 
rhn A.T nicholson d.O.t C-o-M

cs_post...@hotmail.com wrote:
> > Ron N. wrote:
> > > For this counterexample to work, the response of the lowpass filter
> > > for each sample would have to be over an hours worth of samples wide
...
> to which Jerry Avins replied:
> > What if it's a request show and the second half-hour's music isn't known
> > until after the sampling stops? Suppose even that the program is known
> > in advance. Do you suggest that it might be possible to reconstruct the
> > last movement of Beethoven s 9th Symphony from a gross oversampling of
> > the first three?
>
> Yes, provided you pass the samples through the anti-causal low pass
> filter that Ron postulated.

It wouldn't have to be anti-causal.  A symmetric low-pass FIR filter
with enough taps and bits of precision would work.  Of course there
would be a significant filter delay (roughly the length of the entire
symphony) before you would see the first output samples.


-- 
rhn A.T nicholson d.O.t C-o-M

cs_post...@hotmail.com wrote:
> > Ron N. wrote:
> > > For this counterexample to work, the response of the lowpass filter
> > > for each sample would have to be over an hours worth of samples wide
...
> to which Jerry Avins replied:
> > What if it's a request show and the second half-hour's music isn't known
> > until after the sampling stops? Suppose even that the program is known
> > in advance. Do you suggest that it might be possible to reconstruct the
> > last movement of Beethoven s 9th Symphony from a gross oversampling of
> > the first three?
>
> Yes, provided you pass the samples through the anti-causal low pass
> filter that Ron postulated.

It wouldn't have to be anti-causal.  A symmetric low-pass FIR filter
with enough taps and bits of precision would work.  Of course there
would be a significant filter delay (roughly the length of the entire
symphony) before you would see the first output samples.


-- 
rhn A.T nicholson d.O.t C-o-M

cs_post...@hotmail.com wrote:
> > Ron N. wrote:
> > > For this counterexample to work, the response of the lowpass filter
> > > for each sample would have to be over an hours worth of samples wide
...
> to which Jerry Avins replied:
> > What if it's a request show and the second half-hour's music isn't known
> > until after the sampling stops? Suppose even that the program is known
> > in advance. Do you suggest that it might be possible to reconstruct the
> > last movement of Beethoven s 9th Symphony from a gross oversampling of
> > the first three?
>
> Yes, provided you pass the samples through the anti-causal low pass
> filter that Ron postulated.

It wouldn't have to be anti-causal.  A symmetric low-pass FIR filter
with enough taps and bits of precision would work.  Of course there
would be a significant filter delay (roughly the length of the entire
symphony) before you would see the first output samples.


-- 
rhn A.T nicholson d.O.t C-o-M

Jerry Avins wrote:
> Carlos Moreno wrote:
> > Jerry Avins wrote:
> >
> >>>  [...]
> >>> The reasoning can be extended to any number N, no matter how
> >>> large.
> >>>
> >>> I know this is not rigurous -- in particular, this shows that
> >>> the trick works for N samples taken at positions other than
> >>> the corresponding positions, no matter how large;  but this
> >>> proves nothing about an "infinity" of samples taken non-
> >>> uniformly...  Still, the result does suggest that you still
> >>> need the amount of samples that totals the same amount of
> >>> samples required in uniform sampling  (suggesting that your
> >>> Nyquist condition is given by the average sampling rate).
> >>
> >>
> >> It doesn't. There's a limit to how non-uniform the sampling can be
> >> allowed to be. The example given above, of an hour's worth of music
> >> sampled for half an hour at twice the minimum rate for the bandwidth,
> >> is an adequate counterexample
> >
> >
> > No it's not.  Not only is it not an *adequate* counterexample;
> > it's not even a counterexample.
> >
> > The above reasoning has nothing to do with practical applicability
> > of the issue.  The above reasoning is purely mathematical -- or
> > I should rather say, it works purely at the mathematical level.
> >
> > If the music you're talking about is truly *band-limited*, then
> > it spans from time -infinity to +infinity.  So, assuming that
> > the signal is *strictly bandlimited* between DC and 20kHz, then
> > yes, taking one hour worth of samples (at least 1 + 40000*3600
> > samples) in an interval of 1 microsecond right before the hour
> > of music began *is* enough to fully, completely, and perfectly
> > (i.e., 100% accurately) reconstruct the whole hour of music;
> > provided that the remaining infinity of samples before and
> > after the sampleless hour is there, and provided that the
> > 1+40000*3600 samples are distinct, and at times different from
> > all the remaining uniform samples).
> >
> > Again:  *mathematically* speaking, the signal is fully recoverable
> > (analytically;  or numerically, if we could count on "infinite
> > precision" representation of real numbers).
>
> Wonderful! If I've composed two movements of a symphony, how many more
> can I deduce using the principles of DSP without actually composing any
> more music?

None, since you would need to compose more movements to properly
bandlimit the samples of the first two movements to the precision
required.

-- 
rhn A.T nicholson d.O.t C-o-M.

Jerry Avins wrote:

> In the real world, we sample time-limited signals and reconstruct them 
> as if they were bandlimited. Don't knock it: not only does it work, 
> nothing else is possible,

Absolutely -- there is no disagreement there.

But notice how we're talking about different things:  you're
talking about the *approximation* that we do in practical
applications (because let's face it:  we do not have any other
choice!).  My reasoning applies at the mathematical level, since
it is based on the assumption of a *truly bandlimited* signal,
something that does not exist in the real world (at least in
practical terms).

It does, however, have a nice applicability (well, not really
that nice) if we are talking about samples taken without huge
gaps (gaps as in huge periods of time without samples).

Carlos
--

Jerry Avins wrote:

>>> It's also a world where signals exist for all time. I doesn't matter 
>>> how precisely one can sample and how often, nothing can be known 
>>> about a speech yet to be given
>>
>> If that is the case, then the speech signal is not bandlimited -- and
>> if that is the case, then you're talking about an entirely different
>> thing than I was talking about.
> 
> I'm talking about precisely what you are. A signal that is truly 
> bandlimited isn't time limited, and vice versa. In the real world, 
> signals with finite duration can bandlimited well enough so that we can 
> deal with them. 

Absolutely.  And the fact that we *want* to sample them uniformly
because there are endless arguments in favor of it (i.e., there is
an endless list of advantages from both the practical and theoretical
point of view) is an entirely different thing.

When I read the subject of the thread, and the question asked by
the OP, it became more or less clear that we were dealing with the
theoretical/mathematical aspect as much as with the practical one.

In the practical side, there's no question about it -- non-uniform
sampling is virtually an "absolute no-no".

But on the theoretical side, I find it extremely interesting (and
remarkable!) the results and conclusions that we can reach, even
if they seem unintuitive when contrasted with the practical side.

(no, this is not a case of "in theory, there is no difference
between theory and practice, but in practice, there is" -- it's
simply a case of "this particular result from the theory does not
have a practical situation where it is really applicable")

> But when one becomes pedantic about what is 
> theoretically possible, on must be likewise aware of what is 
> theoretically impossible.

Well, it's not really "pedantic" -- I see it more like a matter
of keeping in mind when some theoretical result has a direct
applicability in the practical world.  After all, going back to
the roots, Calculus itself could be accused of "pedantic", in
that the real world is not really how Calculus models it (even
though in the case of Calculus, the *results* are nicely
correlated with the physical world, unlike this issue about
the non-uniform sampling taken to the extreme)

>> But BTW, your argument does not really contradict my reasoning -- I did
>> not say (nor the conclusion I presented implies) that you can determine
>> the hour of speech before it was given.  In fact, not even right after
>> it is given.  To *fully* determine/reconstruct the continuous-time
>> speech signal you have to wait until "t = infinity" to be able to
>> reconstruct it...  (t = infinity is obviously a figure of speech, to
>> simplify the issue that the signal is given by an infinite sum)
> 
> According to the argument you gave, samples from near the end of a 
> program can be moved to near the beginning, one at a time, without 
> compromising the reconstructed signal. How long you must have to wait 
> before the decoding is finished doesn't bear on the claim that you can 
> reconstruct what was not sampled. Do I not understand what you claimed?

I'm not 100% sure...  Maybe you do and you're assuming that I'm
assigning some practical value to it;  but perhaps you misinterpreted
what I said.

In the above paragraph, you talk about "samples from near the end of
a program can be moved to near the beginning" -- if by that you mean
the *sampling position*  (as in, the value of t at which you take a
sample), then we seem to be in sync.

Let's say that we have a *perfectly bandlimited* signal between DC
and 0.499999999Hz, so that a sampling period of 1 second allows us
to reconstruct the signal.

If you have an infinite set of samples of that signal, taken at
exactly .... -3s, -2s, -1s, 0s, 1s, 2s, 3s, ..... , then you can,
mathematically speaking, reconstruct the signal at all times, with
100% accuracy.

My claim (or rather, an example that illustrates my claim) is that
if you have all those samples and instead of taking a sample at
t = 0, you take one additional sample at t = -75.45627, you still
have enough information to reconstruct *exactly* the signal at all
values of t  (again, mathematically speaking).

Why?

If you had all the values of x(t) at t = k seconds (with k integer),
then you could obtain x(-75.45627), right?  (with the reconstruction
formula, using the infinite sum with sinc terms).  The relationship
is linear;  in particular, the relationship between x(-75.45627) and
x(0) is linear:

x(-75.45627) = sinc(-75.45627) x(0) + B

Where B is the rest of the infinite sum (all the terms except for
k = 0)

So, that means that having x(-75.45627), you can obtain x(0)  (since
we know B).  But then, as soon as we have x(0), now the "standard"
sampling theorem tells us that the signal can be reconstructed
with 100% accuracy.

What if instead of sampling x at t = 0 and at t = 1, you take two
additional samples, one at t = -75.45627, and another one at
t = -75.512348 ??).  These two samples, x(-75.45627) and
x(-75.512348) are related to x(0) and x(1) by a linear relationship;
each one provides one equation;  thus, if we want to obtain x(0)
and x(1), we just solve a system of linear equations -- two equations
for the two unknowns, x(0) and x(1).

So, the argument can be extended -- if you do not take any sample
of the signal between t = 0 and t = 1000, and instead you take
samples at t = -0.9, -0.8999, -0.8998, .... and so on, every
tenth of a millisecond, until t = -0.8001, you end up with a
*solvable* system of 1000 linear equations for the 1000 unknowns,
x(0) to x(999).  You *can* solve that system, obtain x(0) to x(999),
and now you can recover the signal for all values of t.

Where do you find a flaw in the above reasoning?

Notice that I would never say as little as half a word in defense
of the practical applicability of the above!!  For one, the
example is taken to a ridiculous extreme of sensitivity to
numerical accuracy -- the samples taken a tenth of a millisecond
away of each other would lead to a matrix that is sooooooo close
to being singular that I guarantee that it would be next to
impossible to solve the system numerically with any *actual*
computer that we may have.

But that still does not defeat the fact that *mathematically*
speaking, those samples provide sufficient information to
determine the values of the signal at every value of t.

Again:  provided that the signal is *truly bandlimited*, which
as we already agreed, implies that it is not time-limited (the
signal goes from -infinity to +infinity).

Carlos
--

Jerry Avins wrote:
> In the real world, we sample time-limited signals and reconstruct them
> as if they were bandlimited. Don't knock it: not only does it work,
> nothing else is possible,

I wonder if, with a low enough stop band in the low pass filter, the
difference between real-world samples and samples bandlimited with
infinite support is within the rounding error of typical sampler
quantization?  So maybe it "works" because it's close enough for the
bits of result we usually need (but not nearly enough to reconstruct
the second half of a symphony. :)



IMHO. YMMV.
-- 
rhn A.T nicholson d.O.t C-o-M