0
$\begingroup$

I have asked this in a previous post, and perhaps the question was not properly posed. I will try again.

I have a square, real, non-symmetric matrix $A$ which satisfies $A + A^T \geq 0$. From $A$, I want to find a low-rank approximation matrix $B$ so that it also satisfies $B + B^T \geq0$.

Will Singular Value Decomposition do the job? I know it would for the symmetric case, but I am not sure I can assume the same for the non-symmetric case.

For the time being, I am trying to see if I can avoid heuristics/etc, and I was hoping that the condition $A + A^T \geq 0$ does help in appying SVD or similar.

Thanks!

$\endgroup$
1
$\begingroup$

By $A+A^T\geq 0$ do you mean the symmetric part $A+A^T$ is positive semidefinite, or do you mean that it is pointwise nonnegative?

If you mean $A+A^T$ is positive semidefinite I the rank truncated SVD will also be positive semidefinite.

The key is that if $A+A^T$ is positive semidefinite then $A$ satisifes: $x^TAx \geq 0$ for all $x$. This is true since for real $A$ and $x$ we have that $x^TAx = (x^TAx)^T = x^TA^Tx$. Therefore, $$x^T(A+A^T)x = x^TAx + x^TA^Tx = 2x^TAx$$

Geometrically, $x^TAx \geq 0$ means that the image of $x$ under $A$, and $x$ have positive inner product. Basically, $Ax$ cannot end up in a direction "too far away" from $x$.

In terms of the SVD this means $v_i^Tu_i \geq 0$ for all $i$. Truncating the SVD will not alter this property.

We can prove this. Indeed, Write the SVD of $A$ as $$ A = U\Sigma V^T = \sum_{i=1}^{n} \sigma_i u_iv_i^T $$

First note that, $$ 0\leq x^TAx = \sum_{i=1}^{n} \sigma_i (x^Tu_i)(v_i^Tx) $$

Since $v_i$ is orthogonal to $v_j$ when $i\neq j$, $$ 0\leq v_i^TAv_i = \sigma_i (v_i^Tu_i)(v_i^Tv_i) $$

Write $y$ as a linear combination of $v_i$, $y=\sum_i c_iv_i$. Then, since $|c_i|^2 \geq 0$, $$ y^T(\sigma_i u_iv_i^T)y = \sigma_i |c_i|^2 (v_i^Tu_t)(v_i^Tv_i) \geq 0 $$

Therefore the rank $r$ truncation $B$ also satisifes $x^TBx \geq 0$.

$\endgroup$
  • $\begingroup$ Hi Tyler, Thanks a lot for your answer! Yes, I meant $A+A^T$ is positive-semidefinite. I am sorry, but I cannot follow your proof from "Since $v_i$ is orthogonal to $v_j$..." Perhaps I am missing some steps? Or I don't understand some indexes... Thanks in advance for your clarification. $\endgroup$ – Ernest Sep 18 '18 at 16:19
  • $\begingroup$ One of the properties of the SVD is that the columns of $V$ are orthonormal. I'm denoting the $j$th column of $V$ by $v_j$. $\endgroup$ – tch Sep 18 '18 at 22:41
  • $\begingroup$ Ah, I see. So, if I understand, with this you are proving that the rank-truncated $B$ will satisfy $x^T B x \geq 0$. And then, from $x^T B x \geq 0$ you deduce that $B + B^T \geq 0$, right? $\endgroup$ – Ernest Sep 18 '18 at 23:03

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.