Decomposition of a semi-definite matrix into sums of sparse semi-definite matrices I'll first provide the background.
Let $x\in\mathbb{R}^N$ be decomposed into $n$ non-overlapping blocks of variables
$x^{(1)},\ldots,x^{(n)}$.
We say that $f:\mathbb{R}^N\rightarrow\mathbb{R}$ is partially separable of degree $w$, that it can be written in the form of
\begin{align}
f(x)=\sum_{J\in\mathcal{J}}f_J(x),
\end{align}
where $\mathcal{J}$ is a finite collection of nonempty subsets of $\{1,\ldots,n\}$,
$f_J$ are differential convex functions such that $f_J$ depends on blocks $x^{(i)}$
for $i\in J$, and
\begin{align}
\lvert J\rvert\le w,\forall J\in\mathcal{J}
\end{align}
My problem is to find the minimum degree of partial separability of function
$f(x)=x^{\mathrm{T}}\mathbf{M}x$, $x\in\mathbb{R}^N$, $\mathbf{M}\succeq\mathbf{0}$.
That is to decompose $\mathbf{M}$ into sums of sparse semi-definite matrix
$\mathbf{M}_J$, while minimizing the number of entries of $\mathbf{M}_J$ which
has the maximum number of entries for all $J\in\mathcal{J}$
\begin{align}
\min\max_{J\in\mathcal{J}}&\lVert\mathbf{M}_J\rVert_0\\
\textrm{s.t. }\sum_{J\in\mathcal{J}}\mathbf{M}_{J}&=\mathbf{M}\\
\mathbf{M}\succeq\mathbf{0},\mathbf{M}_J\succeq&\mathbf{0},\forall J\in\mathcal{J}\\
\mathcal{J}\in2&^{\{1,\ldots,N\}}
\end{align}
where $\lVert\cdot\rVert_0$ represents the number of entries in a matrix.
This nonlinear optimization problem seems very difficult.
I don't even know if there is any feasible solution.
 A: This is a very interesting problem. However, I don't see any way to make it tractable.
If you are interested in good relaxations, you may want to have a look at spectral sparsifiers (see Nick Havey's paper: Sparse Sums of Positive Semideﬁnite Matrices
http://www.cs.ubc.ca/~nickhar/Publications/SparsifierMMWUM/SparsifierMMWUM.pdf and references within). These sparsifiers approximate the quadratic form in the Lowner order, which should work well for your application, but do not exactly minimize the sparsity; they do it only approximately. The analysis depends heavily on results from Matrix Concentration, and I don't know if there are more traditional optimization approaches.
Good luck!
A: A heuristic approach may be to first construct a chordal embedding of the sparsity pattern, which automatically identifies the cliques. This defines the set $J$, and then the problem should be convex (tractable). 
(See, for example, Chapter 4 in http://www.seas.ucla.edu/~vandenbe/publications/chordalsdp.pdf, or for a black box implementation, see symbolic.py in the Chompack package https://github.com/cvxopt/chompack.) 
