# Frequency estimation - Minimising the number of samples

• A
• f95toli
In summary, frequency estimation of a noisy sine signal can be done by using non-uniform sampling and least-squares spectral analysis. However, finding the optimal sampling times may require some trial and error, including using Monte Carlo methods. With a large spread in frequencies, a combination of a logarithmic progression and random sampling may be effective. The ideal pattern for sampling would involve increasing distances between samples to increase the lever arm and reduce uncertainty.
f95toli
Gold Member
TL;DR Summary
What is the "best" real-time algorithm for frequency estimation if the goal is to minimise the number if samples
I have a practical question about frequency estimation of a noisy sine

In some of my experiments I need to estimate the frequency of a noisy damped sine.
Currently I just use uniform sampling (sampling at times t=n*T) (making sure to exceed the Nyquist criteria) followed by an FFT.

In the experiment I apply an excitation at time t0 and then wait for a time t before sampling for a short time(<<t). By repeating this thousands of times and gradually sweeping t, I can reconstruct the waveform (which typically last for 100 us before it decays into the noise floor).

Now, since the signal is noisy I need to average each sample for a very long time making this very time consuming.

My question is if there is a better way of doing this? There are three things that -naively- should mean that it might be possible to speed up the measurement:
-There is no reason for why I need sample uniformly. Would non-uniform sampling help? I believe the answer is yes, but how do I choose the sample times?
-I am doing this in "real" time, if needed I can decide where to sample next based on existing data.
-I can be quite confident that the signal is dominated by a single frequency, i.e. I just need to extract a single value.

Are there any methods which utilise one of more of these "advantages"?
I assumed this would be a common problem; but haven't had much luck when searching the literature. The best lead so far is:

https://www.sciencedirect.com/science/article/abs/pii/S1051200408001577

However, this is a new(ish) algorithm which I would need to implement myself. Are there no established methods ?
Ideally, I would like to find something that someone else has already implemented and tested.,,,

