5
$\begingroup$

Consider the following result which I recently came across in a research paper in my area (Signal Processing)

Let $X$ be a $N\times N$ positive semidefinite (psd) matrix whose rank is $r$. Let $A$ be any symmetric $N\times N$ matrix. Then, there exist a set of vectors $x_1,\dots,x_r$ such that \begin{align} X & = \sum_{i=1}^{r}x_ix_i^T \\ x_i^TAx_i &= \frac{\mbox{trace}\{AX\}}{r},~~~\forall i \end{align}

The following is the proof for it which I can't verify.

Proof: Consider the following step-wise procedure whose inputs are $X$ and $A$.

$~~$0.$~~$ Inputs are $X$ (given $X\geq 0$, $rank(X)=r$) and $A$ (symmetric).

  1. Decompose $X=RR^T$.

  2. Generate the eigen decomposition $R^TAR=U\Lambda U^T$.

  3. Let $h$ be any $N\times 1$ vector such that $\lvert h_i\rvert=1$ (each entry of $h$). Generate the vector $x_1$ and matrix $X_1$ as \begin{align} x_1&=\frac{1}{\sqrt{r}}RUh \\ X_1&=X-x_1x_1^T \end{align}

  4. Outputs are $X_1$ and $x_1$.

The paper then claims that

  • $X_1$ is psd and has rank $r-1$
  • $x_1^TAx_1=\frac{1}{r}trace(AX)$

While I am able to verify the second claim, am not able to verify the first one? How is it true? If this can be done, the rest of the proof is straight forward. I am looking for a rigorous proof.

Read this if you are interested to know where this proof heads. Now do the stepwise algorithm earlier with inputs $X_1$ and $A$ to get $x_2$ and $X_2$ such that \begin{align}X_2&=X_1-x_2x_2^T\\&=X-x_1x_1^T-x_2x_2^T\end{align} and $$x_2^TAx_2=\frac{1}{r-1}trace(AX_1)=\frac{1}{r}trace(AX)$$ Then the result of the paper is that you can do this procedure $r$ times and get a rank-one decomposition $$X=\sum_{i=1}^{r}x_ix_i^T$$ with the property $$x_i^TAx_i\,=\,\frac{1}{r}trace(AX),~\forall i$$for any given psd X with rank $r$ and any symmetrix $A$.

$\endgroup$
  • $\begingroup$ Have you tried it for $2x2$ matrices? It may simply be a mistake in the paper. Wouldn't the rank one decomposition of a general positive definite symmetric $2x2$ matrix be essentially unique (the axis of the ellipse)? Then there is no way to get the desired property for arbitrary $A$. $\endgroup$ – Lev Borisov Sep 2 '14 at 14:00
  • $\begingroup$ I am not talking about the SVD based rank one decomposition if that is what you meant. Consider $2\times 2$ matrices, the result states that you can always find two vectors $x_1$ and $x_2$ such that $X=x_1x_1^T+x_2x_2^T$ and $x_i^TAx_i=trace(A*X)/2,~\forall i$ for any $X\geq 0, rank(X)=2$ and symmetric $A$. $\endgroup$ – dineshdileep Sep 2 '14 at 14:46
  • $\begingroup$ Sorry, please disregard my previous comment. $\endgroup$ – Lev Borisov Sep 2 '14 at 15:26
6
$\begingroup$

I don't know what's going on with the paper, but here is an argument regarding existence of such decompositions.

Given a rank one decomposition $$X = \sum_{i=1}^R x_ix_i^T$$ one has $\sum_{i=1}^R x_i^TAx_i = {\rm Trace}(AX)$, so the question is how to make these pairings $x_i^TAx_i$ equal to each other. Consider the minimum of the function $$ \sum_{i} (x_i^TAx_i-\frac 1R{\rm Trace}(AX))^2 $$ over the set of all possible rank one decompositions of $X$ (which is easily a compact set). Suppose this minimum occurs at some $\{x_i\}$ and is positive.

