Discussion Groups | Comp.DSP | DOA by MUSIC algorithm

There are 8 messages in this thread.

You are currently looking at messages 1 to .

Is this discussion worth a thumbs up?

0

DOA by MUSIC algorithm - krish_dsp - 2008-08-15 18:45:00

HI everyone,
I am going to do a project on implementation of DOA estimation algorithm
using MUSIC. I have read the literature about MUSIC and about DOA
estimation.
Still I am not able to conceive the idea practically. The input signal to
the array of antennas (say M antennas) is X. (consider a single snap shot)
which is equal to
X = (a(theta) * S) + n

Then we need to find the eigen value of the autocorrelation matrix of X.
There will be M eigen values and M eigen vectors correspondingly.
If the number of directions is D (D < M), then the eigen vectors from D+1
to M represent the noise subsspace.

So the MUSIC spectrum is given by

P(theta) = 1 / (summation from D+1 to M (a(theta) * eigen vectors))^2

This is what I understand from the theoretical stuff I read.
Am i right?

If I write a program in MATLAB using the above logic, will it be right?
Where else can I find some practical examples of MATLAB implementation?
Any help will be of great use to me.

Thank you.

Re: DOA by MUSIC algorithm - Rune Allnor - 2008-08-16 05:57:00

On 16 Aug, 00:45, "krish_dsp" <nmkr...@gmail.com> wrote:
> HI everyone,
> I am going to do a project on implementation of DOA estimation algorithm
> using MUSIC. I have read the literature about MUSIC and about DOA
> estimation.
> Still I am not able to conceive the idea practically. The input signal to
> the array of antennas (say M antennas) is X. (consider a single snap shot)
> which is equal to
> X = (a(theta) * S) + n

I suppose S is the steering vector and a(theta) is the amplitude
vector...

> Then we need to find the eigen value of the autocorrelation matrix of X.
> There will be M eigen values and M eigen vectors correspondingly.
> If the number of directions is D (D < M), then the eigen vectors from D+1
> to M represent the noise subsspace.

> So the MUSIC spectrum is given by

Wrong. There is a weide-spread misconception that MUSIC
produces a spectrum. It doesn't. The MUSIC algorithm
locates steering vectors that are orthogonal to the
null space of the covariance matrices. If you look
very closely at the computations, no information
whatsoever about energy distribution is carried from
the signal domain to the MUSIC *pseudo* spectrum.

> P(theta) = 1 / (summation from D+1 to M (a(theta) * eigen vectors))^2
>
> This is what I understand from the theoretical stuff I read.
> Am i right?

You didn't define the quantities in your signal model,
so with the proviso that a(theta) is the amplitude vector,
this is wrong.

If a(theta) is the steering vector then the expression
makes sense.

> If I write a program in MATLAB using the above logic, will it be right?
> Where else can I find some practical examples of MATLAB implementation?
> Any help will be of great use to me.

Keep in mind that you need to pay meticulous attention to
detail. Remember, there is no closed-form solutions here, you
need to search for the steering vectors that are orthogonal
to the null space.

Rune

Re: DOA by MUSIC algorithm - Ikaro - 2008-08-16 18:25:00

> > If I write a program in MATLAB using the above logic, will it be right?
> > Where else can I find some practical examples of MATLAB implementation?
> > Any help will be of great use to me.

Here is a simple matlab program that I wrote a while ago that shows an
example of DOA with MUSIC, hope this help...

%clear all;clc;close all
theta=[-90:0.1:90];
N=length(theta);
%Fixed Limitations
d=0.1
%lambda=2*pi/max(w);
%d=c*pi/max(w);
c=1;
MP;
wmax=3*c*pi/d;

w=2;%linspace(1,wmax,100);
W=length(w);
y=zeros(N,W);
z=y;

wk=2;
s=[0.65*exp(j*wk)  exp(j*wk)];
k=2;
doa=[60 -40];

%Limitations
ws=wk*d*sin(pi*doa/180)/c;

if(abs(max(ws))>pi | abs(max(doa))>90)
%break
warning('Aliasing !!')
end

%Model
a=[exp(-j*ws(1)*[0:M-1]') exp(-j*ws(2)*[0:M-1]')];
%x=[s(:,1).*a(:,1) s(:,2).*a(:,2)];
x=a*s' + 0.1*randn(M,1);

%Beamformer response
bf=zeros(N,1);
msc=zeros(N,1);

[trasn,R]=corrmtx(x,length(x)-1,'modified');
[u,s,v]=svd(R);
E=v(:,1+k:end);

