Scaling, Fractals and Wavelets

Scaling is a mathematical transformation that enlarges or diminishes objects. The technique is used in a variety of areas, including finance and image processing. This book is organized around the notions of scaling phenomena and scale invariance. The various stochastic models commonly used to describe scaling ? self-similarity, long-range dependence and multi-fractals ? are introduced. These models are compared and related to one another. Next, fractional integration, a mathematical tool closely related to the notion of scale invariance, is discussed, and stochastic processes with prescribed scaling properties (self-similar processes, locally self-similar processes, fractionally filtered processes, iterated function systems) are defined. A number of applications where the scaling paradigm proved fruitful are detailed: image processing, financial and stock market fluctuations, geophysics, scale relativity, and fractal time-space.

Preface 17

Chapter 1. Fractal and Multifractal Analysis in Signal Processing 19
Jacques LEVY VEHEL and Claude TRICOT

1.1. Introduction 19

1.2.Dimensions of sets 20

1.2.1.Minkowski-Bouligand dimension 21

1.2.2. Packing dimension 25

1.2.3.Covering dimension 27

1.2.4. Methods for calculating dimensions 29

1.3. Holder exponents 33

1.3.1. Holder exponents related to a measure 33

1.3.2. Theorems on set dimensions 33

1.3.3. Holder exponent related to a function 36

1.3.4. Signal dimension theorem 42

1.3.5. 2-microlocal analysis 45

1.3.6. An example: analysis of stock market price 46

1.4. Multifractal analysis 48

1.4.1. What is the purpose of multifractal analysis? 48

1.4.2. First ingredient: local regularity measures 49

1.4.3. Second ingredient: the size of point sets of the same regularity 50

1.4.4. Practical calculation of spectra 52

1.4.5. Refinements: analysis of the sequence of capacities, mutual analysis and multisingularity 60

1.4.6. The multifractal spectra of certain simple signals 62

1.4.7.Two applications 66

1.5.Bibliography 68

Chapter 2. Scale Invariance and Wavelets 71
Patrick FLANDRIN, Paulo GONCALVES and Patrice ABRY

2.1. Introduction 71

2.2. Models for scale invariance 72

2.2.1. Intuition 72

2.2.2. Self-similarity 73

2.2.3. Long-range dependence 75

2.2.4. Local regularity 76

2.2.5. Fractional Brownian motion: paradigm of scale invariance 77

2.2.6. Beyond the paradigm of scale invariance 79

2.3.Wavelet transform 81

2.3.1. Continuous wavelet transform 81

2.3.2.Discretewavelet transform 82

2.4. Wavelet analysis of scale invariant processes 85

2.4.1. Self-similarity 86

2.4.2. Long-range dependence 88

2.4.3. Local regularity 90

2.4.4. Beyond second order 92

2.5. Implementation: analysis, detection and estimation 92

2.5.1. Estimation of the parameters of scale invariance 93

2.5.2. Emphasis on scaling laws and determination of the scaling range 96

2.5.3. Robustness of the wavelet approach 98

2.6. Conclusion 100

2.7.Bibliography 101

Chapter 3.Wavelet Methods for Multifractal Analysis of Functions 103
Stephane JAFFARD

3.1. Introduction 103

3.2. General points regarding multifractal functions 104

3.2.1. Important definitions 104

3.2.2. Wavelets and pointwise regularity 107

3.2.3. Local oscillations 112

3.2.4. Complements 116

3.3. Random multifractal processes 117

3.3.1. Levy processes 117

3.3.2. Burgers’ equation and Brownian motion 120

3.3.3. Random wavelet series 122

3.4. Multifractal formalisms 123

3.4.1. Besov spaces and lacunarity 123

3.4.2. Construction of formalisms 126

3.5. Bounds of the spectrum 129

3.5.1. Bounds according to the Besov domain 129

3.5.2. Bounds deduced from histograms 132

3.6. The grand-canonical multifractal formalism 132

3.7.Bibliography 134

Chapter 4. Multifractal Scaling: General Theory and Approach by Wavelets 139
Rudolf RIEDI

4.1. Introduction and summary 139

4.2. Singularity exponents 140

4.2.1.Holder continuity 140

4.2.2. Scaling of wavelet coefficients 142

4.2.3. Other scaling exponents 144

4.3. Multifractal analysis 145

4.3.1. Dimension based spectra 145

4.3.2. Grain based spectra 146

