Re: [music-dsp] BW limited peak computation?

[Stefan Sullivan]

TL; DR

A high-pass filter? The first and second derivatives could be easily enough
described with first and second-order feedback filters, respectively, but
once you start fitting that stuff into DSP terminology, then you might as
well make a low-order high-pass filter that has the characteristics you
desire.

If you're looking for the time of the peak, I've had a lot of luck by
taking the time (or index) of samples weighted by their values. This
produces surprisingly high accuracy. I'm sure very mathy person will tell
me why that is mathematically inaccurate, and some other mathy person will
probably tell them that it is approximately correct to some precision
criteria...



On Jul 25, 2016 2:01 PM, "Paul Stoffregen"  wrote:

> Does anyone have any suggestions or references for an efficient algorithm
> to find the peak of a bandwidth limited signal?
>
> If I just look only at the numerical values of the samples (yeah, that's
> what I've been doing), when a signal is close to an integer division of Fs,
> even collecting data over many cycles tends to miss the phases of the
> waveform containing the peaks.  For example:
>
> Image also available here: https://forum.pjrc.com/threads
> /35478-Problems-Plotting-Filter-Response?p=110442=1#post110442
>
> The only solution I'm imagining would involve expensive upsampling and
> filtering.  Even then, if I multiply the sample rate by 16 or more and the
> filter is good enough, I still might not get a sample right at the peak.
>
> Is there a better way?
>
> ___
> dupswapdrop: music-dsp mailing list
> music-dsp@music.columbia.edu
> https://lists.columbia.edu/mailman/listinfo/music-dsp
>
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] BW limited peak computation?

[Russell McClellan]

Hi, I missed this thread until now.  Last year, I published an article
on this topic here:
https://techblog.izotope.com/2015/08/24/true-peak-detection/

In it is included a proof that the true peak can be unboundedly higher
than the sample peak.

Thanks,
-Russell

On Mon, Aug 1, 2016 at 5:05 PM, Theo Verelst  wrote:
> Paul Stoffregen wrote:
>>
>> Does anyone have any suggestions or references for an efficient algorithm
>> to find the peak
>> of a bandwidth limited signal?
>>
>
> Hi,
>
> I think without getting lost in quadratic algebra or endless searches for a
> holy grail that doesn't exist that I don't take part in, you've answered the
> main theoretical question yourself: to know the signal between the samples,
> you need perfect reconstruction to the actual signal, and then analyze that.
>
> Of course, like the "Fast Lookahead Limiter" from Ladspa or LV2 which I use
> regularly does, you could up-sample to a reasonably high sampling frequency
> with the best tools you've got, and hope the best of a tool that up-samples
> another 8 times (IIRC) and leave it at it that if you're using decent input
> signals to your sampling path that there aren't a great many signals
> actually mirrors around the Nyquist frequency so that a tool like that will
> doe a reasonable flattening job.
>
> Of course it's possible there's one peak in your signal at 1/4*PI between
> two samples such that no matter what a rational fraction between samples you
> compute you could never find it with infinite accuracy... I suppose however
> in most practical cases you can have a pre-conditioned situation where you
> know which possible up-samplers are going to be used on your decent digital
> signal product, like wide window sinc, standard short interpolation and a
> couple of other methods (FIR/IIR approximations, wave shape approximations,
> multi-band approaches, and for the pro's: average based frequency components
> with multi-limited computations in the 96kHz or higher sampling domain). If
> you know what the customers are going to use as up-sampler, and once with
> the final product you make a reasonable quality wide-window sync up-sampled
> test run to see if there are any special cases to tend to, you could work
> with that, unless people enjoy endless (but not particularly useful)
> discussions on heuristics.
>
> Theo V.
>
> ___
> dupswapdrop: music-dsp mailing list
> music-dsp@music.columbia.edu
> https://lists.columbia.edu/mailman/listinfo/music-dsp
>
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] BW limited peak computation?

[Theo Verelst]

Paul Stoffregen wrote:

Does anyone have any suggestions or references for an efficient algorithm to 
find the peak
of a bandwidth limited signal?



Hi,

I think without getting lost in quadratic algebra or endless searches for a holy grail 
that doesn't exist that I don't take part in, you've answered the main theoretical 
question yourself: to know the signal between the samples, you need perfect reconstruction 
to the actual signal, and then analyze that.


