Optimization version of the Sylvester equation - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T08:02:57Z http://mathoverflow.net/feeds/question/117263 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/117263/optimization-version-of-the-sylvester-equation Optimization version of the Sylvester equation Uday 2012-12-26T15:40:29Z 2012-12-27T11:25:42Z <p>The <a href="http://en.wikipedia.org/wiki/Sylvester_equation" rel="nofollow">Sylvester equation</a> is a matrix equation of the form $AX-XB=C,$ where $A,B,C$ are given matrices of dimension $m\times m,n\times n$ and $m\times n$ and $X$ is an unknown matrix of dimension $m\times n.$ It is a well known fact that the equation has an unique solution if and only if the matrices $A$ and $B$ have disjoint spectrum. If they do not have disjoint spectrum, then the result in general depends on $C.$ </p> <p>While determining perturbation of eigenvalues in certain context I was naturally drawn to the the problem of determining the minimum, $min_{X}||AX-XB-C||,$ where $||.||$ is the <a href="http://en.wikipedia.org/wiki/Matrix_norm#Frobenius_norm" rel="nofollow">Frobenius norm</a>. Clearly, if the spectrum of $A$ and $B$ is disjoint then there is a choice of $X$ for which the norm is zero. Otherwise, we need to resort to certain optimization techniques. One approach could be to vectorize the matrices using Kronecker products and determine the minimum of a linear system. </p> <p>The problem is: "What is the choice of $X$ for which the norm $||AX-XB-C||$ attains minimum (if it exists) when the spectra of $A$ and $B$ are not disjoint?" </p> <p>I have not found any literature on discussion about similar problems. I would be very thankful for any references or suggestions in this direction. </p> http://mathoverflow.net/questions/117263/optimization-version-of-the-sylvester-equation/117265#117265 Answer by Betrand for Optimization version of the Sylvester equation Betrand 2012-12-26T15:53:28Z 2012-12-26T15:53:28Z <p>Instead of minimizing the norm, the following note proposes a conjecture on minimizing the rank of $AX-XB-C$.</p> <p>M. Lin, H. Wimmer, The generalized Sylvester matrix equation, rank minimization and Roth's equivalence theorem , Bull. Aust. Math. Soc. 84 (2011) 441-443. <a href="http://www.math.uwaterloo.ca/~m29lin/LW2011.pdf" rel="nofollow">http://www.math.uwaterloo.ca/~m29lin/LW2011.pdf</a></p> http://mathoverflow.net/questions/117263/optimization-version-of-the-sylvester-equation/117319#117319 Answer by S. Sra for Optimization version of the Sylvester equation S. Sra 2012-12-27T11:25:42Z 2012-12-27T11:25:42Z <p>First recall two basic ideas.</p> <blockquote> <p><strong>Lemma.</strong> Let $A$, $B$, $C$ be arbitrary; then, $\text{vec}(ABC) = (C^T \otimes A)\text{vec}(B)$, where $\otimes$ denotes the Kronecker product and $\text{vec}(\cdot)$ denotes the 'vec' operator that stacks columns of a matrix to obtain a long vector.</p> <p><strong>Notation.</strong> For any matrix $Z$, I will denote by its lowercase version $z$ the vector $\text{vec}(Z)$.</p> </blockquote> <p>Now observe that $\|X\|_F^2 = \text{trace}(X^TX) = x^Tx$. Thus, (also essentially noted by the OP) we may rewrite the optimization problem as</p> <p>\begin{equation*} \min_x \|Hx-c\|^2, \end{equation*} where $H = I \otimes A - B^T \otimes I$.</p> <p>This equation may or may not have a unique solution, but the <strong>unique</strong> least-norm vector $x$ that solves it is given by $x=H^+c$, where $H^+$ is the Moore-Penrose pseudoinverse of $H$. Thus, clearly, the optimization problem <em>has a solution</em>, which answers the question as asked.</p> <p>Of course, due to the numerical expense of computing the above solution (via the truncated SVD of $H$) might be too high. The OP might be interested in consulting the numerical analysis literature on how to deal with such a case.</p>