# On the solution of a generalized Lyapunov equation

We shall reconsider the following equation $$X=F_{1}XF_{1}^{T}+...+F_{p}XF_{p}^{T}+C$$ where $p$ is a positive integer and $C$ is a known symmetric positive semidefinite matrix.

I met with this problem for dealing with stability analysis for filtering problems with multiple multiplicative noise.

Recall the following property of the Kronecker product \begin{equation*} \text{vec}(AXB) = (B^T \otimes A)\text{vec}(X), \end{equation*} where the $\text{vec}(\cdot)$ stacks columns of $X$ into one long vector.

Defining now $x := \text{vec}(X)$ and $c = \text{vec}(C)$, with the above observation the original equation can be written as the following large (but highly structured) linear system:

\begin{equation*} \left(\sum\nolimits_i F_i \otimes F_i - (I \otimes I)\right)x = c. \end{equation*}

In a special case, for $i=1$, the equation reduces to the normal discrete-time Lyapunov equation, and if $F$ is stable, the solution will be symmetric positive semidefinite, i.e. $$X=F_{1}XF_{1}^{T}+C$$ with $X=\sum\nolimits_{j}^{\infty}F_{1}^{j}C(F_{1}^{T})^{j}$

My question is that, given a symmetric positive semidefinite matrix $C$, under what conditions can we find a symmetric positive semidefinite solution $X$?

• It is unusual (and frowned upon) to thank other users in questions on this site, so I have removed a couple of sentences from your post. Back to business now: you say that it is 'clear' that $X$ is positive definite under those conditions; based on what exactly? The usual criterion for positive-definiteness in the Lyapunov case ($B=A^T$, one term) is that all the eigenvalues of $A$ have negative real part, which seem different from (and contradicting with) with your proposed one. – Federico Poloni Aug 5 '14 at 8:39
• Yep, you are right. I have edited moments ago. The condition I gave may not be correct. But the usual criterion you raised is for continuous case not for discrete one. The discrete form is the eigenvalues of $A$ fall into the unit circle. – Dude-Ray Aug 5 '14 at 9:38
• @FedericoPoloni: thank you. meta.mathoverflow.net/questions/410/… – Joris Bierkens Aug 5 '14 at 9:46
• Ok, buddies, let's focus on the problem. I remembered that last year, Dr. Suvrit proposed a iterative method, i.e. "if ∥∑iFi\kronFi∥<1, then starting from X0=I, you can iterate Xk+1=∑iFiXkFTi+C, and converge to the unique semidefinite solution. If the operators don't satisfy this sufficient condition, then more thought is needed" – Dude-Ray Aug 5 '14 at 9:50
• @JorisBierkens I did not know of this discussion, thanks for pointing it out. On the other hand, I find your sarcastic "thank you" slightly out of line; a simple link would have been sufficient. – Federico Poloni Aug 5 '14 at 11:58

## 1 Answer

In a paper of me of a few years ago, Estimate on the Pathwise Lyapunov Exponent of Linear Stochastic Differential Equations with Constant Coefficients, Theorem 3.6 gives sufficient conditions. The proof is indeed by iteration, but of the continuous time Lyapunov equation, which I found gave better results in the case I was interested in.

These sufficient conditions are, in terms of your notation: $\sum_{i=1}^p ||F_i||^2 < 1$, which looks very similar to the condition you state but is perhaps more restrictive. Unfortunately at the moment I am not too fluent in Kronecker products, so I find it difficult to compare.

• For the record, $\|F_i\otimes F_i\|=\|F_i\|^2$, so this should coincide with the bound mentioned in the comments. – Federico Poloni Aug 5 '14 at 12:02
• Nice comments, Bierkens and Poloni. I will think it over. – Dude-Ray Aug 5 '14 at 13:18
• Hi, buddies. I have found a paper named 'The optimal projection equations for reduced-order, discrete-time state estimation for linear systems with multiplicative white noise' which gives the answer for discrete case. But still lack of proofs. I am very interested with the proof methods. – Dude-Ray Aug 6 '14 at 3:01
• @FedericoPoloni: Actually, what you write won't coincide with the bound in the comments (because that bound is stronger, and only after applying the triangle inequality, does it simplify down to this one...) – Suvrit Sep 9 '14 at 19:20
• @Suvrit I agree -- Both the sum-of-norms and the norm-of-sum version are mentioned in the discussion, I must have missed the stronger form when I wrote that comment. – Federico Poloni Sep 10 '14 at 6:42