question about non-uniform sampling?

lucy wrote:
> Hi all,
>
> 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?
>
> Thanks a lot!
>
> -L

   This was a popular problem in the 1960's.  A fairly thorough
presentation is made in the book "Discrete Time Systems - An
Introduction to the Theory" by Herbert Freeman, Wiley and Sons 1965;
section 4.8 - Nonuniform Sampling.

The main result for this issue is :

" a function f(t), bandlimited to -B/2<=w<=B/2 (where B=2pi/T) can be
uniquely reconstructed from a set of samples which are nonuniformly
spaced but satisfy the condition that there be precisely N distinct
samples to every interval of length NT, where N is some finite integer
."

  The actual reconstruction is shown in the book and is straight
forward; but really ugly.

  This may be a more severe condition that it seems at first;
especially the "precisely N distinct ..." .  There are probably better
results since this book was published forty years ago.

MzF

If you a theoretical discuss, then read the following article:

H.J. Landau, "Sampling, Data Transmission, and the Nyquist Rate",
Proceedings of the IEEE, Vol 55, No 10, October 1967.

I quote from the abstract (note in the brackets is my comments):

"...In this paper we draw a distinction between reconstructioning a
signal from its samples, and doing so in a stable way [small errors in
sampling don't led to large reconstruction errors], we argue that only
stable sampling is meaningful in practice. We then prove that:
1) stable sampling cannot be performed at a rate lower than the
Nyquist,
2) data cannot be transmitted as samples as a rate higher that the
Nyquist,
regardless of the location of sampling instants, the nature of the set
of frequencies which the signals occupy, or the method of construction.
These conclusions apply not merely to finite-energy, but also to
bounded signals."

Scott

lucy wrote:
> Hi all,
> 
> 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?

There's an easy way to look at this.

Imagine that you have a sampled signal -- standard, uniform
sampling at a rate within Nyquist.

That means that the value of the signal at *every* point is
fully and exactly determined by all the samples (the infinity
of samples), by a linear relationship:

         +oo
x(t) = sum      { a_k x(kTs) }
         k = -oo

Where the value of each a_k depends on the value of t (your
sinc function, etc. etc.)

So, if you can find x(t) as a linear function of all the x_k,
then you could solve for one of the x_k's as a function of all
the other x_k's and x(t):

x(nTs) = ( x(t) - sum   {a_k x(kTs)} ) / a_n
                   k != i

So, that means that you can take *one* sample at *any* position
different from its "corresponding" position if you were always
sampling at uniform spacing, and you can then determine the
value of the signal at the point of the missing sample (one of
the points of uniform sampling).  But if you can determine the
missing sample, then you now have all the samples of a uniformly-
sampled signal, and hence you can fully and exactly reconstruct
the analog signal.

Now, if you take two samples (instead of one) at the non-
corresponding positions, the above reasoning can be used to
show that now you have a set of two linear equations with two
unknowns.  Provided that the two signals are sampled at
different points, and different from any other sample in the
uniform-sampling points, the equations are independent, and
the system has a unique solution.

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).

HTH,

Carlos
--

Carlos Moreno wrote:
> lucy wrote:
> 
>> Hi all,
>>
>> 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?
> 
> 
> There's an easy way to look at this.
> 
> Imagine that you have a sampled signal -- standard, uniform
> sampling at a rate within Nyquist.
> 
> That means that the value of the signal at *every* point is
> fully and exactly determined by all the samples (the infinity
> of samples), by a linear relationship:
> 
>         +oo
> x(t) = sum      { a_k x(kTs) }
>         k = -oo
> 
> Where the value of each a_k depends on the value of t (your
> sinc function, etc. etc.)
> 
> So, if you can find x(t) as a linear function of all the x_k,
> then you could solve for one of the x_k's as a function of all
> the other x_k's and x(t):
> 
> x(nTs) = ( x(t) - sum   {a_k x(kTs)} ) / a_n
>                   k != i
> 
> So, that means that you can take *one* sample at *any* position
> different from its "corresponding" position if you were always
> sampling at uniform spacing, and you can then determine the
> value of the signal at the point of the missing sample (one of
> the points of uniform sampling).  But if you can determine the
> missing sample, then you now have all the samples of a uniformly-
> sampled signal, and hence you can fully and exactly reconstruct
> the analog signal.
> 
> Now, if you take two samples (instead of one) at the non-
> corresponding positions, the above reasoning can be used to
> show that now you have a set of two linear equations with two
> unknowns.  Provided that the two signals are sampled at
> different points, and different from any other sample in the
> uniform-sampling points, the equations are independent, and
> the system has a unique solution.
> 
> 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).
> 
> HTH,

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 to what you claim is a general case.

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