4.3.3. Partition function and Legendre spectrum 147

4.3.4. Deterministic envelopes 149

4.4. Multifractal formalism 151

4.5. Binomial multifractals 154

4.5.1.Construction 154

4.5.2. Wavelet decomposition 157

4.5.3. Multifractal analysis of the binomial measure 158

4.5.4. Examples 160

4.5.5. Beyond dyadic structure 162

4.6. Wavelet based analysis 163

4.6.1. The binomial revisited with wavelets 163

4.6.2. Multifractal properties of the derivative 165

4.7. Self-similarity and LRD 167

4.8. Multifractal processes 168

4.8.1.Construction and simulation 169

4.8.2. Global analysis 170

4.8.3. Local analysis of warped FBM 170

4.8.4.LRDand estimation ofwarped FBM 173

4.9.Bibliography 173

Chapter 5. Self-similar Processes 179
Albert BENASSI and Jacques ISTAS

5.1. Introduction 179

5.1.1.Motivations 179

5.1.2. Scalings 182

5.1.3. Distributions of scale invariant masses 184

5.1.4. Weierstrass functions 185

5.1.5. Renormalization of sums of random variables 186

5.1.6. A common structure for a stochastic (semi-)self-similar process 187

5.1.7. Identifying Weierstrass functions 188

5.2. The Gaussian case 189

5.2.1. Self-similar Gaussian processes with r-stationary increments 189

5.2.2. Elliptic processes 190

5.2.3. Hyperbolic processes 191

5.2.4. Parabolic processes 192

5.2.5. Wavelet decomposition 192

5.2.6. Renormalization of sums of correlated random variable 193

5.2.7. Convergence towards fractional Brownian motion 193

5.3. Non-Gaussian case 195

5.3.1. Introduction 195

5.3.2. Symmetric α-stable processes 196

5.3.3. Censov and Takenaka processes 198

5.3.4. Wavelet decomposition 198

5.3.5. Process subordinated to Brownian measure 199

5.4. Regularity and long-range dependence 200

5.4.1. Introduction 200

5.4.2. Two examples 201

5.5.Bibliography 202

Chapter 6. Locally Self-similar Fields 205
Serge COHEN

6.1. Introduction 205

6.2. Recap of two representations of fractional Brownian motion 207

6.2.1. Reproducing kernel Hilbert space 207

6.2.2. Harmonizable representation 208

6.3. Two examples of locally self-similar fields 213

6.3.1. Definition of the local asymptotic self-similarity (LASS) 213

6.3.2. Filtered white noise (FWN) 214

6.3.3. Elliptic Gaussian random fields (EGRP) 215

6.4. Multifractional fields and trajectorial regularity 218

6.4.1.Two representations of theMBM 219

6.4.2. Study of the regularity of the trajectories of the MBM 221

6.4.3. Towards more irregularities: generalized multifractional Brownian motion (GMBM) and step fractional Brownian motion (SFBM) 222

6.5. Estimate of regularity 226

6.5.1. General method: generalized quadratic variation 226

6.5.2. Application to the examples 228

6.6.Bibliography 235

Chapter 7. An Introduction to Fractional Calculus 237
Denis MATIGNON

7.1. Introduction 237

7.1.1.Motivations 237

7.1.2. Problems 238

7.1.3. Outline 239

7.2. Definitions 240

7.2.1. Fractional integration 240

7.2.2. Fractional derivatives within the framework of causal distributions 242

7.2.3. Mild fractional derivatives, in the Caputo sense 246

7.3. Fractional differential equations 251

7.3.1. Example 251

7.3.2. Framework of causal distributions 254

7.3.3. Framework of functions expandable into fractional power series (α-FPSE) 255

7.3.4. Asymptotic behavior of fundamental solutions 257

7.3.5. Controlled-and-observed linear dynamic systems of fractional order 261

7.4. Diffusive structure of fractional differential systems 262

7.4.1. Introduction to diffusive representations of pseudo-differential operators 263

7.4.2. General decomposition result 264

7.4.3. Connection with the concept of long memory 265

7.4.4. Particular case of fractional differential systems of commensurate orders 265

7.5. Example of a fractional partial differential equation 266

7.5.1. Physical problem considered 267

7.5.2. Spectral consequences 268

7.5.3. Time-domain consequences 268

7.5.4. Free problem 272

7.6. Conclusion 273

7.7.Bibliography 273

