# The Kalman Filter for Complex Fibonacci Systems

Authors: John Donoghue
Journal: ISRN Signal Processing
 (2012)

---

## Abstract

This paper investigates the characteristics of the Kalman filter for a broad class of complex Fibonacci systems and represents an extension to the complex domain of the state estimation problem for the real-valued Fibonacci system.  Complex Fibonacci systems are obtained by modifying the real-valued Fibonacci recurrence relation to include complex coefficients, control and noise inputs, and a noisy output-measurement equation.  Analytic expressions for the Kalman filter’s steady-state gain and error covariance matrices are obtained, and it is found that for a broad subclass of these complex systems the elements of the matrices are functions of the golden ratio.


---

## Body

## 1. Introduction

Thenth number F(n) in the real-valued Fibonacci sequence {0,1,1,2,3,5,8,13,…} can be generated either recursively from the recurrence relation (starting with F(0)=0 and F(1)=1)
(1)F(n)=F(n-1)+F(n-2),
or directly using Binet’s formula,(2)F(n)=[φn-(-(1/φ))n]5,
where φ, the golden ratio, is given by φ=(1+5)/2. The Fibonacci numbers and the golden ratio are well known for their number-theoretic properties and for their appearances in natural phenomena and art, and they have also appeared more recently in a state estimation context [1–3]. In [1, 2], connections were made between the Fibonacci numbers, the golden ratio, and properties of the Kalman filter for certain classes of one- and multidimensional systems. In [3], the properties of the filter for the Fibonacci system itself—defined by adding a control input and a noisy measurement equation to the Fibonacci recurrence relation—were also found to involve the Fibonacci numbers and the golden ratio.This paper continues in the vein of [3] and extends the results presented there to a broad class of suitably defined complex Fibonacci systems (which include, as a special case, the real-valued Fibonacci system studied in [3]). Complex systems are obtained by introducing complex coefficients and a noise and control input into the classical Fibonacci recurrence relation (1), along with a noisy measurement equation. The resulting systems’ impulse responses—for different complex coefficients—are different complex-valued Fibonacci sequences. Analytic expressions for the Kalman steady-state gain and a  priori error covariance matrices are developed, and for a broad subclass of these systems it is shown that the elements of these matrices are functions of the golden ratio.While the real-valued Fibonacci sequence is very well known, complex Fibonacci sequences are lesser known, although their number-theoretic properties have been investigated by several authors. Studies of complex sequences generated from the classical recurrence relation (1) either by starting with complex numbers rather than with 0 and 1 or by introducing complex coefficients into the recurrence can be found in [4–8], and studies of the properties of two-dimensional complex sequences can be found in [4–6, 9]. In this paper, the number-theoretic properties of complex sequences are not studied. Rather, by modifying the classical recurrence relation to create complex Fibonacci systems whose impulse responses are complex Fibonacci sequences, the recurrence relations themselves are cast into systems context and the properties of their Kalman filters are investigated.


## 2. Representations of Complex Fibonacci Systems

