It seems that the MUSIC algorithm is for estimation of sinusoids. Is there an adaptation or other similar algorithm that can be applied to estimate the fundamental frequencies of a mixture of periodic signals? -- % Randy Yates % "...the answer lies within your soul %% Fuquay-Varina, NC % 'cause no one knows which side %%% 919-577-9882 % the coin will fall." %%%% <yates@ieee.org> % 'Big Wheels', *Out of the Blue*, ELO http://www.digitalsignallabs.com
MUSIC Algorithm: Suitable for General Periodic Signals?
Started by ●December 2, 2008
Reply by ●December 2, 20082008-12-02
On 2 Des, 15:54, Randy Yates <ya...@ieee.org> wrote:> It seems that the MUSIC algorithm is for estimation of sinusoids. �Is > there an adaptation or other similar algorithm that can be applied to > estimate the fundamental frequencies of a mixture of periodic signals?I don't think so. MUSIC (and friends) is based on the very specific sum-of-sines parametric model. 'Periodic' is a bit too vague to fit into the analytical framework required by the parametric models. Rune
Reply by ●December 3, 20082008-12-03
Randy Yates wrote:> It seems that the MUSIC algorithm is for estimation of sinusoids. Is > there an adaptation or other similar algorithm that can be applied to > estimate the fundamental frequencies of a mixture of periodic signals?Hello Randy In the presence of noise and with only finitely many samples of the signal, I don't think your task is solvable, unless you can supply some constraints. Consider x1[n] = cos(w1 n) and x2[n] = cos(1.00000001 * w1 n). for some 0<w1<pi. Even though the sum x1 + x2 has a fundamental period T = 100000010000 2 pi/w1 you need very many samples (multiple periods) to determine the period. It's even worse for x3[n] = cos((1+sqrt(2)/100000000) * w1 n) where x1+x3 has no fundamental period, and the frequencies of the two summands differ by an arbitrarily small amount. Regards, Andor
Reply by ●December 3, 20082008-12-03
On 3 Des, 09:45, Andor <andor.bari...@gmail.com> wrote:> Randy Yates wrote: > > It seems that the MUSIC algorithm is for estimation of sinusoids. �Is > > there an adaptation or other similar algorithm that can be applied to > > estimate the fundamental frequencies of a mixture of periodic signals? > > Hello Randy > > In the presence of noise and with only finitely many samples of the > signal, I don't think your task is solvable, unless you can supply > some constraints.> you need very many samples (multiple periods) to determine the period.Wrong. MUSIC can do that in very few samples, depending on the SNR. The reason is that MUSIC uses certain facts about signal covariance matrices and match them up with the analytic expressions for the sinusoidal terms. The downside is that MUSIC is totally dependent on this relation between the covariance matrix and the analtitical expression. The consequence is that if there are more sinusodial signals present than the covariance matrix can handle, MUSIC fails. If the signal does not comply to the analytical sum-of-sines signal model, MUSIC fails. But as long as circumstances line up in the MUSIC direction, it is a good tool that provides results close to the CRB (I can't find my copy of Kay's 1988 book right now, but I remeber there was a graph in ch. 13 which showed that MUSIC has attained the CRB at an SNR around 15 or 20 dB or so). Rune
Reply by ●December 3, 20082008-12-03
On 3 Dez., 11:04, Rune Allnor <all...@tele.ntnu.no> wrote:> On 3 Des, 09:45, Andor <andor.bari...@gmail.com> wrote: > > > Randy Yates wrote: > > > It seems that the MUSIC algorithm is for estimation of sinusoids. �Is > > > there an adaptation or other similar algorithm that can be applied to > > > estimate the fundamental frequencies of a mixture of periodic signals? > > > Hello Randy > > > In the presence of noise and with only finitely many samples of the > > signal, I don't think your task is solvable, unless you can supply > > some constraints. > > you need very many samples (multiple periods) to determine the period. > > Wrong. MUSIC can do that in very few samples, depending > on the SNR.No, what I said is correct (and you are saying the same thing): in the presence of noise, the number of samples required for determining the frequencies of the summands depends on the width of the confidence intervals and the SNR. In the examples I gave and that you snipped it is clear why there are many samples required. Regards, Andor The reason is that MUSIC uses certain facts> about signal covariance matrices and match them up with > the analytic expressions for the sinusoidal terms. > > The downside is that MUSIC is totally dependent on this > relation between the covariance matrix and the analtitical > expression. > > The consequence is that if there are more sinusodial > signals present than the covariance matrix can handle, > MUSIC fails. If the signal does not comply to the > analytical sum-of-sines signal model, MUSIC fails. > > But as long as circumstances line up in the MUSIC > direction, it is a good tool that provides results > close to the CRB (I can't find my copy of Kay's 1988 > book right now, but I remeber there was a graph in > ch. 13 which showed that MUSIC has attained the > CRB at an SNR around 15 or 20 dB or so). > > Rune
Reply by ●December 3, 20082008-12-03
On 3 Dez., 12:23, Andor <andor.bari...@gmail.com> wrote:> On 3 Dez., 11:04, Rune Allnor <all...@tele.ntnu.no> wrote: > > > > > > > On 3 Des, 09:45, Andor <andor.bari...@gmail.com> wrote: > > > > Randy Yates wrote: > > > > It seems that the MUSIC algorithm is for estimation of sinusoids. �Is > > > > there an adaptation or other similar algorithm that can be applied to > > > > estimate the fundamental frequencies of a mixture of periodic signals? > > > > Hello Randy > > > > In the presence of noise and with only finitely many samples of the > > > signal, I don't think your task is solvable, unless you can supply > > > some constraints. > > > you need very many samples (multiple periods) to determine the period. > > > Wrong. MUSIC can do that in very few samples, depending > > on the SNR. > > No, what I said is correct (and you are saying the same thing): in the > presence of noise, the number of samples required for determining the > frequencies of the summands depends on the width of the confidence > intervals and the SNR. In the examples I gave and that you snipped it > is clear why there are many samples required.In fact, it just occured to me that the task is not solveable at all in noise. Given any confidence interval for the two frequencies, there will always be two frequencies that lie in the confidence intervals which have irrational periods (thus the sum has no fundamental period). Regards, Andor
Reply by ●December 3, 20082008-12-03
On 3 Des, 12:23, Andor <andor.bari...@gmail.com> wrote:> On 3 Dez., 11:04, Rune Allnor <all...@tele.ntnu.no> wrote: > > > > > > > On 3 Des, 09:45, Andor <andor.bari...@gmail.com> wrote: > > > > Randy Yates wrote: > > > > It seems that the MUSIC algorithm is for estimation of sinusoids. �Is > > > > there an adaptation or other similar algorithm that can be applied to > > > > estimate the fundamental frequencies of a mixture of periodic signals? > > > > Hello Randy > > > > In the presence of noise and with only finitely many samples of the > > > signal, I don't think your task is solvable, unless you can supply > > > some constraints. > > > you need very many samples (multiple periods) to determine the period. > > > Wrong. MUSIC can do that in very few samples, depending > > on the SNR. > > No, what I said is correct (and you are saying the same thing): in the > presence of noise, the number of samples required for determining the > frequencies of the summands depends on the width of the confidence > intervals and the SNR. In the examples I gave and that you snipped it > is clear why there are many samples required.Sorry, I axed your first post too badly: While you are right for general (quasi) periodic signals, you chose an example that doesn't does not support your claim: The sinusoidal is the one quasi-periodic signal where the period can actually be determined with just a few samples. True, stuff like MUSIC only works when the stars align, the pixies have sprinkled some of their dust over your computer after the leperchauns left your garden, but then it actually works. Rune
Reply by ●December 3, 20082008-12-03
On 3 Dez., 12:45, Rune Allnor <all...@tele.ntnu.no> wrote:> On 3 Des, 12:23, Andor <andor.bari...@gmail.com> wrote: > > > > > > > On 3 Dez., 11:04, Rune Allnor <all...@tele.ntnu.no> wrote: > > > > On 3 Des, 09:45, Andor <andor.bari...@gmail.com> wrote: > > > > > Randy Yates wrote: > > > > > It seems that the MUSIC algorithm is for estimation of sinusoids. �Is > > > > > there an adaptation or other similar algorithm that can be applied to > > > > > estimate the fundamental frequencies of a mixture of periodic signals? > > > > > Hello Randy > > > > > In the presence of noise and with only finitely many samples of the > > > > signal, I don't think your task is solvable, unless you can supply > > > > some constraints. > > > > you need very many samples (multiple periods) to determine the period. > > > > Wrong. MUSIC can do that in very few samples, depending > > > on the SNR. > > > No, what I said is correct (and you are saying the same thing): in the > > presence of noise, the number of samples required for determining the > > frequencies of the summands depends on the width of the confidence > > intervals and the SNR. In the examples I gave and that you snipped it > > is clear why there are many samples required. > > Sorry, I axed your first post too badly: While you are > right for general (quasi) periodic signals, you chose > an example that doesn't does not support your claim: > The sinusoidal is the one quasi-periodic signal where the > period can actually be determined with just a few samples.You are forgetting the noise, Rune. Any noise, however small, will not allow to determine the frequencies of two sinusoids accurate enough (with finitely many samples) to exclude the possiblity that there is no fundamental period. This is why I asked Randy if he could supply constraints. If we knew that the frequencies of the sinusoids were selected from a finite set of possible frequencies (eg DTMF tones), then, given some frequency estimation method (MUSIC or any other) and the SNR, we can supply bounds on the number of samples required to determine the fundamental frequency with 1-eps chance for error (the value of eps will give a lower bound on the number of required samples). Regards, Andor
Reply by ●December 3, 20082008-12-03
On 3 Des, 12:54, Andor <andor.bari...@gmail.com> wrote:> On 3 Dez., 12:45, Rune Allnor <all...@tele.ntnu.no> wrote: > > > > > > > On 3 Des, 12:23, Andor <andor.bari...@gmail.com> wrote: > > > > On 3 Dez., 11:04, Rune Allnor <all...@tele.ntnu.no> wrote: > > > > > On 3 Des, 09:45, Andor <andor.bari...@gmail.com> wrote: > > > > > > Randy Yates wrote: > > > > > > It seems that the MUSIC algorithm is for estimation of sinusoids. �Is > > > > > > there an adaptation or other similar algorithm that can be applied to > > > > > > estimate the fundamental frequencies of a mixture of periodic signals? > > > > > > Hello Randy > > > > > > In the presence of noise and with only finitely many samples of the > > > > > signal, I don't think your task is solvable, unless you can supply > > > > > some constraints. > > > > > you need very many samples (multiple periods) to determine the period. > > > > > Wrong. MUSIC can do that in very few samples, depending > > > > on the SNR. > > > > No, what I said is correct (and you are saying the same thing): in the > > > presence of noise, the number of samples required for determining the > > > frequencies of the summands depends on the width of the confidence > > > intervals and the SNR. In the examples I gave and that you snipped it > > > is clear why there are many samples required. > > > Sorry, I axed your first post too badly: While you are > > right for general (quasi) periodic signals, you chose > > an example that doesn't does not support your claim: > > The sinusoidal is the one quasi-periodic signal where the > > period can actually be determined with just a few samples. > > You are forgetting the noise, Rune.No, I'm not.> Any noise, however small, will not > allow to determine the frequencies of two sinusoids accurate enough > (with finitely many samples) to exclude the possiblity that there is > no fundamental period.Now we are moving into hair-splitting. Randy asked about "general periodic" signals. I interpret that as "general signals of quasi-periodic nature". It seems you interpret something else. Rune
Reply by ●December 3, 20082008-12-03
Andor <andor.bariska@gmail.com> writes:> On 3 Dez., 12:45, Rune Allnor <all...@tele.ntnu.no> wrote: >> On 3 Des, 12:23, Andor <andor.bari...@gmail.com> wrote: >> >> >> >> >> >> > On 3 Dez., 11:04, Rune Allnor <all...@tele.ntnu.no> wrote: >> >> > > On 3 Des, 09:45, Andor <andor.bari...@gmail.com> wrote: >> >> > > > Randy Yates wrote: >> > > > > It seems that the MUSIC algorithm is for estimation of sinusoids. �Is >> > > > > there an adaptation or other similar algorithm that can be applied to >> > > > > estimate the fundamental frequencies of a mixture of periodic signals? >> >> > > > Hello Randy >> >> > > > In the presence of noise and with only finitely many samples of the >> > > > signal, I don't think your task is solvable, unless you can supply >> > > > some constraints. >> > > > you need very many samples (multiple periods) to determine the period. >> >> > > Wrong. MUSIC can do that in very few samples, depending >> > > on the SNR. >> >> > No, what I said is correct (and you are saying the same thing): in the >> > presence of noise, the number of samples required for determining the >> > frequencies of the summands depends on the width of the confidence >> > intervals and the SNR. In the examples I gave and that you snipped it >> > is clear why there are many samples required. >> >> Sorry, I axed your first post too badly: While you are >> right for general (quasi) periodic signals, you chose >> an example that doesn't does not support your claim: >> The sinusoidal is the one quasi-periodic signal where the >> period can actually be determined with just a few samples. > > You are forgetting the noise, Rune. Any noise, however small, will not > allow to determine the frequencies of two sinusoids accurate enough > (with finitely many samples) to exclude the possiblity that there is > no fundamental period.I see your point, Andor. Actually, what I'm trying to figure out how to do (as an academic exercise at this point rather than a paying job) is estimate heart rate R_H and respiratory rate R_R from a single microphone signal containing both.> This is why I asked Randy if he could supply constraints. If we knew > that the frequencies of the sinusoids were selected from a finite set > of possible frequencies (eg DTMF tones), then, given some frequency > estimation method (MUSIC or any other) and the SNR, we can supply > bounds on the number of samples required to determine the fundamental > frequency with 1-eps chance for error (the value of eps will give a > lower bound on the number of required samples).Generally R_H > R_R, but not necessarily so. And there's nothing that would prevent R_H = M * R_R, either. Sounds in general to me like MUSIC is a bad approach. Thank you both, Rune/Andor, for your responses and guidance. -- % Randy Yates % "Midnight, on the water... %% Fuquay-Varina, NC % I saw... the ocean's daughter." %%% 919-577-9882 % 'Can't Get It Out Of My Head' %%%% <yates@ieee.org> % *El Dorado*, Electric Light Orchestra http://www.digitalsignallabs.com
