Decomposing PSD block matrix into two PSD block matrices Given
$$Q = \begin{pmatrix} A + B & C \\ C^T & D\end{pmatrix}$$
where we know that $Q, A, B, D$ are all square and positive semidefinite, but not necessarily equally sized matrices, we would like to decompose $Q$ into two matrices in the form of
$$Q = \begin{pmatrix} A & \color{blue}{?} \\ \color{blue}{?} & \color{blue}{?}\end{pmatrix} + \begin{pmatrix} B & \color{blue}{?} \\ \color{blue}{?} & \color{blue}{?}\end{pmatrix}$$
where both terms must be positive semidefinite. What to put in the $\color{blue}{?}$ blocks?
And what if we look for the following?
$$Q = \begin{pmatrix} A & 0 \\ 0 & \color{blue}{?}\end{pmatrix} + \begin{pmatrix} B & \color{blue}{?} \\\color{blue}{?} & \color{blue}{?}\end{pmatrix}$$
The context is quadratic optimization, where I want to solve
$$\min_x c^Tx + \frac{1}{2}x^TQx$$
In the actual problem I have a diagonal $B$ and $A=U\Sigma U^T$, where $\Sigma$ is diagonal and small compared to the huge $A$. I want to use the standard trick of introducing a new $y$ variable with the constraint $y=U^Tx$, thus saving an enormous amount of computation on using $y^T\Sigma y$ instead of $x^TAx$. Without the transformation I am asking about, I cannot decompose the quadratic term into a positive (semi)definite form, which is necessary to keep the optimiser happy. But I would be completely satisfied if somebody can show me an alternative way to play the projection trick here.
 A: Here is a partial answer for the case where both $A$ and $B$ are positive definite. We have
\begin{equation}
Q
=\begin{pmatrix}A&X\\X^T&X^TA^{-1}X\end{pmatrix}
+\begin{pmatrix}B&Y\\Y^T&Y^TB^{-1}Y\end{pmatrix}
+\begin{pmatrix}0&0\\0&D-X^TA^{-1}X-Y^TB^{-1}Y\end{pmatrix},\tag{1}
\end{equation}
where $X=A(A+B)^{-1}C$ and $Y=B(A+B)^{-1}C$. By considering the Schur complements of $A$ and $B$ in the first two summands, we see that the first two terms in $(1)$ are positive semidefinite. Furthermore, as $Q$ is positive semidefinite, the Schur complement of $A+B$ in $Q$ must be positive semidefinite too. That is, $D\succeq C^T(A+B)^{-1}C=X^TA^{-1}X + Y^TB^{-1}Y$. Therefore the last term in $(1)$ is also positive semidefinite. Absorb this last term into the first or second summand, we are done.
Unfortunately, from your problem description, it seems that $A$ is rank deficient. I am not sure if $(1)$ can be modified to work in this case (using pseudoinverse?), but hopefully it can shed some light on the problem.
