Suppose $Y$ is a positive semidefinite matrix, i.e., $Y \succeq 0$, one property of such a matrices allows us to use the Gram representation: $Y = V^T V$ with $V \in \mathbb{R}^{n \times n}$. If $v_i$ denotes the $i$-th column of $V$ then how can one write condition $Y \preceq I$ in terms of $v_i$ which $I$ is identity matrix with all diagonal entries equal to $1$?

For instance: $\langle Y, I \rangle = \sum_{i \in N} \| v_i \|^2$.

  • $\begingroup$ Did you post (and delete) the same question yesterday on this site or MO? I remember that someone answered exactly the same question yesterday, and the answer given was that $\pmatrix{I&V^T\\ V&I}\succeq0$. $\endgroup$ – user1551 Oct 19 '13 at 8:10
  • $\begingroup$ But this is not going to work in my case. $\endgroup$ – Royeh Oct 19 '13 at 9:45

$Y\preceq I$ if and only if $x^\ast (I-Y)x\ge0$ for all vector $x$. Since the norm of $x$ does not matter, we may consider only unit vectors and the previous condition is equivalent to $\|Vx\|_2\le1$ for all unit vector $x$, i.e. the operator 2-norm $\|V\|_2$ (i.e. the largest singular value of $V$), is $\le1$.

  • $\begingroup$ So, by using your comment one can have the following, right? $$ \| V \|_2 = \| V \|_F = \sqrt{{\rm trace~} A^T A} = \sqrt{\sum_i \| v_i \|^2} $$ Which the condition will be in the form: $$ Y \preceq I \Rightarrow \sum_i \| v_i \|^2 \leq 1 $$ $\endgroup$ – Royeh Oct 19 '13 at 10:28
  • $\begingroup$ @Saber No. $\|V\|_2=\max_{\|x\|_2=1}\|Vx\|_2=\sigma_1(V)$ is the operator 2-norm, not the Frobenius norm $\|V\|_F$. However, since all norms on a finite-dimensional vector space are equivalent, there exist some constant $C>0$ (that is dependent of $n$ but not $V$) such that $\|V\|_2\le C\|V\|_F$. So, in theory, $\|V\|_F\le\frac1C$ is a sufficient condition for $Y\preceq I$, but this condition is not very useful in practice. $\endgroup$ – user1551 Oct 19 '13 at 10:31
  • $\begingroup$ But I do not need the singular value. I have to have just an constraint which have only $v_i$ as a variable, nothing more!! $\endgroup$ – Royeh Oct 19 '13 at 10:36

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.