1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
.TH levin 1 "April 1993" "Scilab Group" "Scilab Function"
.so ../sci.an
.SH NAME
levin - Toeplitz system solver by Levinson algorithm (multidimensional)
.SH CALLING SEQUENCE
.nf
[la,sig]=levin(n,cov)
.fi
.SH PARAMETERS
.TP 12
n
: maximum order of the filter
.TP
cov
: matrix containing the
.LA $R_k$
(d x d matrices for a
d-dimensional process). It must be given the following way :
.IG
.nf
| R0 |
| R1 |
| R2 |
| . |
| . |
| Rnlag|
.fi
.FI
.LA \[ \vector{ R_0 \\ R_1\\R_2\\\vdots\\R_{nlag}} \]
.TP
la
: list-type variable, giving the successively calculated
Levinson polynomials (degree 1 to n), with coefficients \fVAk\fR
.TP
sig
: list-type variable, giving the successive
mean-square errors.
.SH DESCRIPTION
function which solves recursively on n
the following Toeplitz system (normal equations)
.IG
.nf
|R1 R2 . . . Rn |
|R0 R1 . . . Rn-1|
|R-1 R0 . . . Rn-2|
| . . . . . . |
|I -A1 .. -An| | . . . . . . | = 0
| . . . . . . |
| . . . . . . |
|R2-n R3-n . . . R1 |
|R1-n R2-n . . . R0 |
.fi
.FI
.LA \[ \vector{ I -A_1 \ldots -A_n}
.LA \left( \begin{array}{cccc} R_1 & R_2 & \ldots & R_{n} \\
.LA R_0 & R_1 & \ldots & R_{n-1} \\
.LA R_{-1} & R_0 & \ldots & R_{n-2} \\
.LA \vdots & \vdots & \ldots & \vdots \\
.LA R_{2-n} & R_{3-n} & \ldots & R_{1} \\
.LA R_{1-n} & R_{2-n} & \ldots & R_{0} \\
.LA \end{array} \right) =0 \]
where {\fVRk;k=1,nlag\fR} is the sequence of \fVnlag\fR empirical covariances
.SH AUTHOR
G. Le Vey
.SH EXAMPLE
.nf
//We use the 'levin' macro for solving the normal equations
//on two examples: a one-dimensional and a two-dimensional process.
//We need the covariance sequence of the stochastic process.
//This example may usefully be compared with the results from
//the 'phc' macro (see the corresponding help and example in it)
//
//
//1) A one-dimensional process
// -------------------------
//
//We generate the process defined by two sinusoids (1Hz and 2 Hz)
//in additive Gaussian noise (this is the observed process);
//the simulated process is sampled at 10 Hz (step 0.1 in t, underafter).
//
t1=0:.1:100;rand('normal');
y1=sin(2*%pi*t1)+sin(2*%pi*2*t1);y1=y1+rand(y1);plot(t1,y1);
//
//covariance of y1
//
nlag=128;
c1=corr(y1,nlag);
c1=c1';//c1 needs to be given columnwise (see the section PARAMETERS of this help)
//
//compute the filter for a maximum order of n=10
//la is a list-type variable each element of which
//containing the filters of order ranging from 1 to n; (try varying n)
//in the d-dimensional case this is a matrix polynomial (square, d X d)
//sig gives, the same way, the mean-square error
//
n=15;
[la1,sig1]=levin(n,c1);
//
//verify that the roots of 'la' contain the
//frequency spectrum of the observed process y
//(remember that y is sampled -in our example
//at 10Hz (T=0.1s) so that we need to retrieve
//the original frequencies (1Hz and 2 Hz) through
//the log and correct scaling by the frequency sampling)
//we verify this for each filter order
//
for i=1:n, s1=roots(la1(i));s1=log(s1)/2/%pi/.1;
//
//now we get the estimated poles (sorted, positive ones only !)
//
s1=sort(imag(s1));s1=s1(1:i/2);end;
//
//the last two frequencies are the ones really present in the observed
//process ---> the others are "artifacts" coming from the used model size.
//This is related to the rather difficult problem of order estimation.
//
//2) A 2-dimensional process
// -----------------------
//(4 frequencies 1, 2, 3, and 4 Hz, sampled at 0.1 Hz :
// |y_1| y_1=sin(2*Pi*t)+sin(2*Pi*2*t)+Gaussian noise
// y=| | with :
// |y_2| y_2=sin(2*Pi*3*t)+sin(2*Pi*4*t)+Gaussian noise
//
//
d=2;dt=0.1;
nlag=64;
t2=0:2*%pi*dt:100;
y2=[sin(t2)+sin(2*t2)+rand(t2);sin(3*t2)+sin(4*t2)+rand(t2)];
c2=[];
for j=1:2, for k=1:2, c2=[c2;corr(y2(k,:),y2(j,:),nlag)];end;end;
c2=matrix(c2,2,128);cov=[];
for j=1:64,cov=[cov;c2(:,(j-1)*d+1:j*d)];end;//covar. columnwise
c2=cov;
//
//in the multidimensional case, we have to compute the
//roots of the determinant of the matrix polynomial
//(easy in the 2-dimensional case but tricky if d>=3 !).
//We just do that here for the maximum desired
//filter order (n); mp is the matrix polynomial of degree n
//
[la2,sig2]=levin(n,c2);
mp=la2(n);determinant=mp(1,1)*mp(2,2)-mp(1,2)*mp(2,1);
s2=roots(determinant);s2=log(s2)/2/%pi/0.1;//same trick as above for 1D process
s2=sort(imag(s2));s2=s2(1:d*n/2);//just the positive ones !
//
//There the order estimation problem is seen to be much more difficult !
//many artifacts ! The 4 frequencies are in the estimated spectrum
//but beneath many non relevant others.
//
.fi
.SH SEE ALSO
phc
|