for i=1:N

%Steer Beam throught theta
b=exp(-j*(wk*d*sin(pi*theta(i)/180)/c)*[0:M-1]);
bf(i)=b*x/M;
b=b';
msc(i)«s(1/(b'*E*E'*b));

end

figure
plot(theta,log10(abs(bf)))
hold on
plot(theta,log10(msc),'r')
%line([-doa(1) -doa(1)],[0 1.2])
%line([-doa(2) -doa(2)],[0 max(msc)])

Re: DOA by MUSIC algorithm - krish_dsp - 2008-08-19 01:35:00

Thanks everyone...
As u told rune, a(theta) is the steering vector and S is the amplitude.
But i am not able to get what you were referring to...

"Keep in mind that you need to pay meticulous attention to
detail. Remember, there is no closed-form solutions here, you
need to search for the steering vectors that are orthogonal
to the null space."

As I understood, when i project the MUSIC spectrum( not referring to the
actual meaning of the word spectrum) in a graph or check the values I will
get the peak values in correspondence to the DOAs. what do you mean when
you say that i need to 'search' for the steering vectors that are
orthogonal?

I might sound very naieve .pls bear with me. As i read the matrix a(theta)
is a (N X M) matrix where N is the number of antennas in the array and M is
the number of directions of arrivals. How can I search for the steering
vectors that are orthogonal? Can u explain that?
b'cos as I read the literature, the N-M smallest eigen values represent
the eigen vectors that are orthogonal to noise subspace. I thought, till
now that its a striagh forward calculation.

i hope you could understand what i am asking.
thank you.

>> > If I write a program in MATLAB using the above logic, will it be
right?
>> > Where else can I find some practical examples of MATLAB
implementation?
>> > Any help will be of great use to me.
>
>
>Here is a simple matlab program that I wrote a while ago that shows an
>example of DOA with MUSIC, hope this help...
>
>
>%clear all;clc;close all
>theta=[-90:0.1:90];
>N=length(theta);
>%Fixed Limitations
>d=0.1
>%lambda=2*pi/max(w);
>%d=c*pi/max(w);
>c=1;
>MP;
>wmax=3*c*pi/d;
>
>w=2;%linspace(1,wmax,100);
>W=length(w);
>y=zeros(N,W);
>z=y;
>
>wk=2;
>s=[0.65*exp(j*wk)  exp(j*wk)];
>k=2;
>doa=[60 -40];
>
>%Limitations
>ws=wk*d*sin(pi*doa/180)/c;
>
>if(abs(max(ws))>pi | abs(max(doa))>90)
>    %break
>    warning('Aliasing !!')
>end
>
>%Model
>a=[exp(-j*ws(1)*[0:M-1]') exp(-j*ws(2)*[0:M-1]')];
>%x=[s(:,1).*a(:,1) s(:,2).*a(:,2)];
>x=a*s' + 0.1*randn(M,1);
>
>%Beamformer response
>bf=zeros(N,1);
>msc=zeros(N,1);
>
>
>[trasn,R]=corrmtx(x,length(x)-1,'modified');
>[u,s,v]=svd(R);
>E=v(:,1+k:end);
>
>
>for i=1:N
>
>    %Steer Beam throught theta
>    b=exp(-j*(wk*d*sin(pi*theta(i)/180)/c)*[0:M-1]);
>    bf(i)=b*x/M;
>    b=b';
>    msc(i)«s(1/(b'*E*E'*b));
>
>end
>
>figure
>plot(theta,log10(abs(bf)))
>hold on
>plot(theta,log10(msc),'r')
>%line([-doa(1) -doa(1)],[0 1.2])
>%line([-doa(2) -doa(2)],[0 max(msc)])
>

Re: DOA by MUSIC algorithm - Rune Allnor - 2008-08-19 02:09:00

On 19 Aug, 07:35, "krish_dsp" <nmkr...@gmail.com> wrote:
> Thanks everyone...
> As u told rune, a(theta) is the steering vector and S is the amplitude.
> But i am not able to get what you were referring to...
>
> "Keep in mind that you need to pay meticulous attention to
> detail. Remember, there is no closed-form solutions here, you
> need to search for the steering vectors that are orthogonal
> to the null space."
>
> As I understood, when i project the MUSIC spectrum( not referring to the
> actual meaning of the word spectrum) in a graph or check the values I will
> get the peak values in correspondence to the DOAs.

You need to be extremely careful about the details here:
The peaks in the pseudo spectrum will be located at the
wavenumbers wich correspond to the DoAs. But the width
or heights of the peaks will not have any relation to
any relevant property of the signal.

