On contractive properties of a nonlinear matrix algorithm

I’m stuck in a problem that concerns a nonlinear iterative matrix algorithm.
Although the problem is quite complicated to explain I’ll try to describe it in a simple way, neglecting unnecessary details.

The matrix iteration is the following one:
Xk+1=ππX1/2kG(ejω)Ψ(ejω)G(ejω)XkG(ejω)G(ejω)X1/2kdω2π()
where {Xk} is a sequence of n×n matrices, and G(ejω), Ψ(ejω)=Ψ(ejω) are n×1 and 1×1, respectively, matrix-valued functions analytic on the complex unit circle which satisfies certain conditions so that there exists at least one fixed point of the iterative algorithm (actually a set of fixed points) and ππΨ(ejω)dω2π=1. Furthermore it can be proved that the above iteration maps positive-definite matrices into positive-definite matrices and if we initialize the algorithm using a trace-one matrix the algorithm is trace preserving.

Experimentally, I noticed that the iteration converges to a positive semi-definite matrix for every positive-definite initialization of the algorithm. Moreover, from the simulations, it seems that the iteration is a contraction in the Hilbert (and Thompson) metric. Hence, my hope is that there exists a way to formally prove this contractive property. I recall the the Hilbert metric on the cone of positive definite matrices is defined as
dH(X,Y)=logλmax(Y1/2XY1/2)λmin(Y1/2XY1/2),
where X and Y are positive definite matrices and λmax(), λmin() denote the maximum and minimum eigenvalue, respectively.
By plugging the latter expression into the initial iteration, we get
dH(Xk+1,Xk)=logλmax(ππG(ejω)Ψ(ejω)G(ejω)XkG(ejω)G(ejω)dω2π)λmin(ππG(ejω)Ψ(ejω)G(ejω)XkG(ejω)G(ejω)dω2π).
Starting from this equation the only thing that I was able to prove, using trivial matrix facts, is that
dH(Xk+1,Xk)2dH(Xk,Xk1)
but clearly this bound is not useful at all.

I’m sorry for the fuzziness of my question, but I have no ideas about how to tackle this problem. Every suggestion or comment is highly appreciated. Thank you.

EDIT. Some further considerations. Assuming that Ψ(ejω)=1 for all ω[π,π) and G(ejω)=(ejωInA)1B where A is n×n Schur stable (i.e. spectrum lies inside the unit circle) and B is n×1 and such that the pair (A,B) is controllable, the above iteration can be written as a Lyapunov-like matrix equation
Xk+1=X1/2kZkX1/2kXk+1X1/2kZkX1/2k+X1/2kBBBPkBX1/2k,
where Pk is the unique stabilizing solution of the following discrete-time algebraic Riccati equation
Π=AΠAAΠB(BΠB)1BΠA+Xk
and Zk:=AB(BPkB)1BPkA is Schur stable.

Now it remains to prove that the above matrix equation converges to a positive semi-definite matrix for every positive definite initialization.

EDIT #2. Additional remarks. Another way to prove convergence is to find a suitable Lyapunov function and prove that this function is decreasing along the trajectories generated by the iteration. Consider the candidate Lyapunov function
L(X)=trace(X)ππΨ(ejω)logG(ejω)XG(ejω)dω2π.
Extensive simulations suggest that this is a valid Lyapunov function. A good deal more is true. If we rewrite () as
Xk+1=Xk+ΔXk
where ΔXk=Xk+1Xk, it can be proved that
L(Xk),ΔXk=trace(L(Xk)ΔXk)0,
i.e. the iteration () can be seen as a gradient descent algorithm with fixed step size equal to 1. Obviously, this is not sufficient to prove convergence, but can it be useful somehow?

Answer

Attribution
Source : Link , Question Author : Ludwig , Answer Author : Community

Leave a Comment