estimation of autocorrelation matrix or eigenvalue spread.

Hi everyone,
I am experimenting with some equalization schemes and to judge the
performance, I need to estimate the eigenvalue spread of the input to
the equalizer. Currently I am working with a single input stream of
many thousands of samples, and I am assuming that my data is more or
less uniformly distributed. To get the eigenvalues, I generate
 R = Sum( x[k]*x[k]T) where x[k] is a vector of length N at time k of
input stream, x[k]T is the transpose of said vector,  and k changes
over the data stream. Then I generate the eigenvalues of R or mainly
the ratio of max eig(R) to min eig(R). Does this make sense ? Any
other way(s) to estimate the eigenvalue spread of the input data?

Thanks.

mk wrote:
> Hi everyone,
> I am experimenting with some equalization schemes and to judge the
> performance, I need to estimate the eigenvalue spread of the input to
> the equalizer. Currently I am working with a single input stream of
> many thousands of samples, and I am assuming that my data is more or
> less uniformly distributed. To get the eigenvalues, I generate
>  R = Sum( x[k]*x[k]T) where x[k] is a vector of length N at time k of
> input stream, x[k]T is the transpose of said vector,  and k changes
> over the data stream.

What's the limits of the summation?

> Then I generate the eigenvalues of R or mainly
> the ratio of max eig(R) to min eig(R). Does this make sense ?

Eh... what do you mean? It is usually a good idea to actually compute
the parameters one wants to analyse. But maybe that's not what you
meant to ask?

> Any
> other way(s) to estimate the eigenvalue spread of the input data?

You have to estimate eigenvalues to be able to analyze
eigenvalues. As you may have seen already, computing
eigenvalues is not the cheapest of tasks, computationally
speaking, so there are a couple of ways to proceed:

- Are there particularly fast ways of computing what one needs?
- Can the same information be obtained by other strategies?

If you use something like matlab to compute the eigenvalues,
there is a huge overhead in those routines, since they need
both to be able to handle the general case, and the compute
everything, like all the eigenvalues and all the corresponding
eigenvectors.

You only need the largest and smallest eigenvalues of a
symmetric(?) matrix.

As far as I remember, there are particular recipes for those
very tasks in the book by Golub and van Loan. The algorithm
only computes what is necessary to get the job done, thus
saving lots of flops. The downside is that you have to implement
it yourself.

The other question was whether you can achieve the same
goals with other means than eigenvalues. You could try to
compute the AR(P) model for some fixed P and estimate
the ration between the geometric and arithmetic means
of the magnitudes of the zeros.

If you use matlab, the downside is that matlab solves for
roots of polynomials by expressing the polynomial as a
matrix and search for the eigenvalues of that matrix.
Which means it's a more computationally demanding task
than the "expensive" scheme above. So you'll have to
implement your own root solver...

Rune

Hello everybody,

                           I am currently intented to work on Seismic
signals. iam new to seismic signals though have some exposure to
Digital signal processing.
                         iam awaiting suggestion

       Thanks in advance

Arul

Arul wrote:
> Hello everybody,
>
>                            I am currently intented to work on Seismic
> signals. iam new to seismic signals though have some exposure to
> Digital signal processing.
>                          iam awaiting suggestion

I suggest you ask a question.

Regards,
Andor

Rune Allnor wrote:
...
> The other question was whether you can achieve the same
> goals with other means than eigenvalues. You could try to
> compute the AR(P) model for some fixed P and estimate
> the ration between the geometric and arithmetic means
> of the magnitudes of the zeros.

Interesting. Why the ratio of the geometric and arithmetic means of the
magnitudes? I would have guessed that an estimate for the eigenspread
of the signal is the square of the ratio of the max and the min of the
magnitudes of the zeros of the prediction polynomial.

As the eigenspread of a signal is more or less equal to the condition
number of the autocorrelation matrix, any condition number estimate
will do.

>
> If you use matlab, the downside is that matlab solves for
> roots of polynomials by expressing the polynomial as a
> matrix and search for the eigenvalues of that matrix.
> Which means it's a more computationally demanding task
> than the "expensive" scheme above. So you'll have to
> implement your own root solver...