Of course, like the "Fast Lookahead Limiter" from Ladspa or LV2 which I use regularly 
does, you could up-sample to a reasonably high sampling frequency with the best tools 
you've got, and hope the best of a tool that up-samples another 8 times (IIRC) and leave 
it at it that if you're using decent input signals to your sampling path that there aren't 
a great many signals actually mirrors around the Nyquist frequency so that a tool like 
that will doe a reasonable flattening job.


Of course it's possible there's one peak in your signal at 1/4*PI between two samples such 
that no matter what a rational fraction between samples you compute you could never find 
it with infinite accuracy... I suppose however in most practical cases you can have a 
pre-conditioned situation where you know which possible up-samplers are going to be used 
on your decent digital signal product, like wide window sinc, standard short interpolation 
and a couple of other methods (FIR/IIR approximations, wave shape approximations, 
multi-band approaches, and for the pro's: average based frequency components with 
multi-limited computations in the 96kHz or higher sampling domain). If you know what the 
customers are going to use as up-sampler, and once with the final product you make a 
reasonable quality wide-window sync up-sampled test run to see if there are any special 
cases to tend to, you could work with that, unless people enjoy endless (but not 
particularly useful) discussions on heuristics.


Theo V.
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] BW limited peak computation?

[Stefano D'Angelo]

2016-07-29 8:55 GMT+02:00  :
>
> On Jul 25, 2016, at 3:20 PM, Stefano D'Angelo  wrote:
>
>> Otherwise, you might very well use higher-order (i.e., not just
>> linear) interpolators, (e.g., not-a-knot cubic spline interpolator),
>
> What is a "not-a-knot cubic spline interpolator"?
> Jerry

Informally speaking, given two points between which to interpolate,
you are left with two degrees of freedom to define a cubic (spline)
interpolating function. Among all the possibilities, if you impose
continuity of the third derivatives between different splines for each
segment (as you go through samples), what you get are so-called
"not-a-knot" splines.

Best,

-- 
Stefano D'Angelo
http://sdangelo.github.io/
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] BW limited peak computation?

[Ethan Fenn]

> Because I don't think there can be more than one between any two
> adjacent sampling times.
>
>
> This really got the gears turning. It seems true, but is it a theorem?
> If not, can anyone give a counterexample?
>

I don't know whether it's a classical theorem, but I think it is true.


Yeah, I thought it was true too, but figured out some counterexamples last
night.

The simplest counterexample is two superimposed sincs which have been
shifted apart just far enough that the main hump gets a cleft in it. For
example, try plotting y(t)=sinc(t+0.175)+sinc(t-1.175), where the sinc is
normalized as you proposed. This has two maxima between 0 and 1.

You can also start with a sinc function with a cutoff that's well below
Nyquist, say Nyquist/10. Take a few of these, shift them away from each
other very slightly in time, and multiply them all together. This will
convolve the frequency spectra together, but the result will still be
bandlimited below Nyquist. Any zero of the original sinc is now several
very closely spaced zeros, which means there are also several very closely
spaced extrema. With this procedure you can generate as many local extrema
as you'd like between two samples.

The "wiggles" you get this way tend to be tiny compared to the surrounding
samples, so I think you can safely ignore this sort of thing in practice.

-Ethan





On Thu, Jul 28, 2016 at 12:18 AM, Ross Bencina 
wrote:

> On 28/07/2016 12:04 AM, Ethan Fenn wrote:
>
>> Because I don't think there can be more than one between any two
>> adjacent sampling times.
>>
>>
>> This really got the gears turning. It seems true, but is it a theorem?
>> If not, can anyone give a counterexample?
>>
>
> I don't know whether it's a classical theorem, but I think it is true.
>
> Define the normalized sinc function as:
>
> sinc(t) := sin( pi t ) / (pi t)
>
> sinc(0) = 1. the signal is analytic everywhere.
>
> A bandlimited, periodically sampled discrete-time signal {x_n} can be
> interpolated by a series of time-shifted normalized sinc functions, each
> centered at time n and scaled by amplitude x_n. This procedure can be used
> to produce the continuous-time analytic signal x(t) induced by {x_n}. We
> want to know how many peaks (direction changes) there can be in x(t)
> between x(n) and x(n+1).
>
> Sinc is bandlimited and has no frequencies above the Nyquist rate (fs/2).
> A sum of time shifted sincs is also bandlimited and therefore has no
> frequencies above the Nyquist rate.
>
> Now all you need to do is prove that a band-limited analytic signal whose
> highest frequency is fs/2 has no more than one direction change per sample
> period. I can't think how to do that formally right now, but intuitively it
> seems plausible that a signal with no frequencies above the nyquist rate
> would not have time-domain peaks spaced closer than the sampling period.
>
> Ross.
>
>
>
>
> ___
> dupswapdrop: music-dsp mailing list
> music-dsp@music.columbia.edu
> https://lists.columbia.edu/mailman/listinfo/music-dsp
>
>
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] BW limited peak computation?

