Forums

estimation of autocorrelation matrix or eigenvalue spread.

Started by mk August 10, 2006
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