To avoid that, I once used the maximum norm condition number of the
autocorrelation matrix to estimate the 2-norm condition number. Worked
quite well, and was cheaper to compute.

Regards,
Andor

Andor wrote:
> Rune Allnor wrote:
> ...
> > The other question was whether you can achieve the same
> > goals with other means than eigenvalues. You could try to
> > compute the AR(P) model for some fixed P and estimate
> > the ration between the geometric and arithmetic means
> > of the magnitudes of the zeros.
>
> Interesting. Why the ratio of the geometric and arithmetic means of the
> magnitudes? I would have guessed that an estimate for the eigenspread
> of the signal is the square of the ratio of the max and the min of the
> magnitudes of the zeros of the prediction polynomial.

First: This has nothing at all to do with the eigenvalues, at least not

in a way I am aware of. It has to do with spectrum flatness. The OP
wanted to evaluate how well the equalizer worked, this is an
alternative
approach that may or may not be a bit cheaper to compute.

If you have a flat spectrum the zeros of the AR predictor tend to
be distributed evenly around the unit circle at fairly similar
magnitudes, say, around 0.5. Both the geometric and arithmetic
means may be fairly low here.

If you have a spectrum with lots of peaks, sone zeros are close to
the unit circle in order to cancel those peaks. The ratio between
the arithmetic and geometric means is nonlinear, and capable of
picking up that difference, even if there is only one or two poles that

have moved.

Both the AIC and MDL order estimators for AR models use this
concept. 

Rune

Andor wrote:
> Arul wrote:
>> Hello everybody,
>>
>>                            I am currently intented to work on Seismic
>> signals. iam new to seismic signals though have some exposure to
>> Digital signal processing.
>>                          iam awaiting suggestion
> 
> I suggest you ask a question.

In a new thread with an appropriate subject.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

"Andor" <andor.bariska@gmail.com> writes:

> Arul wrote:
>> Hello everybody,
>>
>>                            I am currently intented to work on Seismic
>> signals. iam new to seismic signals though have some exposure to
>> Digital signal processing.
>>                          iam awaiting suggestion
>
> I suggest you ask a question.

Oh, come now, Andor - you're too intolerant and demanding. Don't you
know this is the new Information Age, where any anonymous, insolent
person must only hint at a question and the whole world will clammer
to answer it?
-- 
%  Randy Yates                  % "So now it's getting late,
%% Fuquay-Varina, NC            %    and those who hesitate
%%% 919-577-9882                %    got no one..."
%%%% <yates@ieee.org>           % 'Waterfall', *Face The Music*, ELO
http://home.earthlink.net/~yatescr

On 10 Aug 2006 22:16:37 -0700, "Rune Allnor" <allnor@tele.ntnu.no>
wrote:

>
>mk wrote:
>> Hi everyone,
>> I am experimenting with some equalization schemes and to judge the
>> performance, I need to estimate the eigenvalue spread of the input to
>> the equalizer. Currently I am working with a single input stream of
>> many thousands of samples, and I am assuming that my data is more or
>> less uniformly distributed. To get the eigenvalues, I generate
>>  R = Sum( x[k]*x[k]T) where x[k] is a vector of length N at time k of
>> input stream, x[k]T is the transpose of said vector,  and k changes
>> over the data stream.
>
>What's the limits of the summation?

I see that I wasn't very clear. In equalization, one deals with a
regressor of some certain size (here it's N, which is the same length
as that of the equalizer taps). So the vector x is of size N and
effectively it's a moving window over the input data stream. At any
point in time I am generating a matrix by calculating x[k] * x[k]T (x
is a column vector so R is NxN in size). Normally R, the
autocorrelation matrix is the expectation of x*xT but I only have one
data stream so I am moving x over this data stream and averaging the
resulting matrix to get an estimated autocorrelation matrix. The
limits of the summation above, which is the first portion of the
averaging process, is all the input data. ie get a slice of input data
of size N, generate x*xT, add to R, increment k which moves the x one
step, repeat.
At the end of this summation, I get calculate the eigenvalues of the
resulting matrix R. As I am mainly interested in the ratio of the
maximum eigenvalue to the minimum eigenvalue, the normalization of the
R is not really necessary. This ratio gives me the eigenvalue spread
of the input stream which is mainly caused by the ISI in the channel
and the higher that value, the more difficult it's for some equalizers
to converge.

