Monte Carlo and Quasi-Monte Carlo Methods 2004 (eBook)

Preface 5
Contents 7
Invariance Principles with Logarithmic Averaging for Ergodic Simulations 10
1 Ergodic Simulations 10
2 Almost Sure Central Limit Theorem 13
3 Speed of Convergence in the Almost Sure Central Limit Theorem 16
4 Application: Dynamical Estimation of the Asymptotic Variance 18
5 Invariance Principles for the Local Time of a Diffusion 19
Technical Analysis Techniques versus Mathematical Models: Boundaries of Their Validity Domains 24
1 Introduction 24
2 Description of the Setting 25
3 A Technical Analysis Detection Strategy 27
4 The Optimal Portfolio Allocation Strategy 30
5 A Model and Detect Strategy 34
6 The Performances of the Strategies Based on Misspecifed Models 35
7 Conclusions and Remarks 38
Weak Approximation of Stopped Dffusions 40
1 Introduction 40
2 Problem Formulation 41
3 The Method in Dimension One 42
4 Higher Dimensions: the Brownian Motion Case 47
5 Numerical Experiments 47
6 Conclusion and Summary 51
Approximation of Stochastic Programming Problems 54
1 Introduction 54
2 Preliminaries on Epi-convergence 56
3 Main Results 57
4 An Application to ams Transformations 61
5 Proofs 62
The Asymptotic Distribution of Quadratic Discrepancies 70
1 Introduction 70
2 Asymptotic Results for Lp-Discrepancies 71
3 Asymptotic Results for L2-Discrepancies 72
4 Practical Aspects of Testing 75
5 Results of the Algorithm 80
Weighted Star Discrepancy of Digital Nets in Prime Bases 86
1 Introduction 86
2 Digital (t, m, s)-Nets in Base p 88
3 The Star Discrepancy of Digital Nets 89
4 Weighted Star Discrepancy of Digital Nets 91
5 An Alternative Bound in the Binary Case 92
6 Weighted Star Discrepancy of Niederreiter and Faure-Niederreiter Sequences 95
7 Average Weighted Star Discrepancy 100
Explaining Effective Low-Dimensionality 106
1 Formation of the Integrand 107
2 Numerical Examples 109
3 Su.cient Conditions For Effective Low-Dimensionality 112
Selection Criteria for (Random) Generation of Digital (0,s)-Sequences 122
1 Introduction 122
2 Discrepancy and Diaphony 123
3 Van der Corput Sequences, Digital (0,1)-Sequences, and Related Functions 124
4 Exact Formulas, Application 125
5 Estimates and Asymptotic Behaviour 127
6 Computations 131
7 Conclusion 131
Imaging of a Dissipative Layer in a Random Medium Using a Time Reversal Method 136
1 Introduction 136
2 The Acoustic Model 137
3 Propagator Formulation 138
4 Time Reversal 141
5 The Refocused Pulse 142
6 Application to the Detection of a Dissipative Layer 147
A Stochastic Numerical Method for Diffusion Equations and Applications to Spatially Inhomogeneous Coagulation Processes 156
1 Introduction 156
2 The Particle Scheme Approximating the Diffusion Equation 159
3 Applications to Coagulation Processes with Diffusion 164
Non-Uniform Low-Discrepancy Sequence Generation and Integration of Singular Integrands 172
1 Introduction 172
2 Basic De.nitions 173
3 The Hlawka-Mück Method 175
4 Interpolation 177
5 Non-Uniform Integration of Singular Functions References 182
Construction of Good Rank-1 Lattice Rules Based on the Weighted Star Discrepancy 190
1 Introduction 190
2 Rank-1 Lattice Rules Having Certain Weighted Star Discrepancy Bounds 192
3 A Component-by-Component Construction 199
4 Results for the Weighted Lp Discrepancy 202
Probabilistic Approximation via Spatial Derivation of Some Nonlinear Parabolic Evolution Equations 206
Introduction 206
1 One Dimensional Equations 207
2 Multidimensional Equations 215
3 Bounded Spatial Domains 219
Myths of Computer Graphics 226
1 Introduction 226
2 Quasi-Monte Carlo Methods 228
3 Quasi-Monte Carlo in Computer Graphics 236
4 Quasi-Monte Carlo in Movie Industry 247
5 Conclusion 248
Illumination in the Presence of Weak Singularities 253
1 Introduction 253
2 Avoiding Bias Caused by Bounding 254
3 The New Global Illumination Algorithm 257
4 Conclusion 263
Irradiance Filtering for Monte Carlo Ray Tracing 267
1 Introduction 267
2 Irradiance Filtering 270
3 The Rendering Algorithm 274
4 Results 277
5 Conclusions 279
On the Star Discrepancy of Digital Nets and Sequences in Three Dimensions 281
1 Introduction 281
2 The Main Results 284
3 Auxiliary Results 286
4 The Proofs 289
Lattice Rules for Multivariate Approximation in the Worst Case Setting 297
1 Introduction 298
2 Formulation of the Problem 301
3 Preliminaries 302
4 Worst Case Error 309
5 First Approach: Lattice Rules Constructed for Integration 311
6 Second Approach: Lattice Rules Constructed for Approximation 316
7 Proofs 326
Randomized Quasi-Monte Carlo Simulation of Markov Chains with an Ordered State Space 339
1 Introduction 339
2 The Array-RQMC Algorithm 340
3 Unbiasedness and Convergence 343
4 A Numerical Illustration 345
Experimental Designs Using Digital Nets with Small Numbers of Points 351
1 Introduction 351
2 Orthogonal Arrays and Digital Net Designs 352
3 Quality Measures and Bounds of Digital Net Designs 352
4 Search Algorithm 357
5 Conclusion and Open Questions 361
Concentration Inequalities for Euler Schemes 363
1 Poincar´e and Logarithmic Sobolev Inequalities 363
2 Poincar´e Inequalities for Multidimensional Euler Schemes 365
3 Logarithmic Sobolev Inequalities for One-Dimensional Euler and Milstein Schemes 367
4 Logarithmic Sobolev Inequalities for Multidimensional Euler Schemes with Constant Di.usion Coe.cient and Potential Drift Coe.cient 368
5 Uniform Logarithmic Sobolev Inequalities for One–Dimensional Euler Schemes with Constant Di.usion Coe.cient and Convex Potential Drift Coeffcient 371
6 Applications 375
Fast Component-by-Component Construction, a Reprise for Different Kernels 381
1 Introduction 381
2 The Component-by-Component Algorithm 382
3 Fast Matrix-Vector Multiplication 386
4 Applications 388
5 Example Implementation in Matlab 392
6 Critical Remarks 393
A Reversible Jump MCMC Sampler for Object Detection in Image Processing 397
1 Introduction 397
2 Set Up 398
3 An RJMCMC Algorithm for Point Processes 399
4 Results 405
Quasi-Monte Carlo for Integrands with Point Singularities at Unknown Locations 411
1 Introduction 411
2 Literature 412
3 Use of Low Variation Approximations 413
4 Notation 414
5 Integrable Point Singularities 417
6 Discussion 423
Infinite-Dimensional Highly-Uniform Point Sets Defined via Linear Recurrences in F2w 427
1 Introduction 427
2 Definition of the Point Sets 428
3 Measures of Uniformity 430
4 Guaranteed Uniformity of Certain Projections 432
5 A Search for Good Point Sets 432
6 Examples 433
7 Conclusion 436
Monte Carlo Studies of Effective Diffusivities for Inertial Particles 439
1 Introduction 439
2 Periodic Homogenization for Inertial Particles 442
3 Numerical Results 443
4 Conclusions 446
An Adaptive Importance Sampling Technique 451
1 Introduction 451
2 Adapting p to . 453
3 The AIS Algorithm 456
4 Relations to Existing Algorithms 458
5 Numerical Experiments 459
MinT: A Database for Optimal Net Parameters 465
1 Introduction 465
2 Basic De.nitions and Results 466
3 Constructions, Existence, and Bounds 469
4 Sets of Possible Parameters and Their Defining Functions 469
5 Construction Trees 473
6 Outlook 475
On Ergodic Measures for McKean–Vlasov Stochastic Equations 479
1 Introduction 479
2 Main Results 481
3 Proofs 483
On the Distribution of Some New Explicit Inversive Pseudorandom Numbers and Vectors 495
1 Introduction 495
2 Auxiliary Auxiliary 497
3 Bounds for Exponential Sums 498
5 Explicit Inversive Pseudorandom Vectors 504
6 Structural Properties 506
Error Analysis of Splines for Periodic Problems Using Lattice Designs 509
1 Introduction 509
2 Integration Lattices 512
3 Error Analysis for Spline Using Lattice Designs 512
4 Experimental Results 518

