# Proof for a rank-one decomposition theorem of positive (semi) definite matrices

$$\DeclareMathOperator\rank{rank}\DeclareMathOperator\trace{trace}$$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{\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$$.

• 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$. Commented Sep 2, 2014 at 14:00
• 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$. Commented Sep 2, 2014 at 14:46
• Sorry, please disregard my previous comment. Commented Sep 2, 2014 at 15:26

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.

• 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)$. Commented Sep 2, 2014 at 20:01
• 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$? Commented Sep 3, 2014 at 0:25
• 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. Commented Sep 3, 2014 at 1:27
• excellent!. I understood your algorithm. However, I wish I could understand the way the paper has proved it. Commented Sep 4, 2014 at 4:17
• Maybe write to the author? Commented Sep 4, 2014 at 11:55

$$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$.

Prof. Chris Godsil's notes on Semidefinite Programming provides a proof (2.2.1 Theorem) for the first claim, I will quote it here for reference:

2.2.1 Theorem: A positive semidefinite matrix with rank $$r$$ can be written as the sum of at most $$r$$ positive semidefinite matrices with rank one

Proof. We go by induction on $$rk(A)$$. Choose a vector $$x$$ such that $$Ax \neq 0$$—if no such vector exists then $$A = 0$$ and the result holds. Define $$B = A - \frac{1}{x^TAx}A xx^TA$$ and note that $$B - A$$ is a symmetric matrix with rank one. We claim that $$B \succcurlyeq A$$. We have $$y^TBy = y^TA y - \frac{1}{x^TAx} y^T Axx^T Ay = y^TA y - \frac{x^T A y^2}{x^T A x},$$ and, by our version of of Cauchy-Schwarz we deduce that $$B \succcurlyeq 0$$. Since the column space of $$B$$ is a subspace of the column space of $$A$$, and since $$B x = A x - \frac{1}{x^TAx}Axx^TAx= Ax - Ax = 0,$$ we have $$rk(B) < rk(A)$$. By induction, $$B$$ is a sum of at most $$rk(A) - 1$$ symmetric matrices of rank one, and the result follows. $$\square$$

The version of Cauchy-Schwarz that is used here states that if $$A \succcurlyeq 0$$, then $$(x^T A y)^2 \leq x^T A x y^T A y$$.