> what do you mean when
> you say that i need to 'search' for the steering vectors that are
> orthogonal?

That's how MUSIC works. The basic recipe goes as

- Estimate the spatial covariance matrix
- Compute the eigen decomposition of the matrix
- Separate the eigenvectors in signal and noise subspaces
- Throw away any info about the signal subspace (i.e signal
power and phase) {*}
- Find the steering vectors that are orthogonal to the basis
vectors for the noise subspace

[*] This step isn't mentioned in any of the published recipes,
but I include it here since you need to look very carefully
for what info is used in subsequent computations to see
that none of the info one would naively expect to be used
actually is used.

> I might sound very naieve .pls bear with me. As i read the matrix a(theta)
> is a (N X M) matrix where N is the number of antennas in the array and M is
> the number of directions of arrivals.

'Antenna' is ambiguous; it might mean one sensor or the whole
array. I'd say that 'the array contains N sensors.'

> How can I search for the steering
> vectors that are orthogonal? Can u explain that?

By brute force.

> b'cos as I read the literature, the N-M smallest eigen values represent
> the eigen vectors that are orthogonal to noise subspace.

No. These vectors span the noise subspace and are orthogonal
to the signal subspace. So the steering vectors towards the
DoAs will be orthogonal to the noise subspace.

> I thought, till
> now that its a striagh forward calculation.

You need to search through all the steering vectors and
see which ones are orthogonal to the noise subspace.
It's straight-forward in one sense, but you can't find
a closed-form solution in th egeneral case.

There are particular variations of MUSIC which work with
uniform linear arrays, which provide 'semi-closed-form'
solutions as roots of polynomials. However, the ROOT MUSIC
recipe is obsolete as other polynomial root schemes exist
which achieve the same goals with prolynomials of about
half the degree of the polynomials which occur in at lest
the naive versions of ROOT MUSIC.

Rune

Re: DOA by MUSIC algorithm - krish_dsp - 2008-08-19 21:20:00

Thank you rune.
I made the mistake in explaining the algorithm. Now I understand what you
were explaining.

>On 19 Aug, 07:35, "krish_dsp" <nmkr...@gmail.com> wrote:
>> Thanks everyone...
>> As u told rune, a(theta) is the steering vector and S is the
amplitude.
>> But i am not able to get what you were referring to...
>>
>> "Keep in mind that you need to pay meticulous attention to
>> detail. Remember, there is no closed-form solutions here, you
>> need to search for the steering vectors that are orthogonal
>> to the null space."
>>
>> As I understood, when i project the MUSIC spectrum( not referring to
the
>> actual meaning of the word spectrum) in a graph or check the values I
will
>> get the peak values in correspondence to the DOAs.
>
>You need to be extremely careful about the details here:
>The peaks in the pseudo spectrum will be located at the
>wavenumbers wich correspond to the DoAs. But the width
>or heights of the peaks will not have any relation to
>any relevant property of the signal.
>
>> what do you mean when
>> you say that i need to 'search' for the steering vectors that are
>> orthogonal?
>
>That's how MUSIC works. The basic recipe goes as
>
>- Estimate the spatial covariance matrix
>- Compute the eigen decomposition of the matrix
>- Separate the eigenvectors in signal and noise subspaces
>- Throw away any info about the signal subspace (i.e signal
>  power and phase) {*}
>- Find the steering vectors that are orthogonal to the basis
>  vectors for the noise subspace
>
>[*] This step isn't mentioned in any of the published recipes,
>    but I include it here since you need to look very carefully
>    for what info is used in subsequent computations to see
>    that none of the info one would naively expect to be used
>    actually is used.
>
>> I might sound very naieve .pls bear with me. As i read the matrix
a(theta)
>> is a (N X M) matrix where N is the number of antennas in the array and
M is
>> the number of directions of arrivals.
>
>'Antenna' is ambiguous; it might mean one sensor or the whole
>array. I'd say that 'the array contains N sensors.'
>
>> How can I search for the steering
>> vectors that are orthogonal? Can u explain that?
>
>By brute force.
>
>> b'cos as I read the literature, the N-M smallest eigen values
represent
>> the eigen vectors that are orthogonal to noise subspace.
>
>No. These vectors span the noise subspace and are orthogonal
>to the signal subspace. So the steering vectors towards the
>DoAs will be orthogonal to the noise subspace.
>
>> I thought, till
>> now that its a striagh forward calculation.
>
>You need to search through all the steering vectors and
>see which ones are orthogonal to the noise subspace.
>It's straight-forward in one sense, but you can't find
>a closed-form solution in th egeneral case.
>
>There are particular variations of MUSIC which work with
>uniform linear arrays, which provide 'semi-closed-form'
>solutions as roots of polynomials. However, the ROOT MUSIC
>recipe is obsolete as other polynomial root schemes exist
>which achieve the same goals with prolynomials of about
>half the degree of the polynomials which occur in at lest
>the naive versions of ROOT MUSIC.
>
>Rune
>

