# Solving the inverse fractal problem from wavelet analysis

Alain Arneodo, Emmanuel Bacry, Jean-François Muzy

## ► To cite this version:

Alain Arneodo, Emmanuel Bacry, Jean-François Muzy. Solving the inverse fractal problem from wavelet analysis. EPL - Europhysics Letters, 1994, 25 (7), pp.479-484. 10.1209/0295-5075/25/7/001. hal-01557135

HAL Id: hal-01557135

https://hal.science/hal-01557135

Submitted on 3 Aug 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Solving the Inverse Fractal Problem from Wavelet Analysis.

A. ARNEODO(*), E. BACRY(**) and J. F. MUZY (*)

(*) Centre de Recherche Paul Pascal, Avenue Schweitzer - 33600 Pessac, France

(**) Université de Paris VII, UFR de Mathématiques, Tour 45-55

2 Place Jussieu, 75251 Paris Cedex 05, France

**Abstract.** – We report on a wavelet-based technique for solving the inverse fractal problem. We show that one can uncover a dynamical system which leaves invariant a given fractal object from the space scale arrangement of its wavelet transform modulus maxima. Our purpose is illustrated on Bernoulli invariant measures of linear as well as non-linear «cookie-cutters». Application to period-doubling dynamical systems at the onset of chaos is reported.

Fractal and multifractal concepts [1-3] have proved to be very fruitful to describe physical situations where scale-invariant objects are observed [4, 5]. The so-called multifractal formalism [3] which accounts for the statistical scaling properties of singular measures, is now widely used in many fields [4, 5] such as dynamical-system theory, fully developed turbulence, transport processes in disordered systems and interfacial growth phenomena. Recently, this formalism has been generalized to singular distributions [6] (including measures and signals) using the wavelet transform [7, 8]. However, the multifractal formalism is a statistical description that only provides «macroscopic» information about the self-similarity properties of fractal objects through the determination of «thermodynamical» functions such as the generalized fractal dimensions $D_q$ and the $f(\alpha)$ singularity spectrum. It is then natural to try to get deeper insight into the complexity of such objects and eventually to extract some «microscopic» information about their underlying hierarchical structure. The inverse problem consists in expressing these properties in terms of a dynamical system which leaves the fractal object invariant. It has been previously approached within the theory of Iterated Function Systems [9, 10] (IFS). However, the methods developed in this context are based on the search of a «best fit» within a prescribed class of IFS attractors (mainly linear homogeneous attractors). In that sense, they approximate the self-similarity properties more than they reveal them. In this letter, we show that the space scale representation of the wavelet transform of a fractal object can be used to extract some dynamical system which accounts for its construction process.

