MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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

share|cite|improve this answer

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, or for a black box implementation, see in the Chompack package

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.