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⊤(e−jω)XkG(ejω)G⊤(e−jω)X1/2kdω2π(⋆)
where {Xk} is a sequence of n×n matrices, and G(ejω), Ψ(ejω)=Ψ⊤(e−jω) 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(Y−1/2XY−1/2)λmin(Y−1/2XY−1/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⊤(e−jω)XkG(ejω)G⊤(e−jω)dω2π)λmin(∫π−πG(ejω)Ψ(ejω)G⊤(e−jω)XkG(ejω)G⊤(e−jω)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,Xk−1)
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ωIn−A)−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/2kZkX−1/2kXk+1X−1/2kZkX1/2k+X1/2kBB∗B∗PkBX1/2k,
where Pk is the unique stabilizing solution of the following discrete-time algebraic Riccati equation
Π=A∗ΠA−A∗ΠB(B∗ΠB)−1B∗ΠA+Xk
and Zk:=A−B(B∗PkB)−1B∗PkA 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⊤(e−jω)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+1−Xk, 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