Skip to main content
Signal Processing

Return to Answer

added 22 characters in body
Source Link
OverLordGoldDragon
OverLordGoldDragon
  • 9.2k
  • 5
  • 27
  • 88

The inverse solution to the sine DFT closed form solution retrieves amplitude, phase, and frequency from DFT, exactly, for all $N \geq 3$. $N\leq 2$ is under-determined (non-unique recovery). The greater the $N$, the better the performance under noise.

Noiseless

Here's the worst case, $N=3$:

These are maximum squared errors for per a given frequency.

  • Frequency (fractional) is swept 0 to 0.5, skipping integers per numeric instability of the specific implementation used (which can be overcome, and integer $f$ is the most trivial)
  • Phase is linearly swept -pi to pi
  • Amplitude is swept, logarithmically, 1e-3 to 1000, and a normalized error measure is used to avoid artificially inflating the measure: (1 - A_est/A_true)**2.

Noisy

Performance improves with greater $N$, linearly with $N$ over high SNR. In fact, can be super-linear in low SNR in that the CRLB-matching (Cramer Rao Lower Bound, unbiased estimator) interval is increased. For under a second of audio:

Phase is always the most brittle, frequency least. Frequency performance, in accuracy and speed, may be state of the art - see competitive comparison.

OP's case

For OP's setup, except nudging the frequency a little (for aforementioned reasons) to 30.1, and randomizing phase, the results are

MSE: A=1.73e-05, phi=0.0513 -- SNR=23, N=300, n_trials=10000

For greater $N$:

MSE: A=1.7e-06,  phi=0.00395  -- SNR=23, N=3000,  n_trials=10000
MSE: A=1.02e-07, phi=5.77e-07 -- SNR=23, N=50000, n_trials=10000

Once the CRLB interval is matched, performance is phenomenal, and still decent otherwise.

Speed

The parameter retrieval step is $O(1)$ for all parameters. Hence the overall algorithm is just $O(N\log(N))$, FFT + absolute argmax. Interestingly, this faster than certain popular $O(N)$ algorithms - note, $O(N)$ means the full cost function (bound) is $c_0N + c_1$, and FFT's $c_0$ is low.

The method

A Two Bin Solution, by Cedron Dawg.

Notes

  • $N=2$ is doable for complex sines, that have a total of 4 datapoints. Hence Hilbert transform of pre-sampled signal is an option (analytic signal).
  • Noiseless case: if accounting for numeric precision, $N=3$ is the best case, since FFT suffers the least error. $N=3$ is worst in that we have the least possible information to work with, and any estimators (as opposed to exact solutions) suffer greatest error.

Code

Available at Github.

The inverse solution to the sine DFT closed form solution retrieves amplitude, phase, and frequency from DFT, exactly, for all $N \geq 3$. $N\leq 2$ is under-determined (non-unique recovery). The greater the $N$, the better the performance under noise.

Noiseless

Here's the worst case, $N=3$:

These are maximum squared errors for per a given frequency.

  • Frequency (fractional) is swept 0 to 0.5, skipping integers per numeric instability of the specific implementation used (which can be overcome, and integer $f$ is the most trivial)
  • Phase is linearly swept -pi to pi
  • Amplitude is swept, logarithmically, 1e-3 to 1000, and a normalized error measure is used to avoid artificially inflating the measure: (1 - A_est/A_true)**2.

Noisy

Performance improves with greater $N$, linearly with $N$ over high SNR. In fact, can be super-linear in low SNR in that the CRLB-matching (Cramer Rao Lower Bound, unbiased estimator) interval is increased. For under a second of audio:

Phase is always the most brittle, frequency least. Frequency performance, in accuracy and speed, may be state of the art - see competitive comparison.

OP's case

For OP's setup, except nudging the frequency a little (for aforementioned reasons) to 30.1, and randomizing phase, the results are

MSE: A=1.73e-05, phi=0.0513 -- SNR=23, N=300, n_trials=10000

For greater $N$:

MSE: A=1.7e-06,  phi=0.00395  -- SNR=23, N=3000,  n_trials=10000
MSE: A=1.02e-07, phi=5.77e-07 -- SNR=23, N=50000, n_trials=10000

Once the CRLB interval is matched, performance is phenomenal, and still decent otherwise.

Speed

The parameter retrieval step is $O(1)$ for all parameters. Hence the overall algorithm is just $O(N\log(N))$, FFT + absolute argmax. Interestingly, this faster than certain popular $O(N)$ algorithms - note, $O(N)$ means the full cost function (bound) is $c_0N + c_1$, and FFT's $c_0$ is low.

The method

A Two Bin Solution, by Cedron Dawg.

Notes

  • $N=2$ is doable for complex sines, that have a total of 4 datapoints. Hence Hilbert transform is an option (analytic signal).
  • Noiseless case: if accounting for numeric precision, $N=3$ is the best case, since FFT suffers the least error. $N=3$ is worst in that we have the least possible information to work with, and any estimators (as opposed to exact solutions) suffer greatest error.

