Beating Nyquist?

On 25 Jul, 18:30, Steve Underwood <ste...@dis.org> wrote:
> Rune Allnor wrote:
> > On 25 Jul, 15:57, Steve Underwood <ste...@dis.org> wrote:
> >> Rune Allnor wrote:
> >>> I don't like "random" algorithms which work "on average."
> >>> Maybe the claim that random sampling works "on average"
> >>> can be formally justified; I don't have the competence
> >>> to comment on such a *formal* claim either way.
> >> Aren't algorithms that work statistically the very essence of signal
> >> processing? :-\
>
> > No. They play a large part -- adaptive DSP and model-based
> > DSP based on parameter estimation, come to mind -- but all
> > suffer from the same weakness: They only work to whatever
> > extent the statistical model fit reality. Or, alternatively,
> > to the extent the signal fits the model.
>
> > As long as there is a certain degree of match between signal
> > and statistsical model, OK, the algorithms work. The problems
> > occur when the mismatch becomes large and go undetected.
> > Are these instances acceptable "on average" or does the
> > application require *guaranteed* worst-case behaviour?
>
> Pretty much anything in comms is statistical.

You know a few things:

- Transmitter frequency
- Transmitter bandwidth
- Modulation scheme
- Codebook

Given these deterministic basics, the statistics amounts
to handle additive noise and determining exactly which
of these deterministic codes appear when in the signal.

> Pretty much anything in sensing is statistical.

You know a few things:

- Transmitter frequency
- Transmitter bandwidth
- Modulation scheme
- Codebook

Given these deterministic basics, the statistics amounts
to handle additive noise and determining exactly when
these deterministic codes appear in the signal.

> I thought you'd worked in acoustic sensing. That's a very statistical area.

Correct. I have learned the hard way to be as conservative as
possible when working outside purely academic contexts.
Data sampling is a bit too fundamental to mess up; the vessels
I work on cost on the order of $100000 per day to keep in the
field. If you have access to one of those, you want to play
it safe and get some guaranteed performance. Anything else
would be gambling, both with the client's $$ as well as
your own reputation. And professional future.

Of course, one you have sampled the data, you can start
playing with statistics. As long as you have a backup
which provides some guaranteed worst-case performance
which can answer certain very specific questions.

Rune

On Jul 25, 10:19 am, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 25 Jul, 18:30, Steve Underwood <ste...@dis.org> wrote:

> > >> Aren't algorithms that work statistically the very essence of signal
> > >> processing? :-\
> > Pretty much anything in comms is statistical.

Pretty much anything dealing with the real world is
statistical (QM and thermodynamics, etc. as well as
failure rates, humans, and "unexpected" accidents.)

Deterministic engineering usually just renames all
the statistically outlying events as outside the
assumptions for the system.

> You know a few things:
>
> - Transmitter frequency

Assuming a solder joint near the xtal or some other
component didn't go bad... or the janitor hit the
wrong button when turning out the lights, etc. etc.
In a few comms fields, human interface design as well
as failure or even disaster mitigation are part of
the design process.


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

On Jul 25, 2:24 am, Andor <andor.bari...@gmail.com> wrote:
> Friends,
>
> just now I stumbled upon this webpage:
>
> http://www.edi.lv/dasp-web/
>
> Specifically, in this chapter
>
> http://www.edi.lv/dasp-web/sec-5.htm
>
> they state that they can sample a 1.2GHz signal using a pseudo-random
> sampling instants with an average rate of 80MHz (in the last line of
> section "5.2 Aliasing, how to avoid it").

What this paper seems to show is that traditional
image aliases that would go undetected by strictly
periodic sampling would be detected by some sampling
jitter.  What they do not say is whether some other
other type of alias waveform (fractal maybe?) could
still be aliased in their reconstruction.

Bandlimiting allows a clean definition of the types
of waveform which would alias in a periodic sampling
scheme.  My guess is that random sampling merely
makes it harder to define the types of waveforms
which would cause aliasing, making them much harder
or impossible to remove.  But if you rename these
aliases "noise", then you might be able, in return,
to detect the more cleanly defined "bands" of
traditionally aliased spectrum (e.g. an interfering
carrier, etc.).


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