By reindexing, we may assume that $x_1^TAx_1<\frac 1R {\rm Trace}(AX)$ and is the minimum of $x_i^TAx_i$ and that $x_2^TAx_2>x_1^TAx_1$. Consider a small rotation $\alpha$: $$y_1(\alpha)=x_1 \cos \alpha + x_2 \sin \alpha,~ y_2(\alpha) = -x_1\sin\alpha + x_2\cos\alpha,$$ so that $y_1y_1^T+y_2y_2^T=x_1x_1^T+x_2x_2^T$. By minimality, $$ y_1^T(\alpha)Ay_1(\alpha) \leq x_1^TAx_1 $$ at all sufficiently small $\alpha$, else we can move the pairings closer together by replacing $x_1$ and $x_2$ by $y_1$ and $y_2$ for small $\alpha$ and keeping $x_{>2}$, which would contradict the minimality. This first of all implies by differentiating at $\alpha=0$ that $$ x_1^TAx_2=0. $$ Thus we get $$ y_1^T(\alpha)Ay_1(\alpha) = x_1^TAx_1\cos^2\alpha + x_2^TAx_2\sin^2\alpha =x_1^TAx_1 + (x_2^TAx_2-x_1^TAx_1)\sin^2\alpha > x_1^TAx_1 $$ which is a contradiction.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This can be made into an effective algorithm by picking at each step indices with minimum and maximum $x_i^TAx_i$ and performing a rotation to make one of the values the desired $\frac 1R {\rm Trace}(AX)$. $\endgroup$ – Lev Borisov Sep 2 '14 at 20:01
  • $\begingroup$ I am trying to understand your method. So before starting the algorithm, one needs to solve the function $ \sum_{i} (x_i^TAx_i-\frac 1R{\rm Trace}(AX))^2 $ and find $x_i$? Or can one start with any arbitrary $x_i$ which is a rank-one decomposition of $X$? $\endgroup$ – dineshdileep Sep 3 '14 at 0:25
  • $\begingroup$ No, not at all: the algorithm does not use the function. Rather, it is based on the rotation idea. First, you pick ANY decomposition into $x_ix_i^T$. Then at each step, you take the "smallest" and the "largest" indices as far as $x_i^TAx_i$ are concerned and consider the rotations above. For some choice of $\cos \alpha$ one will get the correct value of $x^TAx$ (since at $\alpha=0$ the value is too small at $\alpha=\frac \pi 2$ it is too big; also, it is not a terribly hard equation). You replace the two $x$-s by two $y$-s thus increasing the number of indices for which the $x_i^TAx_i$ is OK. $\endgroup$ – Lev Borisov Sep 3 '14 at 1:27
  • $\begingroup$ excellent!. I understood your algorithm. However, I wish I could understand the way the paper has proved it. $\endgroup$ – dineshdileep Sep 4 '14 at 4:17
  • 1
    $\begingroup$ Maybe write to the author? $\endgroup$ – Lev Borisov Sep 4 '14 at 11:55
1
$\begingroup$

$$X_1 = RR' - x_1x_1'$$ U is unitary therefore, $$X_1 = RUIU'R' - \frac{1}{r}RUhh'U'R'$$ Let $M = RU$ then $X = MM'$ So the question becomes whether $MM' - M\frac{hh'}{r}M'$ is psd or not ? so we go to the definition and consider $$E = x'MM'x - x'Mhh'M'x/r$$ Let $y=M'x$, so we want to show that $||y||^2 > \langle \frac{h}{\sqrt{r}}, y \rangle^2$

Now this is easily seen if $r == N$ because then $||\frac{h}{\sqrt{r}}||=1$ and cauchy-scwartz kicks in.

I don't have a elegant proof when $r < N$ but the basic idea is that since $X$ has rank $r$ therefore $R \in \mathcal{R}^{N, r}, U \in \mathcal{R}^{r,r}$. We can make the dimensions correct by appending $N-r$ columns of zeros before multiplying $U$ with $h$ but that means we would discard those $N-r$ values and therefore truncate the effective norm of $h$ to be less than $r$.

| cite | improve this answer | |
$\endgroup$

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.