# Optimal decomposition of discrete function into sum of factorised terms

I am trying to solve the following optimisation problem. Let $x_i \in \{1, \ldots, N_i\}$ be discrete variables, and $f(x_1, \ldots , x_n)$ any real-valued function. I want to decompose $f$ into a weighted sum of terms $$f(x_1, \ldots , x_n) = \sum_{k=1}^K w_k g_{1k}(x_1)g_{2k}(x_2)\ldots g_{nk}(x_n) \quad w_k \geq 0$$ where each term is a product of single-variable factors, and do this with minimum total weight $\sum_i w_i$. We are free to choose any $g$ functions, I think we need a restriction of $\| g_{ij} \|_\infty = 1$ to make the problem well-defined. $K$ should be assumed to be large enough to allow an exact representation of $f$.

If $K$ is large enough, it is possible to represent any $f$ like this exactly (for example, take $K=\prod_{i=1}^n N_i$ and use indicator functions for the $g$ to point to each individual joint variable configuration in $f$ in turn, and take as $w_k$ the value of $f$ at that configuration), so there is always a solution provided $K$ is sufficiently large.

For $n=2$ binary-valued variables for example, which I am most interested in, the problem becomes

$$\min \sum_{k=1}^K w_k \quad\textrm{s.t.}\quad f_{ij}=\sum_{k=1}^K w_kg_{ki}h_{kj} \quad i\in\{0,1\}, j\in\{0,1\}, \quad \left|g_{ij}\right|,\left|h_{ij}\right| <= 1$$

This can also be viewed as a matrix factorisation: if $F$ is a 2 by 2 matrix containing the function values $f_{ij}$, $G$ and $H$ are $k$ by 2 containing the $g_{ki}$ and $h_{kj}$, and $W$ contains the $w_k$ on the diagonal, then the decomposition is $F = G'WH$.

The problem is also similar to the "mean-field" approximation used in variational inference in machine learning, except instead of approximating $f$ by a fully-factorised distribution I want a sum of fully-factorised distributions.

Is this solvable in this case and/or the general case above? Otherwise, how can I find a good approximate solution?

Someone posted an answer earlier pointing to the CP tensor factorisation which basically describes what I want, except that I am trying to minimise the weight sum rather than minimise distance between a low-rank approximation and the true $f$.

• Do you want to require $w_k\ge0$ as well? Otherwise you can send $\sum w_k\to-\infty$. – user856 Jun 19 '16 at 20:06
• @Rahul yes I should have specified that, thanks. – akxlr Jun 19 '16 at 20:31