Analogue of Chow-Liu tree for $L_1$

Say $$\Omega$$ is a finite set and $$f$$ a probability mass function (pmf) over $$\Omega^d$$. Now let $$T$$ be a spanning tree on the set $$V=\{1,2,\ldots,d\}$$, and consider a collection of one- and two- dimensional pmfs $$f_i$$ over $$\Omega$$ and $$f_{ij}$$ over $$\Omega^2$$, respectively. Together, these induce a tree distribution over $$\Omega^d$$ as follows: $$f_{T}(x)=\prod\limits_{(i,j)\in T}\frac{f_{ij}(x_{i},x_{j})}{f_{i}(x_{i})f_{j}(x_{j})}\prod_{i=1}^{d}f_{i}(x_{i}).$$

One can ask, for a given pmf $$f$$: what is the best approximation by some $$f_T$$? To make the question well-posed, one must provide a cost function on pairs of pmfs. For the choice of KL-divergence (corresponding, for finite samples, to maximum likelihood), Chow and Liu  gave a beautiful efficient algorithm based on Kruskal's MST.

Question: What if we want to minimize $$||f-f_T||_1$$ -- that is, under the $$L_1$$ distance? I suspect that this is computationally hard, but am hoping for a more quantitative statement. Is there any formal sense in which this problem is known to be hard? Are there any known efficient approximation algorithms?

• So, roughly speaking, you're asking about the complexity of agnostically learning (in TV distance) degree-1 Bayes nets? Dec 16 '21 at 9:43
• Now that you put it that way... I guess! But the learning is a bit of a red herring, since the question is about computational complexity on finite data. An interesting issue, though, is one of representation. If your input is the tensor of all of the $|\Omega|^d$ values of $f$, then you should be allowed $\exp(d)$ time just to read the data. So maybe you have oracle access to $f$ and the 1- and 2- dim marginals?.. Like I said, even getting some sort of a formal statement is non-trivial. Dec 16 '21 at 9:48