# Levinson algo. wtih complex coef. required

Started by December 30, 2003
```Hi,

I am desperatly looking for a generalized Levinson algorithm that can
cope with complex autocorrelation values and giving complex filter
coefficients...

I would like to implement it in C, and i have only found the classical
LPC analysis but it can not deal with complex coefficients...

Anyone can help ?

```
```herbert arthur wrote:
>
> Hi,
>
> I am desperatly looking for a generalized Levinson algorithm that can
> cope with complex autocorrelation values and giving complex filter
> coefficients...
>
> I would like to implement it in C, and i have only found the classical
> LPC analysis but it can not deal with complex coefficients...

Off the top of my head, I can't think of any reason why the
algorithm wouldn't work as-is for complex autocorrelation values.
Classical LPC analysis may make assumptions about the sequence
types, but the Levinson algorithm itself is just an iterative one
for computing the inverse of a Toeplitz matrix that relies on the
persymmetry of the matrix and its inverse. This holds whether or
not the matrix is real. Even if the autocorrelation values are
complex, the autocorrelation matrix will still be Toeplitz, no?
Then the algorithm should work just fine with the usual

Glenn Zelniker
```
```Hi,
You're right.. almost :)
If the autocorrelation coefficients are complex, the matrix becomes an
Hermitian one, which is an 'upper class' or Toplietz matrix, i e, all
Toplietz matrices are Hermitians, bute the opposite is not true.
Furthermore, you're right when speaking about the conservation of the
Toplietz properties, but looking at the usual levinson algorithm, i
found that some complex conjugations are to be introduced if one wants
the algorithm to work...
Which calculation terms should be changed ? there, is the question...

H. Arthur

Glenn Zelniker wrote:
> herbert arthur wrote:
>
>>Hi,
>>
>>I am desperatly looking for a generalized Levinson algorithm that can
>>cope with complex autocorrelation values and giving complex filter
>>coefficients...
>>
>>I would like to implement it in C, and i have only found the classical
>>LPC analysis but it can not deal with complex coefficients...
>
>
> Off the top of my head, I can't think of any reason why the
> algorithm wouldn't work as-is for complex autocorrelation values.
> Classical LPC analysis may make assumptions about the sequence
> types, but the Levinson algorithm itself is just an iterative one
> for computing the inverse of a Toeplitz matrix that relies on the
> persymmetry of the matrix and its inverse. This holds whether or
> not the matrix is real. Even if the autocorrelation values are
> complex, the autocorrelation matrix will still be Toeplitz, no?
> Then the algorithm should work just fine with the usual
>
> Glenn Zelniker

```
```
herbert arthur wrote:
>
> Hi,
> You're right.. almost :)
> If the autocorrelation coefficients are complex, the matrix becomes an
> Hermitian one, which is an 'upper class' or Toplietz matrix, i e, all
> Toplietz matrices are Hermitians, bute the opposite is not true.
> Furthermore, you're right when speaking about the conservation of the
> Toplietz properties, but looking at the usual levinson algorithm, i
> found that some complex conjugations are to be introduced if one wants
> the algorithm to work...
> Which calculation terms should be changed ? there, is the question...

On page 865-868 of the third edition of Digital Signal
Processing there is a derivation of Levinson-Durban that,
while I've never studied it in depth, does state at one
point in the derivation that conjugation is required; so
that derivation seems to be generalized to complex matrices.

Bob
--

"Things should be described as simply as possible, but no
simpler."

A. Einstein
```
```Glenn Zelniker <glennz@z-sys.com> wrote in message news:<3FF1A37F.CB0355F3@z-sys.com>...
> herbert arthur wrote:
> >
> > Hi,
> >
> > I am desperatly looking for a generalized Levinson algorithm that can
> > cope with complex autocorrelation values and giving complex filter
> > coefficients...
> >
> > I would like to implement it in C, and i have only found the classical
> > LPC analysis but it can not deal with complex coefficients...
>
> Off the top of my head, I can't think of any reason why the
> algorithm wouldn't work as-is for complex autocorrelation values.
> Classical LPC analysis may make assumptions about the sequence
> types, but the Levinson algorithm itself is just an iterative one
> for computing the inverse of a Toeplitz matrix that relies on the
> persymmetry of the matrix and its inverse. This holds whether or
> not the matrix is real. Even if the autocorrelation values are
> complex, the autocorrelation matrix will still be Toeplitz, no?
> Then the algorithm should work just fine with the usual
>
> Glenn Zelniker

There is a nice recipe in

Therrien: Discrete Random Signals and Statistical Signal Processing,
Prentice-Hall, 1992.

Table 8.2 if my memory serves me correctly.

Rune
```
```
Bob Cain wrote:
>
> On page 865-868 of the third edition of Digital Signal
> Processing

By Proakis and Manolokis.  Sorry.

> there is a derivation of Levinson-Durban that,
> while I've never studied it in depth, does state at one
> point in the derivation that conjugation is required; so
> that derivation seems to be generalized to complex matrices.
>
--

"Things should be described as simply as possible, but no
simpler."

A. Einstein
```
```Bob Cain <arcane@arcanemethods.com> wrote in message news:<3FF257EF.DA197513@arcanemethods.com>...
> Bob Cain wrote:
> >
> > On page 865-868 of the third edition of Digital Signal
> > Processing
>
> By Proakis and Manolokis.  Sorry.
>
> > there is a derivation of Levinson-Durban that,
> > while I've never studied it in depth, does state at one
> > point in the derivation that conjugation is required; so
> > that derivation seems to be generalized to complex matrices.
> >

It appears to be the same as the algorithm Therrien gives.
The predictor coefficents associated with the backwards prediction
are complex conjugated.

Rune
```
```Haykin also has the complex-valued derivation in his "Adaptive Filter Theory" book,

Maurice Givens

allnor@tele.ntnu.no (Rune Allnor) wrote in message news:<f56893ae.0312310513.71b0bcf5@posting.google.com>...
> Bob Cain <arcane@arcanemethods.com> wrote in message news:<3FF257EF.DA197513@arcanemethods.com>...
> > Bob Cain wrote:
> > >
> > > On page 865-868 of the third edition of Digital Signal
> > > Processing
> >
> > By Proakis and Manolokis.  Sorry.
> >
> > > there is a derivation of Levinson-Durban that,
> > > while I've never studied it in depth, does state at one
> > > point in the derivation that conjugation is required; so
> > > that derivation seems to be generalized to complex matrices.
> > >
>
> It appears to be the same as the algorithm Therrien gives.
> The predictor coefficents associated with the backwards prediction
> are complex conjugated.
>
> Rune
```