The complex Fibonacci systems considered here are obtained by modifying the Fibonacci recurrence relation given by (1) to include a control input (a noise input will be added later) and nonunity (and possibly complex) coefficients. Specifically, the systems considered are the second-order discrete-time systems with control input u(n), output d(n), and difference equation (as will be shown below, z1 and z2 are the locations of the system’s poles)(3)d(n)=(z1+z2)d(n-1)-z1z2d(n-2)+u(n-1).
For different choices of z1 and z2, the system’s impulse response (which results when u(n)=δ(n) and there are zero initial conditions, that is, d(-1)=0=d(-2)) will be different Fibonacci sequences. For example, if (z1+z2)=1 and z1z2=-1 (i.e., z1=φ and z2=-(1/φ), where φ is the golden ratio), then the impulse response is the classical, real-valued Fibonacci sequence F(n) defined above; if (z1+z2)=(1+j) (where j=-1) and z1z2=-1, the impulse response is one of the complex Fibonacci sequences whose number-theoretic properties were studied in [8]. A subclass of systems introduced here and which is of particular interest to this work is one whose poles are at z1=φejα and z2=-(1/φ)ejα. These complex (not conjugate) poles are at the same distances from the origin as the poles z1=φ and z2=-(1/φ) of the classical, real-valued Fibonacci system, but lie along the ray that makes an angle α with the real axis. The classical system is the special case of α=0. As shown below, this pair of complex poles gives rise to a subclass of systems whose impulse responses are complex Fibonacci sequences with magnitudes equal to the real-valued Fibonacci numbers but which rotate in the complex plane.The system transfer functionH(z) for the general complex Fibonacci system can be obtained by z-transforming (3) to yield
(4)H(z)=zz2-(z1+z2)z+z1z2=z(z-z1)(z-z2).
Expanding H(z) in partial fractions yields(5)H(z)=1z1-z2(zz-z1-zz-z2)
and since the transfer function H(z) is the z-transform of the impulse response, taking the inverse z-transform of each term in (5) gives(6)h(n)=z1n-z2nz1-z2.
If the poles z1=φ and z2=-(1/φ) for the real-valued Fibonacci system are substituted into this expression, h(n) becomes Binet’s formula given by (2) for calculating the real-valued Fibonacci numbers. If the generalized poles z1=φejα and z2=-(1/φ)ejα for the complex-valued Fibonacci system mentioned above are substituted, h(n) becomes
(7)h(n)=(e-jα5)(φnejnα-(-1φ)nejnα)=(ej(n-1)α5)(φn-(-1φ)n)=F(n)ej(n-1)α,
that is, the impulse response of this system is a complex-valued Fibonacci sequence whose magnitudes are the real-valued Fibonacci numbers and whose angles are (n-1)α.It is assumed in what follows that one pole of the system given by (3) is outside the unit circle and one is inside. The impulse responses of different systems in the class of Fibonacci systems defined by (3) are different versions of Fibonacci sequences, sequences which grow in magnitude, so one of the poles must be unstable. It will be assumed here that |z1|>1.If the states for the system in (3) are defined to be x1(n)=d(n) and x2(n)=d(n-1), and if the system is now further modified to include an excitation noise input w(n) and an output equation with measurement noise v(n), that is, if (3) becomes(8a)d(n)=(z1+z2)d(n-1)-z1z2d(n-2)+u(n-1)+w(n-1),(8b)y(n)=x1(n)+v(n),then a state description for the system is(9a)x(n+1)=Ax(n)+Bu(n)+Gw(n),(9b)y(n)=Cx(n)+v(n),
where
(9c)A=(z1+z2-z1z210),B=(10),G=(10),C=(1,0).


## 3. The Kalman Filter for the Zero-Input-Noise System

The Kalman filter design considered in this section is for the case where the complex Fibonacci system given by (9a), (9b), and (9c) has measurement noise v(n)—assumed to be white with variance σv2—but no excitation noise (i.e., w(n)=0). Letting Kn,Pn-, and Pn+ represent, in turn, the Kalman gain, the a  priori state-estimate error covariance (the error covariance at time n before the measurement y(n) is used), and the a  posteriori state-estimate error covariance (the error covariance after the measurement at n is used), then (following [10, equations (5.19) and (5.26)], [11, Appendix 2.C], and noting that  because the matrix A can now be complex, its conjugate also appears in the Riccati equation) the a  priori error covariance and filter gain are given by (where A*T is the transpose of the complex conjugate of A) (10a)Pn-=APn-1-A*T-APn-1-CT(CPn-1-CT+σv2)-1CPn-1-A*T,n≥2,(10b)Kn=Pn-CT(CPn-CT+σv2)-1,n≥1.If the unknown initial state at n=0 is assumed to have error covariance P0+, then the initial a  priori error covariance at n=1 (to be used in (10a)) is given by P1-=AP0+A*T. It is assumed here that the first measurement is obtained at n=1.The steady-state error covarianceP∞- is the solution to (10a) with both Pn- and Pn-1- replaced by P∞-, and the steady-state gain K∞ follows from (10b). Using the Hamiltonian matrix approach as described in [12, page 203] to solve (10a) results in(11)P∞-=σv2(|z1|2-1)(11z1*1z11|z1|2),K∞=(|z1|2-1|z1|2)(11z1)
(which can be verified most easily by direct substitution into (10a) and (10b)). That these results depend only on the unstable pole z1 is not surprising since as time goes on the system’s response is dominated by that pole. If attention is restricted to any Fibonacci system—real or complex—of the form (3) whose unstable pole z1 is anywhere in the z-plane at a distance φ from the origin, that is, z1=φejα, and z2 is inside the unit circle, then the elements of the steady-state gain and error covariance will be functions of the golden ratio. Specifically, in this case (11) becomes(12)P∞-=σv2(φejαe-jα1φ),K∞=(1φe-jαφ2).
This result is a more general, complex version of a similar result found in [3] for the classical, real-valued Fibonacci system (which results here if α=0), and it makes it clear that for the real-valued system too the matrices depend only on the location of the system’s unstable pole at z1=φ.Finally, if attention is further restricted to the subclass of systems whose poles are complex generalizations of the real pole locations of the real-valued system, and whose impulse responses are given by (7), that is, systems whose poles are z1=φejα and z2=-(1/φ)ejα, then it can be shown that under certain restrictions on the initial a  posteriori error covariance and the measurement noise variance, the elements of the a  priori error covariance are functions of the real-valued Fibonacci numbers. Specifically, if the initial a  posteriori error covariance P0+ is selected to be the identity matrix, and the measurement variance σv2=1, then successive iterations of (10a) show that(13)Pn-=(F(n+2)F(n+1)ejαe-jαF(n)F(n+1)),n≥1,nodd,Pn-=(F(n+1)F(n)ejαe-jαF(n+1)F(n+2)),n≥2,neven,
where F(1)=1,F(2)=1, and F(n), given by (1), is the nth real-valued Fibonacci number. Since limn→∞(F(n+1)/F(n))=φ, it is seen that either expression for Pn- leads to P∞- in the limit. Again, this result is a more general, complex version of a result found in [3] for the real-valued Fibonacci system. This class of complex Fibonacci systems—whose complex poles are at the same distances from the origin as the poles of the real-valued Fibonacci system—is studied in more depth in the next section, where an expression for P∞- is derived for the case of nonzero excitation noise.


