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:
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
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
Starting from this equation the only thing that I was able to prove, using trivial matrix facts, is that
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
where Pk is the unique stabilizing solution of the following discrete-time algebraic Riccati equation
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
Extensive simulations suggest that this is a valid Lyapunov function. A good deal more is true. If we rewrite () as
where ΔXk=Xk+1Xk, it can be proved that
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?


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

Leave a Comment