Anyway to find the complexity of the ESPRIT Algorithm in Spectralanalysis ?

Hi ,
I was wondering if someone did this before and tried to measure the complexity of ESPRIT Algo for spectral estimation in relation to the parameters we need to know like ( m , number of samples and so on ) ... 

Thanks

>Hi ,
>I was wondering if someone did this before and tried to measure the
complexity of ESPRIT Algo for spectral estimation in relation to the
parameters we need to know like ( m , number of samples and so on ) ... 
>
>Thanks
>
>
>
Hi, 

Try to make a list with all the steps of the ESPRIT algorithm (including
the computational complexity for each step).  Usually, a computational
complexity is measured based on the number of multiplications performed in
the solution. For example,

ESPRIT ALGORITHM:

Note: the dot symbol is matrix multiplication and the apostrophe is
transpose. 

FOR EACH TIME t=nTs, n=0,1,2,...,N-1, 
 
1) Computing the Covariance matrix Rxx. In matrix form, Rxx=x.x'. Because
the signal arriving to the subarrays is x=[x1(t) x2(t)] (a matrix of Mx2),
this operations takes 2M^2 real multiplications (at a fixed time t). M is
the number of sensors of each subarray.

END 
The first step is of complexity 2NM^2.

2) Eigendecomposition of Rxx is Rxx.E' = E.D (where E is a matrix
containing the eigenvectors of Rxx, and is D is a diagonal matrix
containing the eigenvalues of Rxx). You must compute the number of
multiplications required to compute the eigenvalues; the same for
eigenvectors, and for the decomposition Rxx.E = E.D. 

For example,
Let consider that Rxx is an MxM matrix,E is an NxM matrix, and D is an MxM
matrix.
The computation of the eigenvalues is the solution of            
det(lambda.I-Rxx)=0, is something like M^2 + M (verify).

Now compute the number of multiplications required to compute the
eigenvalues (may be M^2) and for the multiplication E.D (this is M^2
multiplications).

3) Obtain the signal subspace estimate by choosing the first L eigenvalues
corresponding to the L sources of signals.
       
4) Compute the eigendecomposition of the 2L 2L matrix. 

5) and so on...

Usually, the eigendecomposition of the matrices in ESPRIT algorithm (from
step 4) imply a computational complexity O(L^3).

Finally, sum all the complexities computed in all steps and this is your
computational complexity.  

On Dec 5, 2:37&#4294967295;pm, "mdejesus" <eemdejesus@n_o_s_p_a_m.gmail.com>
wrote:

> Usually, the eigendecomposition of the matrices in ESPRIT algorithm (from
> step 4) imply a computational complexity O(L^3).

Could you substantiate this claim?

The EVD algorithms I am aware of, are iterative: They start out
with some guesstimates for the eigenvalue / eigenvector pairs,
and iteratively improve on these estimates until convergence
has been reached. Or not.

Which causes two problems in the complexity analysis:

1) One can not tell in advance how many iterations are
   needed to compute the EVD.
2) One might have to switch between EVD algorithms if the
   first attempt does not converge.

All in all, one can not come up with a meaningful answer
to the question.

Rune

ulayi wrote:

>I was wondering if someone did this before and tried to measure the complexity >of ESPRIT Algo for spectral estimation in relation to the parameters we need to >know like ( m , number of samples and so on ) ...

I think it depends on how it's done.  See the following, for example:

http://www.cs.umd.edu/~oleary/reprints/j40.pdf

Or an earlier paper:

http://drum.lib.umd.edu/bitstream/1903/5235/1/TR_92-54.pdf

Kevin McGee

>On Dec 5, 2:37=A0pm, "mdejesus" <eemdejesus@n_o_s_p_a_m.gmail.com>
>wrote:
>
>> Usually, the eigendecomposition of the matrices in ESPRIT algorithm
(from
>> step 4) imply a computational complexity O(L^3).
>
>Could you substantiate this claim?
>
>The EVD algorithms I am aware of, are iterative: They start out
>with some guesstimates for the eigenvalue / eigenvector pairs,
>and iteratively improve on these estimates until convergence
>has been reached. Or not.
>
>Which causes two problems in the complexity analysis:
>
>1) One can not tell in advance how many iterations are
>   needed to compute the EVD.
>2) One might have to switch between EVD algorithms if the
>   first attempt does not converge.
>
>All in all, one can not come up with a meaningful answer
>to the question.
>
>Rune
>