The fractal objects we will consider are the invariant measures of «cookie-cutters». A cookie-cutter [11] is a map on $A = [0, 1]$ which is hyperbolic ($|T'| > 1$) and such that $T^{-1}(A)$ is a finite union of $s$ disjoint subintervals $(A_k)_{1 \le k \le s}$ of $A$. For each $k$, $T_k = T|_{A_k}$ is a one-to-one map on $A$. An invariant measure $\mu$ associated to $T$ is a measure which satisfies $\mu \circ T^{-1} = \mu$. We will suppose that the weights are multiplicatively distributed on $A$, i.e.

$$ \mu \circ T_k^{-1} = p_k \mu, \quad \forall k \in \{1, \dots, s\}, \qquad (1) $$
where $\sum p_k = 1$. These self-similar measures are also referred to as Bernoulli invariant measures of expanding Markov maps [3b]. They have been widely used for modeling a large variety of highly irregular physical distributions [4, 11].

The wavelet transform is a space scale analysis [7] which has already proved to be particularly well adapted for studying the hierarchical structure of fractal objects [12,13]. The wavelet transform of a measure $\mu$ according to the *analysing wavelet $\psi$* is defined as [13]

$$T_{\psi}[\mu](b, a) = \int_{A} \psi\left(\frac{x-b}{a}\right) d\mu, \qquad (2)$$

where $a \in \mathbf{R}^{+*}$ is the scale parameter and $b \in \mathbf{R}$ is the space parameter. Usually $\psi$ is chosen to have some vanishing moments up to a certain order so that it is orthogonal to possible regular (i.e. polynomial) behaviour of $\mu$. In the case of invariant measures of cookie-cutters there is no such behaviour so we will use a simple «smoothing wavelet» $\psi(x) = \exp(-x^2)$. By combining eqs. (1) and (2), a straightforward calculation at the first order in $a$ ($a \ll 1$) leads to the following relation [6b, 14]:

$$T_{\psi}[\mu](b, a) = \frac{1}{p_k} T_{\psi}[\mu](T_k^{-1}(b), T_k^{-1}(b)a), \quad \forall k \in \{1, \dots, s\}, \qquad (3)$$

where $T_k^{-1'}$ is the first derivative of $T_k^{-1}$. In the case where the $T_k^{-1'}$s are linear, i.e. $T_k^{-1}(x) = r_k x + s_k$ ($r_k < 1$), we thus obtain

$$T_{\psi}[\mu](b, a) = \frac{1}{p_k} T_{\psi}[\mu](r_k b + s_k, r_k a), \quad \forall k \in \{1, \dots, s\}. \qquad (4)$$

These relations can be interpreted as self-similarity properties of the wavelet transform itself [13]. Indeed, in the linear case, the wavelet transform on the rectangle $[0, 1] \times ]0, a_0]$ of the space scale half-plane $(b, a)$ is «similar» to the wavelet transform on each of the rectangles $[s_k, r_k + s_k] \times ]0, r_k a_0]$ ($a_0$ is an appropriate coarsest scale which actually depends on the analysing wavelet). Our goal is to study the self-similarity properties of $\mu$ through those of its wavelet transform $T_{\psi}[\mu]$. Indeed we will restrict our analysis to the local maxima of the modulus of the wavelet transform [8c, 15], i.e. the local maxima of the function $|T_{\psi}[\mu](x, a)|$ considered as a function of $x$. One can easily prove that the self-similarity relation (3) still holds when restricted to the set of modulus maxima of the wavelet transform [6b].

Let us illustrate our purpose on a particular example. For the sake of simplicity, we choose $s=2$, $p_1 = p_2 = 1/2$ and the $T_k$'s to be linear: $T_1(x) = 5x/3$ and $T_2(x) = 5x - 4$. The corresponding invariant measure is shown in fig. 1a) and the position of its wavelet transform modulus maxima in fig. 1b). As previously pointed out, one can see that the part of the space scale plane displayed in fig. 1b) (the entire rectangle $[0, 1] \times ]0, a_0]$) is «similar» to the two rectangles delimited by the dashed lines ($[0, 3/5] \times ]0, 3a_0/5]$ and $[4/5, 1] \times ]0, a_0/5]$). The local maxima are lying on connected curves usually referred to as *maxima lines* [6, 8c]. We call *bifurcation point* any point in the space scale plane located at a scale where a maxima line appears and which is equidistant to this line and to the closest longer line. The bifurcation points at coarse scales are displayed in fig. 1b) using the symbols (●). They lie on a binary tree whose root is the bifurcation point at the coarsest scale. Each bifurcation point defines naturally a subtree which can be associated to a rectangle in the space scale plane. Thus the root corresponds to the original rectangle $[0, 1] \times ]0, a_0]$, whereas its two sons correspond to reduced copies delimited by the dashed lines. The self-similarity relation (eq. (4)) amounts to matching the «root rectangle» with one of the «son rectangles», i.e. the whole tree with one of the subtrees (fig. 1b). More generally, this relation associates any bifurcation point $(x_n, a_n)$ associated to an order-$n$ subtree to its hierarchical homologous $(x_{n-1}, a_{n-1})$ of an order-$(n-1)$ subtree. It follows from eq. (4) that $x_n = r_k x_{n-1} + s_k$ and $a_n = r_k a_{n-1}$. Thus by
<figure><img src="image_2.png" /></figure>

Fig. 1. — a) Invariant measure of the two-branch cookie-cutter $T_1(x) = 5x/3$, $T_2(x) = 5x - 4$, distributed with equal weights $p_1 = p_2 = 0.5$ on the interval $[0, 1]$. b) Position in the $(b, a)$-half-plane of the local maxima of the modulus of the wavelet transform of the measure shown in a), using a Gaussian analysing function. According to the self-similarity relation (eq. (4)), the maxima line arrangement in the two dashed rectangles is the same as in the original rectangle. The bifurcation points associated to each rectangle are represented by the symbols (●). Arrows indicate the matching of these bifurcation points according to the self-similarity relation (eq. (4)). c) 1D map that represents the position $x_{n-1}$ of an order-(n-1) bifurcation point vs. the position $x_n$ of the associated order-n bifurcation point following the tree matching defined in b). The graph of this map corresponds exactly to the original cookie-cutter. d) Histogram of scale ratios $r = a_n/a_{n-1}$ between the scales of two associated bifurcation points. e) Histogram of amplitude ratios $p = |T_\psi[\mu](x_n, a_n)|/|T_\psi[\mu](x_{n-1}, a_{n-1})|$ computed from two associated bifurcation points.