[Ross Bencina]

On 28/07/2016 12:04 AM, Ethan Fenn wrote:

Because I don't think there can be more than one between any two
adjacent sampling times.


This really got the gears turning. It seems true, but is it a theorem?
If not, can anyone give a counterexample?


I don't know whether it's a classical theorem, but I think it is true.

Define the normalized sinc function as:

sinc(t) := sin( pi t ) / (pi t)

sinc(0) = 1. the signal is analytic everywhere.

A bandlimited, periodically sampled discrete-time signal {x_n} can be 
interpolated by a series of time-shifted normalized sinc functions, each 
centered at time n and scaled by amplitude x_n. This procedure can be 
used to produce the continuous-time analytic signal x(t) induced by 
{x_n}. We want to know how many peaks (direction changes) there can be 
in x(t) between x(n) and x(n+1).


Sinc is bandlimited and has no frequencies above the Nyquist rate 
(fs/2). A sum of time shifted sincs is also bandlimited and therefore 
has no frequencies above the Nyquist rate.


Now all you need to do is prove that a band-limited analytic signal 
whose highest frequency is fs/2 has no more than one direction change 
per sample period. I can't think how to do that formally right now, but 
intuitively it seems plausible that a signal with no frequencies above 
the nyquist rate would not have time-domain peaks spaced closer than the 
sampling period.


Ross.



___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] BW limited peak computation?

[Ethan Fenn]

>
> Because I don't think there can be more than one between any two adjacent
> sampling times.


This really got the gears turning. It seems true, but is it a theorem? If
not, can anyone give a counterexample?

Back to the main question... I think you're really going to need to
oversample by at least 2x. As Robert's example shows, it's hard to even
know where to look for extrema without oversampling. If you want to further
refine the extrema after doing this you could try the methods proposed by
Stefan or Xue, or try something like a golden section search using the
interpolator of your choice.

-Ethan


On Wed, Jul 27, 2016 at 1:29 AM, robert bristow-johnson <
r...@audioimagination.com> wrote:

>
>
>  Original Message ----
> Subject: Re: [music-dsp] BW limited peak computation?
> From: "Ross Bencina" <rossb-li...@audiomulch.com>
> Date: Tue, July 26, 2016 6:21 pm
> To: music-dsp@music.columbia.edu
> --
>
> > On 27/07/2016 7:09 AM, Sampo Syreeni wrote:
> >> Now, what I wonder is, could you still somehow pinpoint the temporal
> >> location of an extremum between sampling instants, by baseband logic?
> >> Because I don't think there can be more than one between any two
> >> adjacent sampling times.
> >
> > Presumably the certainty of such an estimate would depend on how many
> > baseband time samples you considered. Sinc decays as 1/x so that gives
> > you some idea of the potential influence of distant values -- not sure
> > exactly how that maps into distant sample's influence on peak location
> > though.
> >
>
> for normal bandlimited interpolation, i don't think you need to go more
> than +16 and -15 samples from the interpolated region (which is between 0
> and 1) and i don't think you'll need to have more than 16 or 32 phases.
>  and i think you can decently apply quadratic interpolation between those
> 1/16th or 1/32nd sample values and you'll have, for all quantitative
> purposes, a very good interpolation of the peak.
>
> dunno what exactly is meant by "baseband logic".
>
>
> --
>
>
>
>
> r b-j  r...@audioimagination.com
>
>
>
>
> "Imagination is more important than knowledge."
>
> ___
> dupswapdrop: music-dsp mailing list
> music-dsp@music.columbia.edu
> https://lists.columbia.edu/mailman/listinfo/music-dsp
>
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] BW limited peak computation?

[robert bristow-johnson]

 Original Message 