Fred Marshall wrote:
(snip, and previously snipped discussion about Nyquist, aliasing,
and non-uniform sampling)

> Without studying it too hard it looks to me like the proposed approach tends 
> to spread the spectrum of the aliases - generating what looks more like 
> noise.  Thus creating a tradeoff between having aliases and noise.  Seems 
> like it would depends on lot on the nature of the signal for it to work. 
> Periodic waveforms might work fine while more random waveforms might not - 
> because how do you differentiate between "signal" and "noise" in that latter 
> case?

It seems to be popular now to dither the clocks on processors to
"reduce" RFI.  Presumably this just spreads out the RFI so
that instead of a sharp peak at some frequencies it is
smaller peaks at more frequencies.

> I'm not endorsing the claim, just pondering it.

> Knowing the sample times precisely only positions the samples for 
> reconstruction.  Pure sinc reconstruction (or lowpass filtering of 
> precisely-placed samples) works fine for the fundamental components.  But, 
> for higher frequency components that would alias, the dithering might spread 
> their spectrum, would't it?

Isn't the traditional Nyquist limit only good for an infinitely
long signal?

The one I used to consider was N sample points over a time T, with the 
signal zero at t=0 and t=T.  Considering a basis of sin(wt) and
cos(wt), and with the signal zero at t=0, only sin(wt) terms are
allowed.  Zero at t=T allows only discrete frequencies, and
with a band-limited signal, the appropriate Nyquist limit is
found.   In that case, the N samples result in an N equations
with N unknowns at reconstruction, which works as long as the
matrix is not singular.

> Here's another way of looking at it - a thought experiment:
> Assume a really high sample rate that is equivalent to the temporal 
> resolution of the samples to be taken "randomly".  Surely there is a time 
> grid that must underlie the method - for example, on which to place the 
> reconstructing waveforms (e.g. sincs).
> This creates a sample rate that is (by definition) "high enough" for the 
> actual bandwidth and Nyquist.

With non-uniform sampling the reconstruction isn't a sinc,
but if the sample points are rational then a finer grid will exist.
It they are irrational then no such grid exists, but non-uniform
sampling still works the same way.

> Sample at this rate.  You know what the spectrum will look like 
> if you know the signal being sampled.

For a quantized signal you get quantization noise in the
reconstruction.  Uniform sampling minimizes the peaks in
the quantization noise.

> Then, decimate but randomly.  That is, decimate (but not regularly) so that 
> the average sample rate is what you wanted in the first place.  Note that 
> this is a nonlinear operation so familiar methods of analysis don't work.

> Now, use a test signal that is above the "new" fs/2.
> It seems to me that the randomized sample points will modulate the heck out 
> of a higher-frequency sinusoid - turning its samples into what looks like 
> random noise - because of the rather drastic phase hops between samples.

> Thus, no "alias" tonals in the result - but, more noise.

It looks that way to me, too.

> If you switch the input to a test signal that is below the "new" fs/2 then 
> there will be no modulation (spectral spreading) because of the careful 
> temporal registration of the samples and the reconstructing sincs.  Well, 
> that's an arm-waving description and I'm sure others can do a better, more 
> thoughtful, job of explaining why this might be.

Not counting quantization noise.
(snip)

> OK - I thought about it some more...
> The "nonlinear" step above can be replaced with a linear step.
> Create the desired sample points in time.  By definition they align on the 
> fine temporal grid.  Note that the gross view of these samples looks like 
> they are regularly spaced.  But they aren't of course - on purpose.

Unless the sample points are irrational.

> Because the temporal location will be dithered at decimation, using a new 
> set of sample points, there is a spectrum of this lower-frequency unit 
> sample train that's not the typical picket fence repeating at fs.  Rather, 
> there's a broader clump at fs - the width determined by how much temporal 
> deviation is built in between the samples.

Yes, I agree.  The same way that clock dithering spreads out
the RFI of clock frequencies and their harmonics.

-- glen