Chapter 8. Fractional Synthesis, Fractional Filters 279
Liliane BEL, Georges OPPENHEIM, Luc ROBBIANO and Marie-Claude VIANO

8.1. Traditional and less traditional questions about fractionals 279

8.1.1.Notes on terminology 279

8.1.2. Short and long memory 279

8.1.3. From integer to non-integer powers: filter based sample path design 280

8.1.4. Local and global properties 281

8.2. Fractional filters 282

8.2.1. Desired general properties: association 282

8.2.2. Construction and approximation techniques 282

8.3. Discrete time fractional processes 284

8.3.1. Filters: impulse responses and corresponding processes 284

8.3.2. Mixing and memory properties 286

8.3.3. Parameter estimation 287

8.3.4. Simulated example 289

8.4. Continuous time fractional processes 291

8.4.1. A non-self-similar family: fractional processes designed from fractional filters 291

8.4.2. Sample path properties: local and global regularity, memory 293

8.5. Distribution processes 294

8.5.1. Motivation and generalization of distribution processes 294

8.5.2. The family of linear distribution processes 294

8.5.3. Fractional distribution processes 295

8.5.4. Mixing and memory properties 296

8.6.Bibliography 297

Chapter 9. Iterated Function Systems and Some Generalizations: Local Regularity Analysis and Multifractal Modeling of Signals 301
Khalid DAOUDI

9.1. Introduction 301

9.2. Definition of the Holder exponent 303

9.3. Iterated function systems (IFS) 304

9.4. Generalization of iterated function systems 306

9.4.1. Semi-generalized iterated function systems 307

9.4.2. Generalized iterated function systems 308

9.5. Estimation of pointwise Holder exponent by GIFS 311

9.5.1. Principles of themethod 312

9.5.2. Algorithm 314

9.5.3.Application 315

9.6. Weak self-similar functions and multifractal formalism 318

9.7. Signal representation by WSA functions 320

9.8. Segmentation of signals by weak self-similar functions 324

9.9. Estimation of the multifractal spectrum 326

9.10. Experiments 327

9.11.Bibliography 329

Chapter 10. Iterated Function Systems and Applications in Image Processing 333
Franck DAVOINE and Jean-Marc CHASSERY

10.1. Introduction 333

10.2. Iterated transformation systems 333

10.2.1. Contracting transformations and iterated transformation systems 334

10.2.2.Attractor of an iterated transformation system 335

10.2.3. Collage theorem 336

10.2.4. Finally contracting transformation 338

10.2.5. Attractor and invariant measures 339

10.2.6. Inverse problem 340

10.3. Application to natural image processing: image coding 340

10.3.1. Introduction 340

10.3.2. Coding of natural images by fractals 342

10.3.3. Algebraic formulation of the fractal transformation 345

10.3.4. Experimentation on triangular partitions 351

10.3.5. Coding and decoding acceleration 352

10.3.6. Other optimization diagrams: hybrid methods 360

10.4.Bibliography 362

Chapter 11. Local Regularity and Multifractal Methods for Image and Signal Analysis 367
Pierrick LEGRAND

11.1. Introduction 367

11.2.Basic tools 368

11.2.1. Holder regularity analysis 368

11.2.2. Reminders on multifractal analysis 369

11.3. Holderian regularity estimation 371

11.3.1. Oscillations (OSC) 371

11.3.2. Wavelet coefficient regression (WCR) 372

11.3.3. Wavelet leaders regression (WL) 372

11.3.4.Limit inf and limit sup regressions 373

11.3.5. Numerical experiments 374

11.4. Denoising 376

11.4.1. Introduction 376

11.4.2. Minimax risk, optimal convergence rate and adaptivity 377

11.4.3. Wavelet based denoising 378

11.4.4. Non-linear wavelet coefficients pumping 380

11.4.5. Denoising using exponent between scales 383

11.4.6. Bayesian multifractal denoising 386

11.5. Holderian regularity based interpolation 393

11.5.1. Introduction 393

11.5.2.Themethod 393

11.5.3. Regularity and asymptotic properties 394

11.5.4. Numerical experiments 394

11.6. Biomedical signal analysis 394

11.7. Texture segmentation 401

11.8. Edge detection 403

11.8.1. Introduction 403

11.8.1.1. Edge detection 406

11.9. Change detection in image sequences using multifractal analysis 407

11.10. Image reconstruction 408

11.11.Bibliography 409

