Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question

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

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