Hi Rune,

In my claim of

>Usually, the eigendecomposition of the matrices in ESPRIT algorithm (from
>step 4) imply a computational complexity O(L^3).

I mean, to update the eigenvalues/eigenvector estimates in each iteration
the complexity is of order O(M^3) (being M the number of sensors).  

You are right about the fact that the number of iterations is unknown.
However, if you have n iterations, then the complexity of the SVD is
something like O(nM^3) (complexity of order three).

Thank you for the observation,
Miguel

>ulayi wrote:
>
>>I was wondering if someone did this before and tried to measure the
complexity >of ESPRIT Algo for spectral estimation in relation to the
parameters we need to >know like ( m , number of samples and so on ) ...
>
>I think it depends on how it's done.  See the following, for example:
>
>http://www.cs.umd.edu/~oleary/reprints/j40.pdf
>
>Or an earlier paper:
>
>http://drum.lib.umd.edu/bitstream/1903/5235/1/TR_92-54.pdf
>
>Kevin McGee
>

Hi Ulayi,

What a coincidence!!! I read the same reference
(http://www.cs.umd.edu/~oleary/reprints/j40.pdf) some years ago when I was
working on DOA.

For your info, Oleary published a textbook (some years ago), which include
a CD with Matlab codes for ESPRIT and MUSIC. I don't remember the name of
the book. 
 
>I think it depends on how it's done.

That's right.  There multiple solutions to the implementation of ESPRIT. 
For example, there are implementations based on URV decomposition instead
of SVD.  In this case, the decomposition is reduced to O(M^2) (O(M) for a
linear array of M sensors).  

On Dec 7, 4:34&#4294967295;am, "mdejesus" <eemdejesus@n_o_s_p_a_m.gmail.com>
wrote:
> >On Dec 5, 2:37=A0pm, "mdejesus" <eemdejesus@n_o_s_p_a_m.gmail.com>
> >wrote:
>
> >> Usually, the eigendecomposition of the matrices in ESPRIT algorithm
> (from
> >> step 4) imply a computational complexity O(L^3).
>
> >Could you substantiate this claim?
>
> >The EVD algorithms I am aware of, are iterative: They start out
> >with some guesstimates for the eigenvalue / eigenvector pairs,
> >and iteratively improve on these estimates until convergence
> >has been reached. Or not.
>
> >Which causes two problems in the complexity analysis:
>
> >1) One can not tell in advance how many iterations are
> > &#4294967295; needed to compute the EVD.
> >2) One might have to switch between EVD algorithms if the
> > &#4294967295; first attempt does not converge.
>
> >All in all, one can not come up with a meaningful answer
> >to the question.
>
> >Rune
>
> Hi Rune,
>
> In my claim of
>
> >Usually, the eigendecomposition of the matrices in ESPRIT algorithm (from
> >step 4) imply a computational complexity O(L^3).
>
> I mean, to update the eigenvalues/eigenvector estimates in each iteration
> the complexity is of order O(M^3) (being M the number of sensors). &#4294967295;
>
> You are right about the fact that the number of iterations is unknown.
> However, if you have n iterations, then the complexity of the SVD is
> something like O(nM^3) (complexity of order three).

Well, yes. My point is that complexity analyses usually
are used to evaluate the computational workload. If one
can't come up with a closed-form expression where all
factors are known, the evaluation becomes meaningless.

Rune

HI ,
Thanks for the complete explanation :-) 
Can you please help me with the computational complexity for the Esprit algorithm stated here : 
http://www2.ece.ohio-state.edu/~randy/SAtext/sm-slides-1ed.pdf

Thank you 

http://www2.ece.ohio-state.edu/~randy/SAtext/sm-slides-2ed-ver0.9.pdf

On Dec 7, 11:14&#4294967295;pm, ulayi <u...@compgroups.net/> wrote:
> HI ,
> Thanks for the complete explanation :-)
> Can you please help me with the computational complexity for the Esprit algorithm stated here :http://www2.ece.ohio-state.edu/~randy/SAtext/sm-slides-1ed.pdf

Did you understand a single word of what I said?
Your question is meaningless.

Rune