f95toli said:
In some of my experiments I need to estimate the frequency of a noisy damped sine
...
By repeating this thousands of times and gradually sweeping t, I can reconstruct the waveform (which typically last for 100 us before it decays into the noise floor
You don't mention how many periods you get in 100 ##\mu##s. If that is a large number: how about a discriminator and just count for, say, 90 ##\mu##s ?

The best sampling times depends on the details of your measurement: how many cycles of your sinusoid signal evolve during your measurement (in other words, what's your average expected frequency times measurement time)? How many cycles does this change due to frequency uncertainty (std. deviation of frequency times measurement time)?

When I was faced with a similar problem, I ultimately turned to Monte Carlo methods to find the best sampling strategy. I tried a lot of schemes: linear sampling, periodic sampling, prime-number-spaced sampling, "chunks" of samples close together spaced linearly or by prime numbered intervals. However, in my particular case, random sample times actually worked best of everything I tried. The reason was that the variation in phase was large relative to the total phase evolved, and randomly spaced samples have very little phase relation to each other (very low aliasing). Whatever you do, I encourage a little trial and error because the results may surprise you.

If you aren't already familiar, the standard mathematical method for frequency estimation of data at non-uniform spacing is least-squares spectral analysis. You can find an efficient implementation in section 13.8 of "Numerical Recipes in C" Second Edition.

BvU said:
You don't mention how many periods you get in 100 ##\mu##s. If that is a large number: how about a discriminator and just count for, say, 90 ##\mu##s ?

Unfortunately, the period of the signal can vary from ~10ns to 10 us (in theory in the interval is even larger). The period depends on the frequency of the excitation (or to be more exact: the difference between the resonance frequency of the system and the excitation signal)
This is why something "simple" like counting zero-crossings is unlikely to work well.

In case someone is wondering: I am doing Ramsey spectroscopy of a qubit and am trying to speed up the measurements

Last edited:
BvU
Twigg said:
If you aren't already familiar, the standard mathematical method for frequency estimation of data at non-uniform spacing is least-squares spectral analysis. You can find an efficient implementation in section 13.8 of "Numerical Recipes in C" Second Edition.

Thanks. That sounds like a very good starting point

f95toli said:
Unfortunately, the period of the signal can vary from ~10ns to 10 us (in theory in the interval is even larger).

That sounds like one unruly qubit, yikes! I think you're on the right track with non-uniform spacing, and I'd recommend Monte Carlo experimentation.

Just to clarify, least squares spectral analysis (LSSA) will give you a frequency given a set of non-uniformly-spaced data; unfortunately it doesn't tell you how to optimize your sample times.

Edit: With such a large spread in frequencies, you might consider something funky like a logarithmic progression of times with some random times mixed in? The idea being the logarithmic progression would give you the order of magnitude of the frequency and the random times might give you some immunity to whatever aliasing a logarithmic sequence causes. From there, once you have the ballpark of the frequency you could programmatically add ramsey times to hone in on a narrower frequency range. Just a thought.

How long is your sampling time?
If your signal can have a period of 10 us and lasts for 100 us then the frequency can't be that sharp.

Let's look at the other extreme first: Obviously you want some samples that are close together to look for possible short period signals. How many samples you need for an initial frequency estimate depends on experiment details but it will be a small number. If you then sample at the distance where your phase uncertainty reaches pi you get a lot of information but there will be some ambiguity that should be resolvable with another measurement. In general I would expect the ideal pattern to have measurements with increasing distance to each other, each time increasing your lever arm and therefore reducing the uncertainty enough to interpret the next measurement.

This only works if you have many periods to check, of course. 10 us will need a different strategy, most likely a closer measurement of the time where the signal still has a large amplitude.

mfb said:
How long is your sampling time?
If your signal can have a period of 10 us and lasts for 100 us then the frequency can't be that sharp.

It varies quite a bit, from maybe a few minutes or so to several hours; depending on how many samples I use and what I am trying to do.
Part of the reason why Ramsey sequences are somewhat tricky is that both the frequency of the system (qubit) and the excitation pulse is in the microwave range (~typically 3-4 GHz). Since period of the Ramsey oscillations depends on the difference in frequency between these signals even a small (relative) frequency difference will therefore result in oscillations with short periods.
A typical strategy would therefore be to use first uses other types of spectroscopy to try get a good estimate of the system(qubit) frequency and then use Ramsey to get a more accurate measurement of the frequency difference from which -since you know the excitation frequency- you can calculate the system frequency (as well as determine T2, but that is another story).

Now, this is not an issue if I am doing everything manually and everything is stable since I only have to do it once. However, the system (qubit) frequency can also spontaneously change due to external or intrinsic noise. An accurate way of detecting these frequency fluctuations is to do repeated Ramsey measurement; this means if you want to be able to see fast changes you need to be able to determine the frequency of the Ramsey oscillation as quickly as possible.

Anyway, ideally I would therefore like to have fast, automated procedure for doing this which I why I started looking at this.

To clarify, have you observed periods between 10ns and 100us? Or are you looking for a yet-to-be-seen signal in that frequency range? On first reading, I thought you meant that you had slow fluctuations between fringes that cause your frequency to drift around in the 10ns to 100us interval. However, if you are doing your initial spectroscopy, then you may just want to brute force this with a range of uniform sampling times before diving into the math, or at least run the experiment while you read. This isn't the kind of thing you can solve on a napkin over lunch (or at least, not for my brain).

Edit: If the issue is slowly drifting frequencies, what's the timescale like and how fast is your repitition rate (aka how many times can you do a measurement, from state prep to readout, per second)?

Twigg said:
To clarify, have you observed periods between 10ns and 100us?

Almost. Not quite to 100 us, but from say 10ns to ~10 us. Again, the period depends on the frequency difference so if I sweep my excitation frequency the period of the observed oscillations will change with it. In theory I can get whatever frequency I want, but there are other factors that start to limit the visibility for large detunings.

Typically, the goal is to get the excitation frequency close enough so that you can see a few oscillations (enough to determine the system frequency) in a reasonable time-span (say 10 us or so).
Doing this manually is fine, but as mentioned it can be very time consuming and I would also like to automate it.

Can you roughly predict the fringe frequency from the excitation frequency and amplitude? It doesn't have to be a great correlation, any kind of guess will reduce the number of samples you need to take. I can explain more, I'm just still trying to get the full picture first.

f95toli said:
It varies quite a bit, from maybe a few minutes or so to several hours; depending on how many samples I use and what I am trying to do.
I meant the sampling time you mentioned in post 1:
f95toli said:
then wait for a time t before sampling for a short time(<<t)

mfb said:
I meant the sampling time you mentioned in post 1:
That is a bit complicated. I am using the "standard" technique in my field, meaning heterodyne pulsed dispersive read-out. What I am actually detecting is the dispersive shift(which is state dependent) of a read-out resonator. This is done by sending a near-resonant pulse and then measuring the phase of the transmitted pulse. The length of this read-out pulse varies but typically something like ~5us works well.
Usually, I average about 1000 times.

## 1. How does frequency estimation work?

Frequency estimation is a process used in signal processing to determine the frequency of a signal or waveform. It involves analyzing a set of samples of the signal and using mathematical techniques to estimate the underlying frequency.

## 2. Why is minimizing the number of samples important in frequency estimation?

Minimizing the number of samples is important in frequency estimation because it helps to reduce the computational complexity and processing time required. This is especially useful when dealing with large datasets or real-time applications where efficiency is crucial.

## 3. What techniques are commonly used to minimize the number of samples in frequency estimation?

There are several techniques that can be used to minimize the number of samples in frequency estimation, such as the Fast Fourier Transform (FFT), Prony's method, and the MUSIC algorithm. These methods use different mathematical approaches to estimate the frequency with fewer samples.

## 4. How accurate is frequency estimation with a reduced number of samples?

The accuracy of frequency estimation with a reduced number of samples depends on the specific technique used and the characteristics of the signal being analyzed. In general, the accuracy may decrease slightly with fewer samples, but it can still provide a reliable estimate within a certain margin of error.

## 5. Are there any limitations to minimizing the number of samples in frequency estimation?

While minimizing the number of samples can be beneficial in terms of efficiency, there are some limitations to consider. With fewer samples, there may be a trade-off between accuracy and processing time. Additionally, certain techniques may only work well for specific types of signals and may not be suitable for all applications.

• General Math
Replies
14
Views
1K
• General Math
Replies
17
Views
1K
• Electrical Engineering
Replies
4
Views
945
• Computing and Technology
Replies
9
Views
2K
• MATLAB, Maple, Mathematica, LaTeX
Replies
4
Views
1K
• General Math
Replies
2
Views
995
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
• Electrical Engineering
Replies
7
Views
3K
• General Engineering
Replies
5
Views
2K
• General Math
Replies
2
Views
965