## 4. The Kalman Filter for thez1=φejα, z2=-(1/φ)ejα Subclass of Systems with Excitation and Measurement Noise

### 4.1. System Characteristics

The difference equation for this subclass of systems is, from (8a),(14)d(n)=ejαd(n-1)+ej2αd(n-2)+u(n-1)+w(n-1),
where the matrices in its state description are, from (9a), (9b), and (9c),(15)A=(ejαej2α10),B=(10),G=(10),C=(1,0),
and where its impulse response—denoted here asFα(n)—is, from (7),(16)Fα(n)=(ej(n-1)α5)(φn-(-1φ)n)=F(n)ej(n-1)α.
The magnitudes of this complex-valued Fibonacci sequence have the same values as the real-valued sequence, but as n increases they rotate in the complex plane (counterclockwise for α>0, clockwise for α<0). This rotating sequence can be looked upon as the result of sampling a continuous spiral Fα(t) that is readily obtained from (16) by replacing the integer variable n by a real variable t as was done in [13–15] to generalize the real-valued sequence F(n) to a generalized Fibonacci functionF(t). Specifically, if Binet’s formula from (2) is substituted into (16) for F(n), and then n is replaced by t, the resulting generalized Fibonacci function Fα(t) is given as(17)Fα(t)=F(t)ej(t-1)α=(ej(t-1)α5)(φt-(-1φ)t).
While the function F(t) produces the real-valued Fibonacci numbers when t takes on positive integer values, F(t) is, in general, a complex-valued function. A polar plot of the function Fα(t) for α=π/2 and t positive is shown in Figure 1. The magnitudes of the function at the circled points are Fibonacci numbers and correspond to integer values for t ranging from 0 to 7. The function Fα(t) exhibits a spiral shape for both positive and negative values of t and for all values of α except α=0 (for α=0 the complex sequence Fα(n) reduces to the real-valued sequence F(n), and the generalized function F(t) for that case has a sinus-like shape [13–15]). For large positive t, Fα(t) approaches a logarithmic spiral, that is, a spiral whose magnitude at any angle θ is given by r=aebθ, where a and b are arbitrary constants. Specifically, since for large t the generalized function Fα(t)≅(φt/5)ejα(t-1), the angle for a particular t is given as θ=α(t-1) and the magnitude is given as r=(φt/5)=(φ/5)φθ/α. Using the two expressions for r, one can follow [14] and write ln(r)=ln(a)+bθ=ln(φ/5)+(ln(φ)/α)θ, which in turn leads to a=φ/5and b=ln(φ)/α. From (17) it can be seen that the speed with which Fα(t) approaches the logarithmic spiral is the speed with which (1/φt) approaches zero. Finally, it is interesting to note that when α=π/2, the approximating logarithmic spiral is a golden spiral. For this value of α, the complex Fibonacci numbers Fα(n)—which are samples of the spiral Fα(t) at integer values of t—are located alternately on the real and imaginary axes, that is, the spiral Fα(t) goes through a quarter turn from number to number in the sequence. Examination of (16) shows that the ratio of the magnitudes of successive values of Fα(n) is equal to the ratio of successive values of F(n), and so it approaches φ for large n. Thus, for this case where α=π/2, the magnitude of the spiral Fα(t) increases through a quarter turn by a factor of approximately φ, where an increase by a factor of exactly φ in a quarter turn is a characteristic of a golden spiral. The curve shown in Figure 1 is for this case of α=π/2.Figure 1
Polar plot ofFα(t) for α=π/2 and t positive.