On 25 Jul, 20:35, "Ron N." <rhnlo...@yahoo.com> wrote:
> On Jul 25, 10:19 am, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > On 25 Jul, 18:30, Steve Underwood <ste...@dis.org> wrote:
> > > >> Aren't algorithms that work statistically the very essence of signal
> > > >> processing? :-\
> > > Pretty much anything in comms is statistical.
>
> Pretty much anything dealing with the real world is
> statistical (QM and thermodynamics, etc. as well as
> failure rates, humans, and "unexpected" accidents.)

That's a fatalist's attitude. "It was by sheer bad luck
that car ran off the road and hit the tree!" Have a look
at the F1 accident record over the past 50 years, and
see how the fatality rate is correlated with the track
safety zones and car designs. The occurence of cars
running off track might be random, but the concequences
of it happening is all but mitigated. That's due to
deterministic factors of track design.

> Deterministic engineering usually just renames all
> the statistically outlying events as outside the
> assumptions for the system.

There are assumptions and there is knowledge.

If you are happy with designing a speech processing
system under the *assumption* that the human voice
has its main spectral content in the range
1.3804 MHz - 22.78 GHz, then by all means, go ahead
and design and market your system.

Just be prepared to answer to whoever funded your
project, after your project has gone bankrupt.

> > You know a few things:
>
> > - Transmitter frequency
>
> Assuming a solder joint near the xtal or some other
> component didn't go bad... or the janitor hit the
> wrong button when turning out the lights, etc. etc.
> In a few comms fields, human interface design as well
> as failure or even disaster mitigation are part of
> the design process.

Exactly. "Design" is all about handling certain key
aspects of the system in a very deterministic way, as
opposed to leaving them to chance. In my book -- if
not in yours -- the sampling period is one of those
factors concerning DSP which should *not* be left
to chance.

A high risk -- be it national security or mere $$ -- tends
to bring most competent project managers to their senses.

Rune

On 25 Jul, 23:47, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:

> Isn't the traditional Nyquist limit only good for an infinitely
> long signal?

No. Sample a sinusoidal for arbitrary length of time (N > 1)
and you will find aliasing to be an issue.

> The one I used to consider was N sample points over a time T, with the
> signal zero at t=0 and t=T.  Considering a basis of sin(wt) and
> cos(wt), and with the signal zero at t=0, only sin(wt) terms are
> allowed. Zero at t=T allows only discrete frequencies, and
> with a band-limited signal, the appropriate Nyquist limit is
> found.   In that case, the N samples result in an N equations
> with N unknowns at reconstruction, which works as long as the
> matrix is not singular.

Nope. The problem is that the identity

sin(2*pi*f*n) = sin(2*pi*f*n + 2*pi*p),  p integer

always holds; you can not find a unique value for p.

Rune

On Jul 25, 1:59 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 25 Jul, 20:35, "Ron N." <rhnlo...@yahoo.com> wrote:
>
> > On Jul 25, 10:19 am, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > > On 25 Jul, 18:30, Steve Underwood <ste...@dis.org> wrote:
> > > > >> Aren't algorithms that work statistically the very essence of signal
> > > > >> processing? :-\
> > > > Pretty much anything in comms is statistical.
>
> > Pretty much anything dealing with the real world is
> > statistical (QM and thermodynamics, etc. as well as
> > failure rates, humans, and "unexpected" accidents.)
>
> That's a fatalist's attitude. "It was by sheer bad luck
> that car ran off the road and hit the tree!" Have a look
> at the F1 accident record over the past 50 years, and
> see how the fatality rate is correlated with the track
> safety zones and car designs. The occurence of cars
> running off track might be random, but the concequences
> of it happening is all but mitigated. That's due to
> deterministic factors of track design.

I would hesitate to call it deterministic unless you
can predict which driver on which day at which turn
will run off the track.  If not, you are merely dealing
with statistical safety issues, (e.g. doing this to
that turn will reduce the expected accident rate from
x per year to y per year, on average and rarely
exactly.)

...