Carlos Moreno wrote:
> lucy wrote:
> 
>> Hi all,
>>
>> 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?
> 
> 
> There's an easy way to look at this.
> 
> Imagine that you have a sampled signal -- standard, uniform
> sampling at a rate within Nyquist.
> 
> That means that the value of the signal at *every* point is
> fully and exactly determined by all the samples (the infinity
> of samples), by a linear relationship:
> 
>         +oo
> x(t) = sum      { a_k x(kTs) }
>         k = -oo
> 
> Where the value of each a_k depends on the value of t (your
> sinc function, etc. etc.)
> 
> So, if you can find x(t) as a linear function of all the x_k,
> then you could solve for one of the x_k's as a function of all
> the other x_k's and x(t):
> 
> x(nTs) = ( x(t) - sum   {a_k x(kTs)} ) / a_n
>                   k != i
> 
> So, that means that you can take *one* sample at *any* position
> different from its "corresponding" position if you were always
> sampling at uniform spacing, and you can then determine the
> value of the signal at the point of the missing sample (one of
> the points of uniform sampling).  But if you can determine the
> missing sample, then you now have all the samples of a uniformly-
> sampled signal, and hence you can fully and exactly reconstruct
> the analog signal.
> 
> Now, if you take two samples (instead of one) at the non-
> corresponding positions, the above reasoning can be used to
> show that now you have a set of two linear equations with two
> unknowns.  Provided that the two signals are sampled at
> different points, and different from any other sample in the
> uniform-sampling points, the equations are independent, and
> the system has a unique solution.
> 
> 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).
> 
> HTH,

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 to what you claim is a general case.

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

Carlos Moreno wrote:
> lucy wrote:
> 
>> Hi all,
>>
>> 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?
> 
> 
> There's an easy way to look at this.
> 
> Imagine that you have a sampled signal -- standard, uniform
> sampling at a rate within Nyquist.
> 
> That means that the value of the signal at *every* point is
> fully and exactly determined by all the samples (the infinity
> of samples), by a linear relationship:
> 
>         +oo
> x(t) = sum      { a_k x(kTs) }
>         k = -oo
> 
> Where the value of each a_k depends on the value of t (your
> sinc function, etc. etc.)
> 
> So, if you can find x(t) as a linear function of all the x_k,
> then you could solve for one of the x_k's as a function of all
> the other x_k's and x(t):
> 
> x(nTs) = ( x(t) - sum   {a_k x(kTs)} ) / a_n
>                   k != i
> 
> So, that means that you can take *one* sample at *any* position
> different from its "corresponding" position if you were always
> sampling at uniform spacing, and you can then determine the
> value of the signal at the point of the missing sample (one of
> the points of uniform sampling).  But if you can determine the
> missing sample, then you now have all the samples of a uniformly-
> sampled signal, and hence you can fully and exactly reconstruct
> the analog signal.
> 
> Now, if you take two samples (instead of one) at the non-
> corresponding positions, the above reasoning can be used to
> show that now you have a set of two linear equations with two
> unknowns.  Provided that the two signals are sampled at
> different points, and different from any other sample in the
> uniform-sampling points, the equations are independent, and
> the system has a unique solution.
> 
> 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).
> 
> HTH,

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 to what you claim is a general case.

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

Carlos Moreno wrote:
> lucy wrote:
> 
>> Hi all,
>>
>> 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?
> 
> 
> There's an easy way to look at this.
> 
> Imagine that you have a sampled signal -- standard, uniform
> sampling at a rate within Nyquist.
> 
> That means that the value of the signal at *every* point is
> fully and exactly determined by all the samples (the infinity
> of samples), by a linear relationship:
> 
>         +oo
> x(t) = sum      { a_k x(kTs) }
>         k = -oo
> 
> Where the value of each a_k depends on the value of t (your
> sinc function, etc. etc.)
> 
> So, if you can find x(t) as a linear function of all the x_k,
> then you could solve for one of the x_k's as a function of all
> the other x_k's and x(t):
> 
> x(nTs) = ( x(t) - sum   {a_k x(kTs)} ) / a_n
>                   k != i
> 
> So, that means that you can take *one* sample at *any* position
> different from its "corresponding" position if you were always
> sampling at uniform spacing, and you can then determine the
> value of the signal at the point of the missing sample (one of
> the points of uniform sampling).  But if you can determine the
> missing sample, then you now have all the samples of a uniformly-
> sampled signal, and hence you can fully and exactly reconstruct
> the analog signal.
> 
> Now, if you take two samples (instead of one) at the non-
> corresponding positions, the above reasoning can be used to
> show that now you have a set of two linear equations with two
> unknowns.  Provided that the two signals are sampled at
> different points, and different from any other sample in the
> uniform-sampling points, the equations are independent, and
> the system has a unique solution.
> 
> 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).
> 
> HTH,

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 to what you claim is a general case.

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