Re: DOA by MUSIC algorithm - krish_dsp - 2008-08-31 13:32:00

Hi..
you have mentioned that there are other root algorithms which are more
efficient than the ROOT-MUSIC. Can you mention the names of them?
Thank you.
bye.
>Thank you rune.
>I made the mistake in explaining the algorithm. Now I understand what
you
>were explaining.
>
>>On 19 Aug, 07:35, "krish_dsp" <nmkr...@gmail.com> wrote:
>>> Thanks everyone...
>>> As u told rune, a(theta) is the steering vector and S is the
>amplitude.
>>> But i am not able to get what you were referring to...
>>>
>>> "Keep in mind that you need to pay meticulous attention to
>>> detail. Remember, there is no closed-form solutions here, you
>>> need to search for the steering vectors that are orthogonal
>>> to the null space."
>>>
>>> As I understood, when i project the MUSIC spectrum( not referring to
>the
>>> actual meaning of the word spectrum) in a graph or check the values I
>will
>>> get the peak values in correspondence to the DOAs.
>>
>>You need to be extremely careful about the details here:
>>The peaks in the pseudo spectrum will be located at the
>>wavenumbers wich correspond to the DoAs. But the width
>>or heights of the peaks will not have any relation to
>>any relevant property of the signal.
>>
>>> what do you mean when
>>> you say that i need to 'search' for the steering vectors that are
>>> orthogonal?
>>
>>That's how MUSIC works. The basic recipe goes as
>>
>>- Estimate the spatial covariance matrix
>>- Compute the eigen decomposition of the matrix
>>- Separate the eigenvectors in signal and noise subspaces
>>- Throw away any info about the signal subspace (i.e signal
>>  power and phase) {*}
>>- Find the steering vectors that are orthogonal to the basis
>>  vectors for the noise subspace
>>
>>[*] This step isn't mentioned in any of the published recipes,
>>    but I include it here since you need to look very carefully
>>    for what info is used in subsequent computations to see
>>    that none of the info one would naively expect to be used
>>    actually is used.
>>
>>> I might sound very naieve .pls bear with me. As i read the matrix
>a(theta)
>>> is a (N X M) matrix where N is the number of antennas in the array
and
>M is
>>> the number of directions of arrivals.
>>
>>'Antenna' is ambiguous; it might mean one sensor or the whole
>>array. I'd say that 'the array contains N sensors.'
>>
>>> How can I search for the steering
>>> vectors that are orthogonal? Can u explain that?
>>
>>By brute force.
>>
>>> b'cos as I read the literature, the N-M smallest eigen values
>represent
>>> the eigen vectors that are orthogonal to noise subspace.
>>
>>No. These vectors span the noise subspace and are orthogonal
>>to the signal subspace. So the steering vectors towards the
>>DoAs will be orthogonal to the noise subspace.
>>
>>> I thought, till
>>> now that its a striagh forward calculation.
>>
>>You need to search through all the steering vectors and
>>see which ones are orthogonal to the noise subspace.
>>It's straight-forward in one sense, but you can't find
>>a closed-form solution in th egeneral case.
>>
>>There are particular variations of MUSIC which work with
>>uniform linear arrays, which provide 'semi-closed-form'
>>solutions as roots of polynomials. However, the ROOT MUSIC
>>recipe is obsolete as other polynomial root schemes exist
>>which achieve the same goals with prolynomials of about
>>half the degree of the polynomials which occur in at lest
>>the naive versions of ROOT MUSIC.
>>
>>Rune
>>
>

Re: DOA by MUSIC algorithm - Rune Allnor - 2008-08-31 14:36:00

On 31 Aug, 19:32, "krish_dsp" <nmkr...@gmail.com> wrote:
> Hi..
> you have mentioned that there are other root algorithms which are more
> efficient than the ROOT-MUSIC. Can you mention the names of them?

I don't know if the algorith has a name as such, but it
was described in a paper by Tufts and Kumaresan in the
Proceedings of IEEE in (I *think*) September 1982.

Rune