0
$\begingroup$

I have a PPG signal and I wanted to write a code that gives the maxima and minima value of signal by using frequency domain method. Any suggestions?

$\endgroup$
  • 1
    $\begingroup$ What is a reason you want to use frequency domain method for such simple task? I am afraid it is not possible at all. $\endgroup$ – SergV Sep 12 '15 at 11:16
  • $\begingroup$ What is a PPG signal? Why do you think the maxima or minima can be found better in the frequency domain than the time domain? $\endgroup$ – Peter K. Sep 12 '15 at 20:59
2
$\begingroup$

Global maximum

Representation of a signal from DFT components is:

$$f[n] = \frac{1}{N} \sum_{k=0}^{N-1} F[k] e^{i 2\pi k n /N}$$

Let $\theta = 2\pi n /N$

$$f[N\theta/(2\pi)] = \frac{1}{N} \sum_{k=0}^{N-1} F[k] e^{i k \theta}$$

This is a trigonometric polynomial with coefficients $F[k]/N$. Finding the maximum is the same as for a normal polynomial, at the maximum the derivative is 0. Thus you calculate the derivative polynomial,

$$\frac{1}{N} \sum_{k=0}^{N-1} i k F[k] e^{i k \theta}$$

Use root finding to obtain $N-1$ possible values of $\theta$ (the roots), substitute them back into the original polynomial and choose the one that corresponds to the maximum. Then $n$ can be found as $n = N\theta/(2\pi)$.

Global minimum

Same as the above except you choose the value of the original polynomial that is a minimum

Local maxima and minima

Find the $N-1$ roots of the polynomial as before. Discard any points which do not correspond to derivative of zero. The remaining points are local maxima or minima. At the local maxima the second derivative is negative, at local minima it is positive.

$\endgroup$
  • $\begingroup$ Interesting idea but very impractical. Finding the roots of a polynomial is difficult and prone to numerical errors especially if the order of the polynomial is large. It is much easier to do a simple inverse Fourier Transform and find the max/min directly in the time domain, $\endgroup$ – Hilmar Sep 12 '15 at 14:57
  • 1
    $\begingroup$ Excellent answer, never thought of it that way :) But seriously, finding the roots of that polynomial is, for almost any $N$, way more computational intense than just taking the (i)DFT and linearly searching for the max/min. Finding the roots of a polynomial is typically done using an Eigenvalue decomposition, which is waaaaay worse (known algorithms have complexity $cN^3+ O(N^2)$) than DFT + linear search (FFT: $O(N \log N)$ and linear search: $N$, so $N+ O(N \log N)\ll cN^3+ O(N^2)$). $\endgroup$ – Marcus Müller Sep 12 '15 at 14:58
  • $\begingroup$ Obviously, the problem is ill-conditioned for EVD if the signal has multiple extrema, which, sadly, is likely for the signals you'd typically push through a DFT. $\endgroup$ – Marcus Müller Sep 12 '15 at 14:59
  • $\begingroup$ @MarcusMüller Yep, excellent points. One thing, though more applicable to the continuous case, for small $N$ you can get a... finer... estimate for $\theta$ than from to solving it discretely. I actually made a quick approximation method that gives a useable estimation of $\theta$ in linear time, because solving roots for every pixel in an image takes fooooreeeeeveeerr $\endgroup$ – geometrikal Sep 13 '15 at 2:40
  • $\begingroup$ @geometrikal: ah good point; That's the analogous for the "hyperefficienty" of EVD/autocorrelation-based spectrum estimators like MUSIC, whereyour spectral resolution is also higher than that of the DFT of the same input data. $\endgroup$ – Marcus Müller Sep 13 '15 at 8:04
1
$\begingroup$

After reading geometrikal's answer, I came to the conclusion (after only having the intuition) that the fastest, and easiest, method will just be transforming your vector back to time domain and simply search for the extrema in time domain.

Trying to extract something that is trivial to get in time domain but doesn't exist in frequency domain, using frequency domain, is simply nonsensical.

$\endgroup$
  • $\begingroup$ This problem comes up in another context: steerable filters. Basically the responses to a steerable filter basis are the coefficients of a trigonometric polynomial. The maximum of the polynomial is the optimum orientation to steer the filter to. Typically the number of filters in the basis set is small, so the degree of the polynomial is small. To get a good estimate of the orientation one either solves the roots or evaluates the polynomial at discrete points. The former obviously gives the more accurate estimate. $\endgroup$ – geometrikal Sep 13 '15 at 2:47
  • $\begingroup$ he, you just accidentally gave me an idea how to approach a completely different problem. Thanks, @geometrikal! $\endgroup$ – Marcus Müller Sep 13 '15 at 8:05
  • $\begingroup$ Nice, what problem are you working on? Have a look at this paper too - might be helpful for similar problems: statweb.stanford.edu/~candes/papers/super-res.pdf $\endgroup$ – geometrikal Sep 13 '15 at 10:57
  • $\begingroup$ @geometrikal : implementing time-variant filters for real time cyclostationary channel simulation... I'll have to sleep over this one. $\endgroup$ – Marcus Müller Sep 13 '15 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.