> > > You know a few things:
>
> > > - Transmitter frequency
>
> > Assuming a solder joint near the xtal or some other
> > component didn't go bad... or the janitor hit the
> > wrong button when turning out the lights, etc. etc.
> > In a few comms fields, human interface design as well
> > as failure or even disaster mitigation are part of
> > the design process.
>
> Exactly. "Design" is all about handling certain key
> aspects of the system in a very deterministic way, as
> opposed to leaving them to chance.

I think we may just be calling the same (good)
engineering process by two different names.

> In my book -- if
> not in yours -- the sampling period is one of those
> factors concerning DSP which should *not* be left
> to chance.

If you can.  An if the solution to the more tractable
resulting situation is the desired one.


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

Rune Allnor wrote:

> On 25 Jul, 23:47, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:

>>Isn't the traditional Nyquist limit only good for an infinitely
>>long signal?

> No. Sample a sinusoidal for arbitrary length of time (N > 1)
> and you will find aliasing to be an issue.

I meant it the other way around.  That for finite length
(and non-periodic) signals, you can't exactly reproduce them
with a finite number of samples.

>>The one I used to consider was N sample points over a time T, with the
>>signal zero at t=0 and t=T.  Considering a basis of sin(wt) and
>>cos(wt), and with the signal zero at t=0, only sin(wt) terms are
>>allowed. Zero at t=T allows only discrete frequencies, and
>>with a band-limited signal, the appropriate Nyquist limit is
>>found.   In that case, the N samples result in an N equations
>>with N unknowns at reconstruction, which works as long as the
>>matrix is not singular.

> Nope. The problem is that the identity

> sin(2*pi*f*n) = sin(2*pi*f*n + 2*pi*p),  p integer

> always holds; you can not find a unique value for p.

Again the other way around.  The signal is known to be band
limited which selects the appropriate p.  The reconstruction
has to be done with the selected p.

-- glen

On 25 Jul, 23:38, "Ron N." <rhnlo...@yahoo.com> wrote:
> On Jul 25, 1:59 pm, Rune Allnor <all...@tele.ntnu.no> wrote:

> > > Pretty much anything dealing with the real world is
> > > statistical (QM and thermodynamics, etc. as well as
> > > failure rates, humans, and "unexpected" accidents.)
>
> > That's a fatalist's attitude. "It was by sheer bad luck
> > that car ran off the road and hit the tree!" Have a look
> > at the F1 accident record over the past 50 years, and
> > see how the fatality rate is correlated with the track
> > safety zones and car designs. The occurence of cars
> > running off track might be random, but the concequences
> > of it happening is all but mitigated. That's due to
> > deterministic factors of track design.
>
> I would hesitate to call it deterministic unless you
> can predict which driver on which day at which turn
> will run off the track.

That particular aspect is random. The chain of events
when it happens, is more or less deterministic: The gravel
pits and grass slow the sliding car down, the tire stacks
by the wall and crumble zones built into the car bring
it to a final halt in a way that is survivable to the
driver.

The goal in DSP, as far as I can see, is to use deterministic
models whereever possible, and resort to statistics only
reluctantly.

I analyzed real-life data for my PhD thesis using statistical
fits to deterministic models, Prony's method to be precise.
Prony's method is a way to determine the parameters in a
D-component sum-of-sines data model,

        D
x[n] = sum A_d sin(w_d n)                      [1]
       d=1

(note that the model contains no noise terms)

The first account of Prony's method I read was

Kay & Marple: "Spectrum Analysis - A modern perspective"
      Proc IEEE October 1981.

I had just taken a DSP course where AR methods, whitening
filters, innovation processes and all that had been covered.
The basic idea behind Prony's method was easily covered,
assuming that the model contained N sinusoidals and one
had N data samples available, i.e. D = N in [1].

I remember noting that Kay and Marple were very meticulous
in the phrasing of certain sentences concerning the case
when one has N data samples available but one does not know
the exact number of sinusoidals, D, present. Since there is
no noise, one can not talk about a "prediction error", as
we had just done in the course I had taken merely months
before; rather, they talked about "model mismatch." Kay
and Marple made some more or less ad hoc remarks that the
phrasing did not matter, since one used more or less
the same methods for minimizing the *model* error as one
would do to minimize the *prediction* error in other
applications.