Subject: Re: [music-dsp] BW limited peak computation?

From: "Ross Bencina" <rossb-li...@audiomulch.com>

Date: Tue, July 26, 2016 6:21 pm

To: music-dsp@music.columbia.edu

--



> On 27/07/2016 7:09 AM, Sampo Syreeni wrote:

>> Now, what I wonder is, could you still somehow pinpoint the temporal

>> location of an extremum between sampling instants, by baseband logic?

>> Because I don't think there can be more than one between any two

>> adjacent sampling times.

>

> Presumably the certainty of such an estimate would depend on how many

> baseband time samples you considered. Sinc decays as 1/x so that gives

> you some idea of the potential influence of distant values -- not sure

> exactly how that maps into distant sample's influence on peak location

> though.

>
for normal bandlimited interpolation, i don't think you need to go more than 
+16 and -15 samples from the interpolated region (which is between 0 and 1) and 
i don't think you'll need to have more than 16 or 32 phases. �and i think you 
can decently apply quadratic interpolation
between those 1/16th or 1/32nd sample values and you'll have, for all 
quantitative purposes, a very good interpolation of the peak.
dunno what exactly is meant by "baseband logic".

--
�


r b-j � � � � � � � � � � �r...@audioimagination.com
�


"Imagination is more important than knowledge."
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] BW limited peak computation?

[Ross Bencina]

On 27/07/2016 7:09 AM, Sampo Syreeni wrote:

Now, what I wonder is, could you still somehow pinpoint the temporal
location of an extremum between sampling instants, by baseband logic?
Because I don't think there can be more than one between any two
adjacent sampling times.


Presumably the certainty of such an estimate would depend on how many 
baseband time samples you considered. Sinc decays as 1/x so that gives 
you some idea of the potential influence of distant values -- not sure 
exactly how that maps into distant sample's influence on peak location 
though.


Ross.
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] BW limited peak computation?

[Sampo Syreeni]

On 2016-07-26, Stefan Stenzel wrote:

the acid test is when the pre-upsampled data is alternating signs on 
a large amplitude with *one* sample missing.  like:


 ... -A, +A, -A, +A, -A, +A, -A, +A, -A, +A, -A, +A, -A, +A, -A, +A, -A, +A, 
+A, -A, +A, -A, +A, -A, +A, -A, +A, -A, +A, -A, +A, -A, +A, -A, +A, ...

you might get an unnaturally large peak (many times bigger than |A|) 
with that.


Should be something like the sum of all 2A/(pi*(t+0.5)) for t an 
integer going from zero to infinity. Not sure if that converges.


It doesn't. Intuitively speaking, after some heady limit arguments, a 
pure ...,+1, -1, +1,-1,... train decodes as a sinusoid at the Nyquist 
frequency. It does so because of phase cancellation between the various, 
in-phase but at least double in period sinusoids which go into the 
Nyquist-Shannon reconstruction.


What this particular sequence does is, it sums two one-sided alternating 
sequences together, too. But it does it so that it leaves out a single 
sample at the origin, and by doing so, pushes those otherwise nicely 
cancelling, marginal cosines from the various sinc(x) functions into 
phase between two sampling times. Obviously what you get then is not 
convergence, but very fast divergence. All within the band-limited 
interpolation theorem, which in the limit only applies in general 
strictly below the Nyquist frequency. (This stuff for once doesn't 
converge even in the weak, distribution sense.)


Now, what I wonder is, could you still somehow pinpoint the temporal 
location of an extremum between sampling instants, by baseband logic? 
Because I don't think there can be more than one between any two 
adjacent sampling times. And if you can pinpoint its location, then I 
believe you could derive an iterative algorithm relying on higher and 
higher, recursively computed interpolation formulae which could drive 
the uncertainty in its location as low as necessary. On the fly. 
Irrespective of what the real *amplitude* of the thing really is.


If you could do that, I think you could then put upper bounds on both 
the L^1 and L^2 norms of the deviation above full range, between the 
sampling instants, in closed form. And once you'd done that, I think you 
could pretty much tame any sonically/musically relevant problem 
happening "between the samples", as well: just take note of where the 
peak seems to be for phase stuff, and then take note of how rapidly your 
interpolands grow, for an approximation of what you should do wrt

