Decomposition of a semi-definite matrix into sums of sparse semi-definite matrices

Question

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.

Answer 1

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 Semidefinite 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!

Answer 2

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