# 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 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).