### 4.2. The Kalman Filter

In developing the Kalman filter for this subclass of complex Fibonacci systems—the systems given by (15)—it is assumed that the measurement noise v(n) and the excitation noise w(n) are uncorrelated, zero-mean, white noise processes with variances σv2 and σw2, respectively. The Riccati equation for the a  priori error covariance Pn- is the same as (10a) except for an additional term to account for the presence of the excitation noise w(n). Specifically, Pn- now satisfies
(18)Pn-=APn-1-A*T-APn-1-CT(CPn-1-CT+σv2)-1CPn-1-A*T+σw2GGT
and expression (10b) for the gain Kn is unaltered. The steady-state error covariance P∞- is the solution to (18) with both Pn- and Pn-1- replaced by P∞-, and the steady-state gain K∞ follows from (10b). Again using the Hamiltonian matrix approach [12, page 203] to solve (18) results in
(19)P∞-=σv2(σ2+2-q(σ2)ejαe-jα1-q(σ2)),
where σ2=σw2/σv2 and the function q(σ2)=(1/2){(σ2+3)-(σ2+1)(σ2+5)}. That (19) is a solution to (18) is verified most easily by direct substitution and use of the fact that q2-3q+1=σ2q. The function q is real, and it is not difficult to show that 0<q<1. When there is measurement noise but no excitation noise, σ2=0, q(0)=1/φ2, and (19) reduces to (12), as expected. Also, if the system’s A matrix and error covariance matrix are written as A(α) and Pn-(α), respectively (to explicitly show their dependence on the locations of the poles), and if, further, it is noted from (15) that A(-α)=A*(α), where A*(α) is the complex conjugate of A(α), then it follows from conjugating both sides of (18) that Pn-(-α)=(Pn-(α))*. Finally, noting that the limσ2→∞q(σ2)=0, if the excitation noise variance is large relative to the measurement noise variance, then the a  priori error covariance on the first state approaches σw2+2σv2 from below, and the error covariance on the second state approaches σv2, also from below.


## 4.1. System Characteristics

The difference equation for this subclass of systems is, from (8a),(14)d(n)=ejαd(n-1)+ej2αd(n-2)+u(n-1)+w(n-1),
where the matrices in its state description are, from (9a), (9b), and (9c),(15)A=(ejαej2α10),B=(10),G=(10),C=(1,0),
and where its impulse response—denoted here asFα(n)—is, from (7),(16)Fα(n)=(ej(n-1)α5)(φn-(-1φ)n)=F(n)ej(n-1)α.
The magnitudes of this complex-valued Fibonacci sequence have the same values as the real-valued sequence, but as n increases they rotate in the complex plane (counterclockwise for α>0, clockwise for α<0). This rotating sequence can be looked upon as the result of sampling a continuous spiral Fα(t) that is readily obtained from (16) by replacing the integer variable n by a real variable t as was done in [13–15] to generalize the real-valued sequence F(n) to a generalized Fibonacci functionF(t). Specifically, if Binet’s formula from (2) is substituted into (16) for F(n), and then n is replaced by t, the resulting generalized Fibonacci function Fα(t) is given as(17)Fα(t)=F(t)ej(t-1)α=(ej(t-1)α5)(φt-(-1φ)t).
While the function F(t) produces the real-valued Fibonacci numbers when t takes on positive integer values, F(t) is, in general, a complex-valued function. A polar plot of the function Fα(t) for α=π/2 and t positive is shown in Figure 1. The magnitudes of the function at the circled points are Fibonacci numbers and correspond to integer values for t ranging from 0 to 7. The function Fα(t) exhibits a spiral shape for both positive and negative values of t and for all values of α except α=0 (for α=0 the complex sequence Fα(n) reduces to the real-valued sequence F(n), and the generalized function F(t) for that case has a sinus-like shape [13–15]). For large positive t, Fα(t) approaches a logarithmic spiral, that is, a spiral whose magnitude at any angle θ is given by r=aebθ, where a and b are arbitrary constants. Specifically, since for large t the generalized function Fα(t)≅(φt/5)ejα(t-1), the angle for a particular t is given as θ=α(t-1) and the magnitude is given as r=(φt/5)=(φ/5)φθ/α. Using the two expressions for r, one can follow [14] and write ln(r)=ln(a)+bθ=ln(φ/5)+(ln(φ)/α)θ, which in turn leads to a=φ/5and b=ln(φ)/α. From (17) it can be seen that the speed with which Fα(t) approaches the logarithmic spiral is the speed with which (1/φt) approaches zero. Finally, it is interesting to note that when α=π/2, the approximating logarithmic spiral is a golden spiral. For this value of α, the complex Fibonacci numbers Fα(n)—which are samples of the spiral Fα(t) at integer values of t—are located alternately on the real and imaginary axes, that is, the spiral Fα(t) goes through a quarter turn from number to number in the sequence. Examination of (16) shows that the ratio of the magnitudes of successive values of Fα(n) is equal to the ratio of successive values of F(n), and so it approaches φ for large n. Thus, for this case where α=π/2, the magnitude of the spiral Fα(t) increases through a quarter turn by a factor of approximately φ, where an increase by a factor of exactly φ in a quarter turn is a characteristic of a golden spiral. The curve shown in Figure 1 is for this case of α=π/2.Figure 1
Polar plot ofFα(t) for α=π/2 and t positive.