So I proceeded using this no-noise, deterministic model
to analyze noisy measured data.

A couple of years later I found a different approach to
the same problem, in the article

Tufts & Kumaresan: "Estimation os frequencies of sinusoids:
    Making linear prediction behave like Maximum Likelihood"
    Proc. IEEE, September 1982.

Those guys started from the same model but derived a
different numerical routine to do the job. Tufts and
Kumaresan used a Singular Value Decomposition with some
dimension reduction steps. Their rationale was that
these computations introduce numerical errors, and
introducing the dimension reduction step improved the
numerical properties of the routine.

So I implemented their method and saw dramatic
improvements in my results.

Now, at that stage I had several issues to deal with
while analyzing my data:

1) Model mismatch: The sum-of-sines model was positively
   wrong, since the data could formally be described as
   spherical Bessel functions, culindrical Bessel functions
   or exp(x)/x type functions, at various ranges.

2) Incomplete model knowledge: I did not know what model
   order (the number of sinusoidals present) in the data

3) Errors introduced by numerical issues of computer
   computations

4) Additive noise in the measurements

Of these issues, only issue 4, additive noise, is truly
"random" in the sense that the numbers could be generated
by rolling dice [*]. Nevertheless, the "statistical" approach
to problem-solving did handle all these issues, simply
because errors don't come with tags as to their causes.

As far as I am concerned, the ideal is to use deterministic
models wherever possible. That's an ideal which is not
easily met, so one needs to deal with all these issues as
best one can, more often than not using statistical
methods.

Rune

[*] Strictly speaking, that's true for numerical errors
    as well. However, the terminology and approach to
    handle numerical errors is a bit different than
    the terminology and approach dealing with measurement
    noise.

On Jul 25, 5:24 am, Andor <andor.bari...@gmail.com> wrote:
> Friends,
>
> just now I stumbled upon this webpage:
>
> http://www.edi.lv/dasp-web/
>
> Specifically, in this chapter
>
> http://www.edi.lv/dasp-web/sec-5.htm
>
> they state that they can sample a 1.2GHz signal using a pseudo-random
> sampling instants with an average rate of 80MHz (in the last line of
> section "5.2 Aliasing, how to avoid it").
>
> I know that for nonuniform sampling, a generalization of the Sampling
> Theorem has been proved [1], which states that a bandlimited signal
> maybe reconstructed from nonuniformly spaced samples if the "average"
> sampling rate is higher than twice the bandwidth of the signal.
>
> This doesn't immediately contradict the claim above - it just says
> that if the average sampling rate exceeds a certain limit, it can be
> shown that the samples are sufficient for reconstruction. It might
> well be that if the average rate is below the limit, reconstruction is
> still possible. However, the claim still seems like magic to me,
> specifically in the light that the sampled signals underlie no
> restrictions (apart from the 1.2GHz bandwidth).
>
> Comments?
>
> Regards,
> Andor
>
> [1] F. J. Beutler, "Error-free recovery of signals from irregularly
> spaced
> samples," SIAM Rev., vol. 8, pp. 328-335, July 1966.


Hello Andor,

This is quite intriguing! I wonder besides using a psuedorandom (which
gets around Rune's objection of sometimes failing to meet some
critical threshold such as always having a mean sampling rate high
enough) sequence if a sequence that resembles the spacing of the nodes
in a Gauss-Legendre integration scheme would have this property. And
of course what are the different allowable sample distributions that
minimize the number of samples verses a nonaliased bandwidth? Radio
astronomers have played around with putting the telescopes on points
that correspond to the "inch marks" on a giant Golomb ruler.  Hence
maximizing the number of different spacings between telescopes given a
fixed number of them. Even some cell towers have the antennas for a
given sector set up on the marks of a Golomb ruler. I see some
similarities in the ideas behind these applications of nonlinear
sampling (whether temporal or spatial) even if the math works out to
be a little different. Having the sample times obey a pseudorandom or
other deterministic sequence keeps one from needing to store all of
the sample times, as they can be reconstructed at will.

Clay