Code

Available at Github.

The inverse solution to the sine DFT closed form solution retrieves amplitude, phase, and frequency from DFT, exactly, for all $N \geq 3$. $N\leq 2$ is under-determined (non-unique recovery). The greater the $N$, the better the performance under noise.

Noiseless

Here's the worst case, $N=3$:

These are maximum squared errors for per a given frequency.

  • Frequency (fractional) is swept 0 to 0.5, skipping integers per numeric instability of the specific implementation used (which can be overcome, and integer $f$ is the most trivial)
  • Phase is linearly swept -pi to pi
  • Amplitude is swept, logarithmically, 1e-3 to 1000, and a normalized error measure is used to avoid artificially inflating the measure: (1 - A_est/A_true)**2.

Noisy

Performance improves with greater $N$, linearly with $N$ over high SNR. In fact, can be super-linear in low SNR in that the CRLB-matching (Cramer Rao Lower Bound, unbiased estimator) interval is increased. For under a second of audio:

Phase is always the most brittle, frequency least. Frequency performance, in accuracy and speed, may be state of the art - see competitive comparison.

OP's case

For OP's setup, except nudging the frequency a little (for aforementioned reasons) to 30.1, and randomizing phase, the results are

MSE: A=1.73e-05, phi=0.0513 -- SNR=23, N=300, n_trials=10000

For greater $N$:

MSE: A=1.7e-06,  phi=0.00395  -- SNR=23, N=3000,  n_trials=10000
MSE: A=1.02e-07, phi=5.77e-07 -- SNR=23, N=50000, n_trials=10000

Once the CRLB interval is matched, performance is phenomenal, and still decent otherwise.

Speed

The parameter retrieval step is $O(1)$ for all parameters. Hence the overall algorithm is just $O(N\log(N))$, FFT + absolute argmax. Interestingly, this faster than certain popular $O(N)$ algorithms - note, $O(N)$ means the full cost function (bound) is $c_0N + c_1$, and FFT's $c_0$ is low.

The method

A Two Bin Solution, by Cedron Dawg.

Notes

  • $N=2$ is doable for complex sines, that have a total of 4 datapoints. Hence Hilbert transform of pre-sampled signal is an option (analytic signal).
  • Noiseless case: if accounting for numeric precision, $N=3$ is the best case, since FFT suffers the least error. $N=3$ is worst in that we have the least possible information to work with, and any estimators (as opposed to exact solutions) suffer greatest error.

Code

Available at Github.

Source Link
OverLordGoldDragon
OverLordGoldDragon
  • 9.2k
  • 5
  • 27
  • 88

The inverse solution to the sine DFT closed form solution retrieves amplitude, phase, and frequency from DFT, exactly, for all $N \geq 3$. $N\leq 2$ is under-determined (non-unique recovery). The greater the $N$, the better the performance under noise.

Noiseless

Here's the worst case, $N=3$:

These are maximum squared errors for per a given frequency.

  • Frequency (fractional) is swept 0 to 0.5, skipping integers per numeric instability of the specific implementation used (which can be overcome, and integer $f$ is the most trivial)
  • Phase is linearly swept -pi to pi
  • Amplitude is swept, logarithmically, 1e-3 to 1000, and a normalized error measure is used to avoid artificially inflating the measure: (1 - A_est/A_true)**2.

Noisy

Performance improves with greater $N$, linearly with $N$ over high SNR. In fact, can be super-linear in low SNR in that the CRLB-matching (Cramer Rao Lower Bound, unbiased estimator) interval is increased. For under a second of audio:

Phase is always the most brittle, frequency least. Frequency performance, in accuracy and speed, may be state of the art - see competitive comparison.

OP's case

For OP's setup, except nudging the frequency a little (for aforementioned reasons) to 30.1, and randomizing phase, the results are

MSE: A=1.73e-05, phi=0.0513 -- SNR=23, N=300, n_trials=10000

For greater $N$:

MSE: A=1.7e-06,  phi=0.00395  -- SNR=23, N=3000,  n_trials=10000
MSE: A=1.02e-07, phi=5.77e-07 -- SNR=23, N=50000, n_trials=10000

Once the CRLB interval is matched, performance is phenomenal, and still decent otherwise.

Speed

The parameter retrieval step is $O(1)$ for all parameters. Hence the overall algorithm is just $O(N\log(N))$, FFT + absolute argmax. Interestingly, this faster than certain popular $O(N)$ algorithms - note, $O(N)$ means the full cost function (bound) is $c_0N + c_1$, and FFT's $c_0$ is low.

The method

A Two Bin Solution, by Cedron Dawg.

Notes

  • $N=2$ is doable for complex sines, that have a total of 4 datapoints. Hence Hilbert transform is an option (analytic signal).
  • Noiseless case: if accounting for numeric precision, $N=3$ is the best case, since FFT suffers the least error. $N=3$ is worst in that we have the least possible information to work with, and any estimators (as opposed to exact solutions) suffer greatest error.

Code

Available at Github.