amplitude.
--
Sampo Syreeni, aka decoy - de...@iki.fi, http://decoy.iki.fi/front
+358-40-3255353, 025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] BW limited peak computation?

[Stefan Stenzel]

Paul,

It all depends what you consider a peak. Imagine a single sample of one, 
surrounded by nothing but zeros left and right, upsampling this signal would 
bring up many peaks that you might not be interested in.

For practical purposes I suggest you start with the simple approach to search 
for a sample with neighbours smaller in magnitude, refine the fractional 
position of the peak and then evaluate the peak value at this position. A 
simple quadratic function and its derivative for this:

suppose a,b,c are successive samples and b having maximum magnitude:

fraction(a,b,c)  = (a-c)/(2a-4b+2c)
value(a,b,c,fraction) = ((a-2b+c)fraction^2 + (c-a)fraction + 2b)/2

This would work well with the data in your graphs.

Stefan

> On 25 Jul 2016, at 23:00 , Paul Stoffregen  wrote:
> 
> Does anyone have any suggestions or references for an efficient algorithm to 
> find the peak of a bandwidth limited signal?
> 
> If I just look only at the numerical values of the samples (yeah, that's what 
> I've been doing), when a signal is close to an integer division of Fs, even 
> collecting data over many cycles tends to miss the phases of the waveform 
> containing the peaks.  For example:
> 
> 
> Image also available here: 
> https://forum.pjrc.com/threads/35478-Problems-Plotting-Filter-Response?p=110442=1#post110442
> 
> The only solution I'm imagining would involve expensive upsampling and 
> filtering.  Even then, if I multiply the sample rate by 16 or more and the 
> filter is good enough, I still might not get a sample right at the peak.
> 
> Is there a better way?
> ___
> dupswapdrop: music-dsp mailing list
> music-dsp@music.columbia.edu
> https://lists.columbia.edu/mailman/listinfo/music-dsp

___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] BW limited peak computation?

[Wen Xue]

I suggest the cubic spline interpolator. It expresses the underlying function 
as piecewise trinomial so that the maxima/minima can be computed by solving 
binomial equations. It is also known to be close to the ideal sync 
interpolation alias-wise. 

Xue



From: Paul Stoffregen___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] BW limited peak computation?

[Stefano D'Angelo]

2016-07-25 23:00 GMT+02:00 Paul Stoffregen :
>
> Does anyone have any suggestions or references for an efficient algorithm to 
> find the peak of a bandwidth limited signal?
>
> If I just look only at the numerical values of the samples (yeah, that's what 
> I've been doing), when a signal is close to an integer division of Fs, even 
> collecting data over many cycles tends to miss the phases of the waveform 
> containing the peaks.  For example:
>
> Image also available here: 
> https://forum.pjrc.com/threads/35478-Problems-Plotting-Filter-Response?p=110442=1#post110442
>
> The only solution I'm imagining would involve expensive upsampling and 
> filtering.  Even then, if I multiply the sample rate by 16 or more and the 
> filter is good enough, I still might not get a sample right at the peak.
>
> Is there a better way?

I'm no special expert in these matters, however I'll try to help.

AFAIK it really depends on the application. As you noticed, just
comparing sample values is not always sufficient, and that is the case
when the signal has relatively strong frequency components not too far
from the Nyquist limit (well, I mean, something like fs/10 or
something like that).

Then, you obviously do need some sort of resampling/interpolation (or
at least, I don't know any cheaper alternative to that). IIRC, the
ITU-R BS.1770 even goes as far as suggesting a specific 4x polyphase
filter to cope with this problem somehow (I guess it was was the "true
peak meter" thing... I guess you easily can check it yourself).

Otherwise, you might very well use higher-order (i.e., not just
linear) interpolators, (e.g., not-a-knot cubic spline interpolator),
and check for first derivative sign change on the "reconstructed" part
of the signal. This is most likely much cheaper, but also more
"risky", as its precision could be very sensitive to the kind of input
signal you have.

In both cases, you need to careful about Gibbs (resampler) / Runge
(interpolator) phenomena. Theoretically speaking, if your signal is
"perfectly bandlimited", Gibbs fluctuations would indeed be "valid",
but in the real world that's probably not the case.

So... according to my limited knowledge, it all boils down to what you
are really trying to do.

Hope this helps somehow,

-- 
Stefano D'Angelo
http://sdangelo.github.io/
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp