Fractal-based measure approximation with entropy maximization and sparsity constraints

Let (X, d) denote a complete metric space. An N-map iterated function system with probabilities (IFSP) is a set of N contraction maps wi : X ! X with associated probabilities pi. The IFSP, denoted as (w, p), defines a contractive Markov operator M, on the space of of probability measures M(X) equipped with the Monge-Kantorovich metric dMK. The unique fixed point ¯μ = M¯μ is referred to as the invariant measure of the N-map IFSP. Here we consider the following inverse problem: Given a target measure μ, find an IFSP (w, p) with invariant measure ¯μ sufficiently close to μ, i.e., dMK(μ, ¯μ) < ǫ. From Banach’s Theorem, the problem may converted into finding an IFSP with Markov operator M that minimizes the collage error dMK(μ,Mμ). Nevertheless, the determination of optimal wi and pi is still a formidable problem. It was simplified in [1] by employing a fixed, infinite set of maps wi satisfying a refinement condition on (X, d). This problem was then translated into a moment matching problem that becomes a quadratic programming (QP) problem in the pi. In this paper we extend the method developed in [1] along two different directions. First, we search for a set of probabilities pi that not only minimizes the collage error but also maximizes the entropy of the iterated function system. Second, we include an extra term in the minimization process which takes into account the sparsity of the set of probabilities. In our new formulations, collage error minimization can be understood as a multi-criteria problem: i.e., collage error, entropy and sparsity. We consider two different methods of solution: (i) scalarization, which reduces the multi-criteria program to a single-criteria program by combining all objective functions with different trade-off weights and (ii) goal programming, involving the minimization of the distance between each objective function and its goal. Numerical examples show how the two above methods work in practice