Carlos Moreno wrote:
> lucy wrote:
> 
>> Hi all,
>>
>> 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?
> 
> 
> There's an easy way to look at this.
> 
> Imagine that you have a sampled signal -- standard, uniform
> sampling at a rate within Nyquist.
> 
> That means that the value of the signal at *every* point is
> fully and exactly determined by all the samples (the infinity
> of samples), by a linear relationship:
> 
>         +oo
> x(t) = sum      { a_k x(kTs) }
>         k = -oo
> 
> Where the value of each a_k depends on the value of t (your
> sinc function, etc. etc.)
> 
> So, if you can find x(t) as a linear function of all the x_k,
> then you could solve for one of the x_k's as a function of all
> the other x_k's and x(t):
> 
> x(nTs) = ( x(t) - sum   {a_k x(kTs)} ) / a_n
>                   k != i
> 
> So, that means that you can take *one* sample at *any* position
> different from its "corresponding" position if you were always
> sampling at uniform spacing, and you can then determine the
> value of the signal at the point of the missing sample (one of
> the points of uniform sampling).  But if you can determine the
> missing sample, then you now have all the samples of a uniformly-
> sampled signal, and hence you can fully and exactly reconstruct
> the analog signal.
> 
> Now, if you take two samples (instead of one) at the non-
> corresponding positions, the above reasoning can be used to
> show that now you have a set of two linear equations with two
> unknowns.  Provided that the two signals are sampled at
> different points, and different from any other sample in the
> uniform-sampling points, the equations are independent, and
> the system has a unique solution.
> 
> 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).
> 
> HTH,

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 to what you claim is a general case.

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

Jerry Avins wrote:
> Carlos Moreno wrote:
> 
>> lucy wrote:
>>
>>> Hi all,
>>>
>>> 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?
>>
>>
>>
>> There's an easy way to look at this.
>>
>> Imagine that you have a sampled signal -- standard, uniform
>> sampling at a rate within Nyquist.
>>
>> That means that the value of the signal at *every* point is
>> fully and exactly determined by all the samples (the infinity
>> of samples), by a linear relationship:
>>
>>         +oo
>> x(t) = sum      { a_k x(kTs) }
>>         k = -oo
>>
>> Where the value of each a_k depends on the value of t (your
>> sinc function, etc. etc.)
>>
>> So, if you can find x(t) as a linear function of all the x_k,
>> then you could solve for one of the x_k's as a function of all
>> the other x_k's and x(t):
>>
>> x(nTs) = ( x(t) - sum   {a_k x(kTs)} ) / a_n
>>                   k != i
>>
>> So, that means that you can take *one* sample at *any* position
>> different from its "corresponding" position if you were always
>> sampling at uniform spacing, and you can then determine the
>> value of the signal at the point of the missing sample (one of
>> the points of uniform sampling).  But if you can determine the
>> missing sample, then you now have all the samples of a uniformly-
>> sampled signal, and hence you can fully and exactly reconstruct
>> the analog signal.
>>
>> Now, if you take two samples (instead of one) at the non-
>> corresponding positions, the above reasoning can be used to
>> show that now you have a set of two linear equations with two
>> unknowns.  Provided that the two signals are sampled at
>> different points, and different from any other sample in the
>> uniform-sampling points, the equations are independent, and
>> the system has a unique solution.
>>
>> 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).
>>
>> HTH,
> 
> 
> 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 to what you claim is a general case.
> 
> Jerry

The practicality of non-uniform sample isn't a whole lot different 
whether we are talking about minor non-uniformity or some extreme. As 
soon as sampling is even a little non-uniform it is highly sensitive to 
sampling error and converter noise. As it becomes more non-uniform it 
quickly becomes totally impractical to make sense of the kind of samples 
you can get in the real world. There is nothing wrong with any extreme 
of non-uniformity in a purely mathematical sense. That is in a world 
with infinite sampling precision and no noise due to the converter itself.

Regards,
Steve

Steve Underwood wrote:

   ...

> The practicality of non-uniform sample isn't a whole lot different 
> whether we are talking about minor non-uniformity or some extreme. As 
> soon as sampling is even a little non-uniform it is highly sensitive to 
> sampling error and converter noise. As it becomes more non-uniform it 
> quickly becomes totally impractical to make sense of the kind of samples 
> you can get in the real world. There is nothing wrong with any extreme 
> of non-uniformity in a purely mathematical sense. That is in a world 
> with infinite sampling precision and no noise due to the converter itself.

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, even if the mathematics of nonuniform and highly 
clumped sampling shows that it can.

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