On solution of a class of discrete-time Lyapunov equation

Hello members, let's consider the following equation $$X=F_{1}XF_{1}^{T}+...+F_{p}XF_{p}^{T}+C$$ where $p$ is an positive integer and $C$ is a known positive semidefinite matrix. If we augment $F=[F_{1}...F_{p}]$ and $Y=diag (X...X)$, then the equation becomes $$FYF^{T}−[I...0]Y[I...0]^{T}+C=0$$ seems like a generalized Lyapunov equation. However, there is a constraint on $Y$ for its diagonal form. How to compute $X$?

I met with this problem for dealing with stability analysis for dynamic systems with multiple multiplicative noise.

A trivial way (not necessarily the one you'd use, unless the matrices were very large) to solve this problem is to rewrite it using Kronecker product notation. We use the observation

\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*}

You can try solving this linear system using any standard method, taking care to implement the matrix-vector product to take advantage of the Kronecker product structure.

• Thanks. Dr. S. Sra for your kind help. Indeed, we have thought of the vectorization method. But we still have a question that does the solution obtained by vectorization method has a 'clear' or the 'same' meaning as the original one. For example, the original solution means a covariance of some statistical variables, but when we use the vectorization method, we may collect up the vectors to build a 'suitable' solution, does this solution still means the covariance? – eolithr May 8 '13 at 12:04
• Ah, so you are asking whether $\text{mat}(x)$ will be positive semidefinite? Well, if the original linear system has a unique solution that is guaranteed to be semidefinite, then by solving the vectorized linear system, we should end up recovering that. It remains to determine conditions under which the original system has a semidefinite solution. The above system seems to me to be a well-studied problem; hopefully, F. Poloni (on MO) takes a look and provides some more details, as I think he knows more about these things. – Suvrit May 8 '13 at 17:59
• Also note that if $\|\sum_i F_i \kron F_i\| < 1$, then starting from $X_0=I$, you can iterate $X_{k+1} = \sum_i F_iX_kF_i^T + C$, and converge to the unique semidefinite solution. If the operators don't satisfy this sufficient condition, then more thought is needed. – Suvrit May 8 '13 at 19:41