plotting $x_{n-1}$ vs. $x_n$, one can expect to recover the initial cookie-cutter $T$. This reconstructed 1D map is displayed in fig. 1c). As one can see, the two branches $T_1$ and $T_2$ of the cookie-cutter $T$ provide a remarkable fit of the numerical data. Let us point out that the non-uniform repartition of the data points on the theoretical curve results from the lacunarity of the measure induced by the «hole» between the two branches $T_1$ and $T_2$. In fig. 1d), we show the histogram of the (contracting) scale ratio values $r = a_n/a_{n-1}$. As expected, it displays two peaks corresponding to the two slopes $r_1 = 3/5$ and $r_2 = 1/5$ of $T_1^{-1}$ and $T_2^{-1}$, respectively. Note that the peak corresponding to the smallest value of $r$ is lower than the other one; this is a direct consequence of the finite cut-off we use in our wavelet transform calculation at small scales (the so-computed histogram can be artificially
corrected by plotting $N(r) \ln(1/r)$ instead of $N(r)$. Figure 1e) displays the histogram of amplitude ratio values $p = |T_\psi[\mu](x_n, a_n)|/|T_\psi[\mu](x_{n-1}, a_{n-1})|$. This distribution appears to be a Dirac at $p = 0.5$ which indicates (eq. (4)) that the weights $p_1$ and $p_2$ (defined in eq. (1)) are equal, i.e. the measure is uniformly distributed on the cookie-cutter Cantor set. Let us mention that the distribution $N(r)$ of scale ratios is in a way redundant with the 1D map, since it is basically made of two Diracs located at the inverse of the slopes of the two branches of this piecewise linear map. On the contrary, the distribution $N(p)$ of amplitude ratios brings a very important piece of information which is not present in the 1D map: the repartition of the weights at each construction step. In the case this repartition is not uniform, $N(p)$ no longer reduces to a single point $p = 1/2$ and one can furthermore study the joint law of $p$ with $r$ in order to find out the specific «rules» for associating a $p$ with a $r$.

Since eq. (3) generally holds for hyperbolic maps, one can apply exactly the same technique to non-linear cookie-cutters. Figure 2a) displays the 1D map extracted from the wavelet transform modulus maxima skeleton of the uniform Bernoulli measure associated to a non-linear cookie-cutter made of two inverse hyperbolic tangent branches. Once again, the numerical results match perfectly the theoretical curve. In this case, the histogram of amplitude ratios is still concentrated at a single point $p = 1/2$. The histogram of scale ratios, however, involves more than simply two scale ratios, as before, since the non-linearity of the map implies that new scale ratios are actually operating at each construction step.

As a first application of our technique to a physical problem, let us analyse the natural measure associated to the iteration of quadratic unimodal maps at the accumulation point of period doubling. It is well known [16] that the discrete-time dynamical system: $x_{i+1} = f_R(x_i) = 1 - Rx_i^2$ exhibits, as the parameter $R$ is increased, an infinite sequence of subharmonic bifurcations which accumulate at $R_\infty$ where the system possesses a $2^\infty$ orbit. Beyond this critical value, the dynamics becomes chaotic. As originally discovered independently by Feigenbaum [17a] and by Coullet and Tresser [17b], there exists a deep analogy between this transition to chaos and second-order phase transitions occurring in equilibrium thermodynamical systems. At the value $R = R_\infty$, the map $f_{R_\infty}$ belongs to the stable manifold of the fixed point $f^*$ of the renormalization operation $\mathcal{R}[f] = 1/f(1)[f \circ f](f(1)x)$. The asymptotic behaviour of the dynamics generated by $f_{R_\infty}$ is «universal» and corresponds to the one of $f^*$ which is confined on a Cantor set. The natural invariant measure is