Chapter 12. Scale Invariance in Computer Network Traffic 413
Darryl VEITCH

12.1. Teletraffic – a new natural phenomenon 413

12.1.1. A phenomenon of scales 413

12.1.2. An experimental science of “man-made atoms” 415

12.1.3. A random current 416

12.1.4. Two fundamental approaches 417

12.2. From a wealth of scales arise scaling laws 419

12.2.1. First discoveries 419

12.2.2.Laws reign 420

12.2.3. Beyond the revolution 424

12.3. Sources as the source of the laws 426

12.3.1.The sumor its parts 426

12.3.2.The on/off paradigm 427

12.3.3. Chemistry 428

12.3.4. Mechanisms 429

12.4. New models, new behaviors 430

12.4.1. Character of a model 430

12.4.2. The fractional Brownian motion family 431

12.4.3. Greedy sources 432

12.4.4. Never-ending calls 432

12.5. Perspectives 433

12.6.Bibliography 434

Chapter 13. Research of Scaling Law on Stock Market Variations 437
Christian WALTER

13.1. Introduction: fractals in finance 437

13.2. Presence of scales in the study of stock market variations 439

13.2.1. Modeling of stock market variations 439

13.2.2. Time scales in financial modeling 445

13.3. Modeling postulating independence on stock market returns 446

13.3.1. 1960-1970: from Pareto’s law to Levy’s distributions 446

13.3.2. 1970–1990: experimental difficulties of iid-α-stable model 448

13.3.3. Unstable iid models in partial scaling invariance 452

13.4. Research of dependency and memory of markets 454

13.4.1. Linear dependence: testing of H-correlative models on returns 454

13.4.2. Non-linear dependence: validating H-correlative model on volatilities 456

13.5. Towards a rediscovery of scaling laws in finance 457

13.6.Bibliography 458

Chapter 14. Scale Relativity, Non-differentiability and Fractal Space-time 465
Laurent NOTTALE

14.1. Introduction 465

14.2. Abandonment of the hypothesis of space-time differentiability 466

14.3. Towards a fractal space-time 466

14.3.1. Explicit dependence of coordinates on spatio-temporal resolutions 467

14.3.2. From continuity and non-differentiability to fractality 467

14.3.3. Description of non-differentiable process by differential equations 469

14.3.4. Differential dilation operator 471

14.4. Relativity and scale covariance 472

14.5. Scale differential equations 472

14.5.1. Constant fractal dimension: “Galilean” scale relativity 473

14.5.2. Breaking scale invariance: transition scales 474

14.5.3. Non-linear scale laws: second order equations, discrete scale invariance, log-periodic laws 475

14.5.4. Variable fractal dimension: Euler-Lagrange scale equations 476

14.5.5. Scale dynamics and scale force 478

14.5.6. Special scale relativity – log-Lorentzian dilation laws, invariant scale limit under dilations 481

14.5.7. Generalized scale relativity and scale-motion coupling 482

14.6. Quantum-like induced dynamics 488

14.6.1. Generalized Schrodinger equation 488

14.6.2. Application in gravitational structure formation 492

14.7. Conclusion 493

14.8.Bibliography 495

List of Authors 499

Index 503

Paulo Goncalves graduated from the Signal Processing Department of ICPI, Lyon, France in 1993. He received the Masters (DEA) and Ph.D. degrees in signal processing from the Institut National Polytechnique, Grenoble, France, in 1990 and 1993 respectively. While working toward his Ph.D. degree, he was with Ecole Normale Superieure, Lyon. In 1994-96, he was a Postdoctoral Fellow at Rice University, Houston, TX. Since 1996, he is associate researcher at INRIA, first with Fractales (1996-99), and then with a research team at INRIA Rhone-Alpes (2000-2003). His research interests are in multiscale signal and image analysis, in wavelet-based statistical inference, with application to cardiovascular research and to remote sensing for land cover classification.

Jacques Levy Vehel graduated from Ecole Polytechnique in 1983 and from Ecole Nationale Superieure des Telecommuncations in 1985. He holds a Ph.D in Applied Mathematics from Universite d'Orsay. He is currently a research director at INRIA, Rocquencourt, where he created the Fractales team, a research group devoted to the study of fractal analysis and its applications to signal/image processing. He also leads a research team at IRCCYN, Nantes, with the same scientific focus. His current research interests include (multi)fractal processes, 2-microlocal analysis and wavelets, with application to Internet traffic, image processing and financial data modelling.