## 4.2. The Kalman Filter

In developing the Kalman filter for this subclass of complex Fibonacci systems—the systems given by (15)—it is assumed that the measurement noise v(n) and the excitation noise w(n) are uncorrelated, zero-mean, white noise processes with variances σv2 and σw2, respectively. The Riccati equation for the a  priori error covariance Pn- is the same as (10a) except for an additional term to account for the presence of the excitation noise w(n). Specifically, Pn- now satisfies
(18)Pn-=APn-1-A*T-APn-1-CT(CPn-1-CT+σv2)-1CPn-1-A*T+σw2GGT
and expression (10b) for the gain Kn is unaltered. The steady-state error covariance P∞- is the solution to (18) with both Pn- and Pn-1- replaced by P∞-, and the steady-state gain K∞ follows from (10b). Again using the Hamiltonian matrix approach [12, page 203] to solve (18) results in
(19)P∞-=σv2(σ2+2-q(σ2)ejαe-jα1-q(σ2)),
where σ2=σw2/σv2 and the function q(σ2)=(1/2){(σ2+3)-(σ2+1)(σ2+5)}. That (19) is a solution to (18) is verified most easily by direct substitution and use of the fact that q2-3q+1=σ2q. The function q is real, and it is not difficult to show that 0<q<1. When there is measurement noise but no excitation noise, σ2=0, q(0)=1/φ2, and (19) reduces to (12), as expected. Also, if the system’s A matrix and error covariance matrix are written as A(α) and Pn-(α), respectively (to explicitly show their dependence on the locations of the poles), and if, further, it is noted from (15) that A(-α)=A*(α), where A*(α) is the complex conjugate of A(α), then it follows from conjugating both sides of (18) that Pn-(-α)=(Pn-(α))*. Finally, noting that the limσ2→∞q(σ2)=0, if the excitation noise variance is large relative to the measurement noise variance, then the a  priori error covariance on the first state approaches σw2+2σv2 from below, and the error covariance on the second state approaches σv2, also from below.


## 5. Summary and Future Work

This paper has determined analytic expressions for the Kalman filter’s steady-state gain anda  priori error covariance matrices for a broad class of suitably defined complex Fibonacci systems. The impulse responses of these systems are complex Fibonacci sequences, and of particular interest to this work was the subclass of systems investigated in Section 4 whose pole locations are complex generalizations of the real pole locations of the classical, real-valued Fibonacci system. The impulse responses of this subclass of systems are Fibonacci sequences that rotate in the complex plane, and which can be viewed as being samples of continuous spirals that are approximately logarithmic. Although the goal in this paper was to study the characteristics of Kalman filters for suitably defined complex Fibonacci systems, and not to study the number-theoretic properties of the Fibonacci sequences which arose as impulse responses of those systems, it would nevertheless be interesting to investigate the properties of the spiral sequence given by (16). It may also be useful to investigate—as was done in [3]—the characteristics of controllers such as LQR and deadbeat controllers for complex Fibonacci systems.



---

*Source: 631873-2012-06-19.xml*