<figure><img src="image_3.png" /><figcaption>Fig. 2. – a) Inverse problem for a non-linear cookie-cutter made of two inverse hyperbolic tangent branches. The data are obtained from the same wavelet transform tree-matching analysis as in fig. 1. The original dynamical system (solid lines) is recovered accurately. b) Inverse problem for the invariant measure associated to the critical period-doubling dynamical system $f^*$ (see text). The solid lines represent the theoretical prediction. Finer resolution computations would reveal that the right-hand branch is non-linear. The left-hand branch is linear with a slope $1/f^*(1) \approx -2.5$.</figcaption></figure>
defined on this Cantor set as the visiting probability of the orbit of $x = 0$. In fig. 2b), we show the results of our wavelet transform analysis of this measure. It reveals a well-defined map with two distinct hyperbolic branches (finer resolution computations would reveal that the left-hand branch is linear whereas the right-hand one is not). One can compute the amplitude ratio histogram and find that the weights associated to these two branches are equal ($p_1 = p_2 = 1/2$). The period-doubling natural measure can thus be seen as the invariant measure of the cookie-cutter displayed in fig. 2b) with uniform probability distribution. Ledrappier and Misiurewicz [18] have proved that the invariant measure of $f^*(x)$ is actually the same as the one of the cookie-cutter defined by $T(x) = x/f^*(1)$ on $[f^*(1), (f^*(1))^2]$ and $T(x) = f^*(x)/f^*(1)$ on $[f^*(-f^*(1)), 1]$. This map is represented in fig. 2b) by a solid line. Our numerical data are in remarkable agreement with the theoretical prediction.

In the case where $s$ is no longer equal to 2, one can easily adapt the technique by trying to match not only the root bifurcation point on its sons but also on its grandsons and so on.... For instance, in the case $s = 3$, we will match the root with one of its sons and with each of the two sons of its other son. The general algorithm uses a «best matching» procedure, so that it automatically performs the matching which is the most consistent (e.g., so that the different derivatives of $T_\psi[\mu]$ follow the same self-similarity relations as $T_\psi[\mu]$). Thus the algorithm is not looking for a given number $s$ of branches that the user would have guessed *a priori*, it automatically comes up with the «best» value of $s$. In fig. 3 we show the 1D map and the histograms of scale and amplitude ratios obtained in the linear case where $s = 3$, $p_1 = p_2 = p_3 = 1/3$ and $r_1 = 0.2$, $r_2 = 0.3$, $r_3 = 0.5$. All these values are very accurately recovered by our algorithm. Let us notice that we have considered in this letter only measures which do not involve any «memory» effect in their hierarchical structure, i.e. the successive iterations always consist in applying the same dynamical system $T$, independently of the previous iterations. However, in a certain way, a memory component can be accounted for by increasing the number $s$ of branches of a «no-memory» map $T$. As illustrated in fig. 3, this class of dynamical systems is directly amenable to our wavelet transform algorithmic procedure. Nevertheless, it is important to emphasize that because of finite-size effects, it is meaningless to look for dynamical systems with a rather high number of branches; generally, there would not be

<figure><img src="image_4.png" /><figcaption>Fig. 3. – a) Inverse problem for the invariant measure of the three-branch cookie-cutter $T_1(x) = 5x$, $T_2(x) = 10x/3 - 2/3$, $T_3(x) = 2x - 1$, distributed with equal weights $p_1 = p_2 = p_3 = 1/3$ on the interval $[0, 1]$. b) Histogram of scale ratios $\dot{r} = a_n/a_{n-1}$. c) Histogram of amplitude ratios $p = |T_\psi[\mu](x_n, a_n)|/|T_\psi[\mu](x_{n-1}, a_{n-1})|$.</figcaption></figure>
enough scales in the data in order to ensure the theoretical validity of the outcome discrete map.

In this letter, we have elaborated on a wavelet-based method for extracting a dynamical system associated to a given fractal measure. Its robustness and accuracy have been illustrated on various systems including non-linear ones. As demonstrated for the 2∞ cycle of period-doubling dynamical systems, our method is undoubtedly a powerful tool for analysing multifractal measures arising in a wide variety of physical systems. Furthermore, the ability of the wavelet transform to get rid of smooth behaviours [6, 8] allows a natural generalization of our approach to fractal signals that possess an underlying multiplicative structure. More details of this unified framework for solving the inverse-fractal problem, including stochastic processes, will be reported elsewhere. Applications of this method to diffusion-limited aggregates, turbulent velocity signals and DNA «walks» nucleotide sequences are currently in progress.

