Finding $P$ points among $N$ to approximate a probability density function?

Question

Let $f$ be a probability density function (positive such that $\int_{\mathbb{R}} f(x) \mathrm{d} x = 1$) and $X_0 = \{x_n\}_{1\leq n \leq N}$ be $N$ given real points. We also fix $1 \leq P \leq N$ an integer.

For $X$ a subset of $X_0$ of size $P$, we set $$f_X(x) = \frac{1}{P} \sum_{x_0 \in X} g(x-x_0),$$ where $g$ is a Gaussian of mean $0$ and variance $1$.

We consider the following optimisation problem: $$\min_{X \subset X_0} \int_{\mathbb{R}} \lvert f (x) - f_X(x) \rvert \mathrm{d} x.$$

This means that we aim at approximating $f(x)$ optimally with a density of the form $f_X$, the challenge being to adequately select $P$ points among the $N$ that are initially given.

Is there any smart way to tackle such optimization task?

NB: $g$ can be changed for any other density if the problem is easier to solve.

Answer 1

One approach is to reformulate the problem as an integer convex optimization problem.

For $\lambda \in \mathbb{R}^N$, $\lambda = (\lambda_1, \ldots, \lambda_N)$, let $g_{\lambda}(x) = \frac{1}{P} \sum_i \lambda_i g(x - x_i)$. Now consider $V : \mathbb{R}^N \to \mathbb{R}$ given by

$$ V : \lambda \mapsto \int_{\mathbb{R}} | f(x) - g_{\lambda}(x) | \, dx $$

The function $V$ is convex, and the desired solution is the integer lattice minimizer of $V$ subject to the constraints $0 \leq \lambda_i \leq 1$ and $\sum_i \lambda_i = P$. Techniques exist to minimize convex functions on a convex domain in the integer lattice by reformulating as an integer linear programming problem with added slack variables.

This approach has the advantages of being general (it will work for any choice of the approximating distribution $g$ for instance) and of being supported by various mature software packages, but it has the disadvantage that it doesn't make much use of the specifics of the problem in question.