A Reversible Jump MCMC Sampler for Object Detection in Image Processing (p. 389)

Mathias Ortner, Xavier Descombes, and Josiane Zerubia

Ariana Research Group (INRIA/I3S), INRIA, 2004 route des Lucioles BP 93, 06902 Sophia Antipolis Cedex, France

Summary. To detect an unknown number of objects from high resolution images, we use spatial point processes models. The method is adapted to our image processing applications since it describes images as realizations of a point process whose points represent geometrical objects. We consider models made of two parts: a data term which quanti.es the relevance of a set of objects with respect to the image and a prior term, containing strong geometrical interactions between objects. We use the Maximum A Posteriori estimator, which is obtained by combining a reversible Markov chain monte carlo (RJMCMC) point process sampler with a simulated annealing procedure. The quality of the results and the speed of the algorithm strongly depend on the used sampler.We present here an adaptation of Geyer-Møller sampler for point processes and show that the resulting Markov Chain keeps the required convergence properties. In particular, we design an updating scheme which allows the generation of points in the neighborhood of some others, and check the relevance of such moves on a toy example. We present experimental results on the di.cult problem of the detection of buildings in a Digital Elevation Model of a dense urban area.

Key words: Spatial point process, RJMCMC, non homogeneous Poisson point process, image processing, building detection.


1 Introduction

A natural way to model images in a probabilistic framework is to consider Markov Random Fields [2]. Such models allow the use of smoothing priors like the Ising model, but require to consider images as a collection of pixels. In the early nineties, A. Baddeley and M.N.M. Van Lieshout [1] proposed to model images as realizations of spatial point processes. Since a spatial point process realization can be a random con.guration of disks, rectangles, lines or any other kind of geometric shapes, spatial point process models appear to be especially amenable to the introduction of a geometric knowledge in the prior term. Spatial point process models in image processing have been used by Green [11] and Rue [12] for object detection and have been applied to real applications in remote sensing [7, 9, 13] and medical imaging [3].

Point process models are especially adapted to object detection as they allow the introduction of a probability distribution on con.gurations of geometrical shapes. Such distributions are usually sub-divided into two parts: a prior term acting on the con.guration of objects to favor or penalize speci.c geometrical patterns, and a likelihood comparing con.gurations of objects to the data. The estimator commonly used is the Maximum a Posteriori (MAP) estimator. Simulated annealing algorithms provide a practical way to compute the MAP despite numerous local maxima. However, the algorithm performance strongly depends on the mixing ability of the sampler. In this paper we present a new updating scheme that improves the quality of the Markov Chain.