# MUSIC Algorithm: Suitable for General Periodic Signals?

Started by December 2, 2008
```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?
--
%% 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
```
```On 2 Des, 15:54, Randy Yates <ya...@ieee.org> wrote:
> It seems that the MUSIC algorithm is for estimation of sinusoids. &#2013266080;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
```
```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
```
```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. &#2013266080;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
```
```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. &#2013266080;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

```
```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. &#2013266080;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
```
```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. &#2013266080;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.

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
```
```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. &#2013266080;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
```
```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. &#2013266080;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.

"general periodic" signals. I interpret that as "general
signals of quasi-periodic nature". It seems you interpret
something else.

Rune
```
```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. &#2013266080;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.

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
```