***

This work was supported by the Direction des Recherches Etudes et Techniques under contract No. 92/097.

## REFERENCES

[1] MANDELBROT B. B., *The Fractal Geometry of Nature* (Freeman, San Francisco, 1982).

[2] FRISCH U. and PARISI G., in *Turbulence and Predictability in Geophysical Fluid Dynamics and Climate Dynamics*, edited by M. GHIL, R. BENZI and G. PARISI (North-Holland, Amsterdam) 1985, p. 84.

[3] a) HALSEY T. C., JENSEN M. H., KADANOFF L. P., PROCACCIA I. and SHRAIMAN B. I., *Phys. Rev. A*, **33** (1986) 1141; b) COLLET P., LEBOWITZ G. and PORZIO A., *J. Stat. Phys.*, **47** (1987) 609.

[4] PALADIN G. and VULPIANI A., *Phys. Rep.*, **156** (1987) 148.

[5] Essays in honour of MANDELBROT B. B., *Fractal in Physics*, edited by A. AHARONY and J. FEDER, *Physica D*, **38** (1989) and references therein.

[6] a) MUZY J. F., BACRY E. and ARNEODO A., *Phys. Rev. Lett.*, **67** (1991) 3515; *Phys. Rev. E*, **47** (1993) 875; b) BACRY E., MUZY J. F. and ARNEODO A., *J. Stat. Phys.*, **70** (1993) 635.

[7] COMBES J. M., GROSSMANN A. and TCHAMITCHIAN P. (Editors), *Wavelets* (Springer, Berlin) 1989; b) LEMARIÉ P. G. (Editor), *Les Ondelettes en 1989* (Springer, Berlin) 1990); c) MEYER Y. (Editor), *Wavelets and Applications* (Springer, Berlin) 1992.

[8] a) JAFFARD S., C. R. Acad. Sci. Paris, **308** (1989) 79; b) HOLSCHNEIDER M. and TCHAMITCHIAN P., in ref. [7b] p. 102; c) MALLAT S. and HWANG W. L., *IEEE Trans. Inform. Theory*, **38** (1992) 617.

[9] a) BARNSLEY M. F. and DEMKO S. G., *Proc. R. Soc. London A*, **399** (1985) 243; b) BARNSLEY F. M., *Fractals Everywhere* (Academic Press, New York, N.Y.) 1988.

[10] HANDY C. R. and MANTICA G., *Physica D*, **43** (1990) 17.

[11] RAND D., *Ergod. Th. & Dynam. Sys.*, **9** (1989) 527.

[12] HOLSCHNEIDER M., *J. Stat. Phys.*, **50** (1988) 963; Thesis, University of Aix-Marseille II (1988).

[13] a) ARNEODO A., GRASSEAU G. and HOLSCHNEIDER M., *Phys. Rev. Lett.*, **61** (1988) 2281; in ref. [7a)] p. 182; b) ARNEODO A., ARGOUL F., ELEZGARAY F. and GRASSEAU G., in *Nonlinear Dynamics*, edited by G. TURCHETTI (World Scientific, Singapore, 1988) p. 130; c) ARNEODO A., ARGOUL F. and GRASSEAU G., in ref. [7b)] p. 125; d) ARNEODO A., ARGOUL F., BACRY E., ELEZGARAY J., FREYSZ E., GRASSEAU G., MUZY J. F. and POULIGNY B., in ref. [7c)] p. 286.

[14] MUZY J. F., Thesis, University of Nice Sophia-Antipolis (1993).

[15] MALLAT S. and ZHONG S., *IEEE Trans. Pattern Anal. Machine Intell.*, **14** (1992) 710.

[16] COLLET P. and ECKMANN J. P., *Iterated Map on the Interval as Dynamical Systems* (Birkhäuser, Boston) 1980.

[17] a) FEIGENBAUM M. J., *J. Stat. Phys.*, **19** (1978) 25; **21** (1979) 669; b) COULLET P. and TRESSER C., *J. Phys. (Paris)*, **39** C5 (1978); *C. R. Acad. Sci.*, **287** (1978) 577.

[18] LEDRAPPIER F. and MISIUREWICZ M., *Ergodic Th. and Dyn. Syst.*, **5**, (1985) 595.