6
$\begingroup$

Question: Given the long and skinny matrix $A\in\mathbb{R}^{m\times n}$ with $m\ge n$, define the matrix valued operator

$$\mathcal{A}:X\mapsto AX^{T}+XA^{T}.$$

What is the tightest nontrivial lower-bound on the singular value

$$\sigma_{\min}(\mathcal{A})\triangleq\min_{X}\{\|\mathcal{A}(X)\|_{F}:\|X\|_{F}=1\},$$

where $\|X\|_{F}^{2}=\mathrm{trace}(X^{T}X)$ is the usual matrix Euclidean norm (i.e. Frobenius norm)?

Remark 1. In the case that $A=a$ is a vector (i.e. with $n=1$), it is easy to show that $\sigma_{\min}(\mathcal{A})=\sqrt{2}\|a\|$, since $\|ax^{T}+xa^{T}\|^{2}=2\|a\|^{2}\|x\|^{2}+2(a^{T}x)^{2}$, and the term $(a^{T}x)^{2}$ is obviously nonnegative. However in the general matrix case, we have $\|AX^{T}+XA^{T}\|^{2}=2\|AX^{T}\|_{F}^{2}+2\mathrm{trace}[(A^{T}X)^{2}]$, and it appears possible for $\mathrm{trace}[(A^{T}X)^{2}]$ to be negative.

Remark 2. In the case that $A$ is square and that $X$ is forced to be symmetric, this problem is closely related to the smallest singular value of the Lyapunov operator $A\otimes I+I\otimes A$, which is known to be related (in a fairly complicated way) to the singular values of $P$, where $P$ solves $AP+PA^{T}=I$.

Edit 1. Federico Poloni remarked that the rectangular case should not be easier than the square one. Agreed. In this case, consider where $n$ is very small, say 1 or 2, or at least $n\ll m/2,$ so that $\mathcal{A}(X)$ can be considered low-rank. As mentioned above, the $n=1$ case has an exact solution. Can tight bounds be derived for $n$ small?

$\endgroup$
  • $\begingroup$ What do you mean by $\parallel \;. \;\parallel_F$? $\endgroup$ – Ali Taghavi Aug 24 '17 at 19:16
  • $\begingroup$ It would be strange if the rectangular case were easier than the square one... $\endgroup$ – Federico Poloni Aug 24 '17 at 19:32
  • $\begingroup$ Is X the same size as A? $\endgroup$ – Min-Oo Aug 24 '17 at 19:42
  • 1
    $\begingroup$ @AliTaghavi I mean the Frobenius norm. I've edited the question accordingly. $\endgroup$ – Richard Zhang Aug 24 '17 at 20:37
  • 1
    $\begingroup$ @AliTaghavi, you're absolutely right. The square case is not interesting. Instead, consider the long-and-skinny case $n\ll m$. Where $n=1$, the minimum is certainly not zero. $\endgroup$ – Richard Zhang Aug 24 '17 at 20:48
4
$\begingroup$

There is always a zero singular value as soon as $n \geq 2$.

Write $A = UD V$ with $D$ diagonal and $U, V$ orthogonal. Then we can write $X \mapsto AX^T + X A^T$ as $$X \mapsto UDV X^T + X V^T D^T U^T = U(D (U^T X V^T)^T + (U^T X V^T) D^T ) U^T$$ i.e. the composition of the operation $X \mapsto D X^T + X D^T$ with two orthogonal operatorions. So we may assume $A=D$ is diagonal

By performing singular value decomposition on $A$, we may assume that $A$ is diagonal. Say the first two entries are $\lambda_1,\lambda_2$. Then $\begin{pmatrix} 0 & -\lambda_1 \\ \lambda_2 & 0 \end{pmatrix}$, padded with zero entries, is sent to zero.

Of course if $\lambda_1 = \lambda_2=0$, then any $2 \times 2$ matrix is sent to $0$.

The remaining singular values are either $\sqrt{2}$ times a singular value of $A$, the square root of twice the sum of the squares of two different singular values of $X$, or twice a singular value of $A$.

$\endgroup$
  • $\begingroup$ Perfect answer. $\endgroup$ – Richard Zhang Aug 24 '17 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.