5
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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