>> Any
>> other way(s) to estimate the eigenvalue spread of the input data?
>
>You have to estimate eigenvalues to be able to analyze
>eigenvalues. As you may have seen already, computing
>eigenvalues is not the cheapest of tasks, computationally
>speaking, so there are a couple of ways to proceed:

Actually because the number of taps in the equalizer is rather small
(5 to 15), the computational burden of calculating the eigenvalues of
the autocorrelation matrix is not that high. The main question I am
trying to answer is whether the averaging process I am using to
approximate the expectation is really meaningful or not.

mk wrote:
> On 10 Aug 2006 22:16:37 -0700, "Rune Allnor" <allnor@tele.ntnu.no>
> wrote:
>
> >
> >mk wrote:
> >> Hi everyone,
> >> I am experimenting with some equalization schemes and to judge the
> >> performance, I need to estimate the eigenvalue spread of the input to
> >> the equalizer. Currently I am working with a single input stream of
> >> many thousands of samples, and I am assuming that my data is more or
> >> less uniformly distributed. To get the eigenvalues, I generate
> >>  R = Sum( x[k]*x[k]T) where x[k] is a vector of length N at time k of
> >> input stream, x[k]T is the transpose of said vector,  and k changes
> >> over the data stream.
> >
> >What's the limits of the summation?
>
> I see that I wasn't very clear. In equalization, one deals with a
> regressor of some certain size (here it's N, which is the same length
> as that of the equalizer taps). So the vector x is of size N and
> effectively it's a moving window over the input data stream. At any
> point in time I am generating a matrix by calculating x[k] * x[k]T (x
> is a column vector so R is NxN in size). Normally R, the
> autocorrelation matrix is the expectation of x*xT but I only have one
> data stream so I am moving x over this data stream and averaging the
> resulting matrix to get an estimated autocorrelation matrix. The
> limits of the summation above, which is the first portion of the
> averaging process, is all the input data. ie get a slice of input data
> of size N, generate x*xT, add to R, increment k which moves the x one
> step, repeat.
> At the end of this summation, I get calculate the eigenvalues of the
> resulting matrix R. As I am mainly interested in the ratio of the
> maximum eigenvalue to the minimum eigenvalue, the normalization of the
> R is not really necessary. This ratio gives me the eigenvalue spread
> of the input stream which is mainly caused by the ISI in the channel
> and the higher that value, the more difficult it's for some equalizers
> to converge.
>
> >> Any
> >> other way(s) to estimate the eigenvalue spread of the input data?
> >
> >You have to estimate eigenvalues to be able to analyze
> >eigenvalues. As you may have seen already, computing
> >eigenvalues is not the cheapest of tasks, computationally
> >speaking, so there are a couple of ways to proceed:
>
> Actually because the number of taps in the equalizer is rather small
> (5 to 15), the computational burden of calculating the eigenvalues of
> the autocorrelation matrix is not that high. The main question I am
> trying to answer is whether the averaging process I am using to
> approximate the expectation is really meaningful or not.

Ah. Much clearer. Thanks.

I would be very reluctant to use an covariance accumulator like that.
The first N-length frame totally dominates the structure of R,  the
next
a little less so, and as the number of samples increases the relative
contribution to R from each new sample vanishes.

You can handle this in at least two ways. Each new frame can be
added with a forgetting factor a, 0<a<1,  like

R_{n} = a*x[n]x'[n] + (1-a)R_{n-1}

where x[n] is the N-length subsequence of x that ends at sample n.
This way, the last frame x[n] always make a large contribution to
the covariance matrix.

Or you can use a sliding window covariance estimator like

R_{n} = R_{n-1} + x[n]x'[n] - x[n-M]x'[n-M]

i.e. you add a new frame and remove the contributions from the
M'th oldest frame.

Rune