Fourier Analysis Of Correlated Monte Carlo Importance .
Fourier Analysis of Correlated Monte Carlo Importance SamplingGurprit SinghKartic SubrDavid CoeurjollyVictor OstromoukhovWojciech Jarosz
Monte Carlo Integration2
Monte Carlo Integrationf ( x)I Z0!31f ( x)d x
Monte Carlo Estimatorf ( x)IN!41 NNXk 1f ( xk )p( xk )
Monte Carlo Estimatorf ( x)IN!51 NNXk 1f ( xk )p( xk )
Random vs. Correlated SamplesRandomNX1( x xk )S( x) Np( xk )k 1!6Slide after Wojciech Jarosz
Random vs. Correlated SamplesRandomNX1( x xk )S( x) Np( xk )k 1!7Slide after Wojciech Jarosz
Random vs. Correlated SamplesRandomJitterNX1( x xk )S( x) Np( xk )k 1!8Slide after Wojciech Jarosz
Random vs. Correlated SamplesRandomJitterNX1( x xk )S( x) Np( xk )k 1!9Slide after Wojciech Jarosz
Random vs. Correlated SamplesRandomJitterNX1( x xk )S( x) Np( xk )k 1!10Poisson DiskSlide after Wojciech Jarosz
Fourier Statistics: Power SpectrumRandomJitterPS ( ) 1NNXk 1!11Poisson Disk2ei2 · xk
Point Samples’ Expected Power Spectrahi hRandomi hiJitterhPS ( )i hPoisson Disk1N12NXk 12ei2 · xki
Point Samples’ Expected Power SpectraRandomJitterhPS ( )i hPoisson Disk1N13NXk 12ei2 · xki
Monte Carlo Estimation Variance for Stationary SamplesZhPSN( )iPf ( )Fredo Durand [2011]Subr & Kautz [2013] Var(IN ) f ( x)RandomSN ( x)d 14
Monte Carlo Estimation Variance for Stationary SamplesZhPSN( )iPf ( )Fredo Durand [2011]Var(IN ) Only valid for constant PDFs (uniformly distributed samples)15!15Subr & Kautz [2013]d
Real vs. Integer FrequenciesRandomd JitteredExpected power spectraRandom:.,-0.2, 0.0, 0.2,,., -0.2, 0.0, 0.2,,. Integer freq.Var(IN ) Jittered:Real freq.Z!16
ZVar(IN ) RandomConvergence Rates Divergesd Jittered0.5With continuous formulationsWith continuous formulations0.30.20.10.2-0.2Log Variance-0.40.4f ( x)0.080.06Real freq.Integer freq.0.40.040.02-1.00.5-0.5g( x)Log N!171.0
Convergence Rates Diverges at Real FrequenciesRandomJittered1000.5Real freq.With continuous formulations10-20.30.20.1-0.4Log VarianceInteger freq.0.4Only usingInteger frequencies10-610-101000.4f ( .040.02-1.0g( x)103Log N!180.5-0.51041051.0
Monte Carlo Estimation Variance for Random SamplesZhPSN( )iPf ( )Fredo Durand [2011]Var(IN ) Only valid for constant PDFs (uniformly distributed samples)Finite sampling domain is not properly handled!19Subr & Kautz [2013]d Pilleboue et al. [2015]
Fourier series based Variance FormulationXVar(IN ) m2Z/0hPSN( )iPf ( ) Only valid for constant PDFs (uniformly distributed samples)Finite sampling domain is not properly handled!20
Fourier series based Variance FormulationXVar(IN ) m2Z/0hPSN( )iPf ( ) Stationarity can imposed using homogenization or Cranley-Patterson rotation for all samplersPilleboue et al. [2015]Only valid for constant PDFs (uniformly distributed samples)Finite sampling domain is not properly handled!21
Homogenization or Cranley-Patterson rotation!22
Homogenization or Cranley-Patterson rotation!23
Homogenization or Cranley-Patterson rotation!24
Homogenization affect Convergence!25
No Homogenization: Strata alignment helps100Log Variance10-2Worst-case BoxExponential-noCPr10-14100101102103Log N!26104105Best-caseConvergence
Strata-alignment affects Convergence100Log Variance10-2Worst-case BoxExponential-noCPr10-14100101102103Log N!27104105
Homogenization Destroys Good Correlations100Log Variance10-2Worst-case )BoxExponential-noCPr10-14100101102103Log N!28104105
Fourier series based Variance FormulationXVar(IN ) m2Z/0hPSN( )iPf ( ) Only valid for constant PDFs (uniformly distribute samples)Finite sampling domain is not properly handledHomogenization could destroy good correlations!29
Generalized Variance Formulationbased on Fourier Series!30
Generalized Variance Formulation2Var(IN ) I Var(S0 ) Xm2Zm6 0Third term fm fm hSm Sm im2Z l2Zl6 mImag coeffsReal coeffsDC component X X!31 fm fl hSm Sl i
Variance Formulation: For Homogenized SamplesVar(IN ) Xm2Zm6 0 fm fm hSm Sm i!32
Generalized Variance Formulationm2Zm6 0 m2Z l2Zl6 mReal coeffsVar(IN ) I Var(S0 ) fm fm hSm Sm iX XImag coeffs2XThird term!33 fm fl hSm Sl i
Generalized Variance Formulationm2Zm6 0 m2Z l2Zl6 mReal coeffsVar(IN ) I Var(S0 ) fm fm hSm Sm iX XImag coeffs2XThird term!34 fm fl hSm Sl i
Covariance Matrix Form2I Var(S0 ). . fm fl hSm Sl i fm fm hSm Sm i hSm Sl i. . fm f l!35
Generalized Variance Formulationm2Zm6 0 m2Z l2Zl6 mReal coeffsVar(IN ) I Var(S0 ) fm fm hSm Sm iX XImag coeffs2XThird term!36 fm fl hSm Sl i
Generalized Variance Formulation2Var(IN ) I Var(S0 ) Xm2Zm6 0Third term fm fm hSm Sm iValid for non-uniform PDFs (importance samples)No Homogenization (CPr) performedFinite sampling domain is properly handled!37 X Xm2Z l2Zl6 m fm fl hSm Sl i
Third Term is Crucial!38
Generalized Variance Formulation: Third Term CrucialVar(IN ) I Var(S0 ) m2Zm6 0 fm fm hSm Sm iFirst term cannot be ignored for IS variance predictionThird term allows correct prediction of variance:m2Z l2Zl6 mImag coeffs- when samples and integrand have correlations X XReal coeffs2XThird term- during importance sampling!39 fm fl hSm Sl i
Generalized Variance Formulation: Third Term CrucialVar(IN ) I Var(S0 ) m2Zm6 0 fm fm hSm Sm i X Xm2Z l2Zl6 mReal coeffs2XThird termSecond term is always positiveImag coeffsFor constant PDF, first term is zero, therefore,third term is negative and reduces varianceWith IS, both the first and thethird term reduces variance!40 fm fl hSm Sl i
Third termX XImag coeffsThird term is difficult to analyzeReal coeffsm2Z l2Zl6 m!41 fm fl hSm Sl i
Third Term: Encodes phase hSm Sl i hSm Sl i hSm Sl ishift 0.01shift 0.15Imag coeffsReal coeffs fm f l!42
Third Term: Encodes phase hSm Sl i hSm Sl i hSm Sl ishift 0.01shift 0.15Imag coeffsVarianceReal coeffs fm f lSpatial locationRamamoorthi et al.[2012]!43
Strata shifting affects convergenceN 2-1.50.5-1.6-1.7Convergence rateVariance0.40.30.2N 4-1.8-1.9-2-2.1-2.20.1N 16-2.30-2.400.10.20.30.40.50.60.70.80.910First stratum shift position0.10.20.30.40.50.60.7First stratum shift position!440.80.91
Third Term: Encodes phase hSm Sl i hSm Sl i hSm Sl ishift 0.01shift 0.15Imag coeffsVarianceReal coeffs fm f lSpatial locationRamamoorthi et al.[2012]!45
Third Term: Dimensionality grows fastVar(IN ) I Var(S0 ) m2Zm6 0 fm fm hSm Sm i X Xm2Z l2Zl6 mReal coeffs2XThird termImag coeffsFor one-dimensional problem:!46 fm fl hSm Sl i
Correlated Importance Samplingaffects convergence rate!47
Direct Illumination IntegralINNX1f ( xk ) Np( xk )k 1SensorLight PDF SamplingBSDF PDF SamplingLight ISBSDF IS!48
Veach Scene: Multiple Importance SamplingReference imageN 1024 sppLight importance samplingN 4 spp!49BSDF importance samplingN 4 spp
Veach Scene: Multiple Importance SamplingReference imageN 1024 sppLight importance samplingN 4 spp!50BSDF importance samplingN 4 spp
Variance Convergence: Importance Sampling!51
Variance Convergence: Importance Sampling10-2Log -12100101102103Log N104!52105
Variance Convergence: Importance Sampling10-2Log -12100101102103Log N104!53105
Variance Convergence: Importance N-2.0)Log Variance10-410-610-810-1010-12100101102103Log N104!54105
Variance Convergence: Importance g Variance10-4For multiple importance sampling (MIS),convergence is determined by the BSDF sampling strategy.10-610-810-1010-12100101102103Log N104!55105
Variance Convergence: Importance N-2.0)Log Variance10-410-610-810-1010-12100101102103Log N104!56105
10-2Integrand ter Toroidal wrappingHomogenization (CPr)Original102!57
10-2Integrand ter Toroidal wrappingHomogenization (CPr)Original102!58
Sampling Integrand MirroringOriginalMirror-random!59
Sampling Integrand MirroringOriginalMirror-randomMirror-uniform!60
Sampling Integrand MirroringOriginalMirror-randomMirror-uniform!61
Convergence: Homogenized not 101102103104105106
Convergence: No homogenized (N-2)10-1210-14100!63101102103104105106
Convergence: Mirroring variance niform-noCPr-O(N-2)10-14100!64101102103104105106
Convergence: Mirroring variance random-noCPr-O(N-2)10-14100!65101102103104105106
Convergence: Take ion introduces boundary discontinuitiesIntegrand Mirroring helps avoid these discontinuitiesBut, Integrand mirroring quadruples the sampling domain in 2D!66
Theory sidePractical sideThird term2Var(IN ) I Var(S0 ) Xm2Zm6 0 fm fm hSm Sm i X Xm2Z l2Zl6 m fmfl hS m Sl iThird term is crucial and must not be missed- consider correlations within samples w.r.t the integrandThe formulation handles Importance SamplingIn MIS, the worst of the two strategieswould determine the overallconvergence rate.In environment map sampling,simply importance samplingw.r.t. the gray channel introducesdiscontinuities. IS all the channels.Difficult to gain insights in 2D (and beyond) due tohigh-dimensional nature of the third term.!67
Future DirectionsHow can we leverage more insights from this formulation?How we can use other statistical tools to represent variance?PCF is there but what else?Can we do better than traditional Importance Sampling?Integrand spaceRandom number 810-1010-12100!68101102103104105
Future DirectionsHow can we leverage more insights from this formulation?How we can use other statistical tools to represent variance?Can we do better than traditional Importance Sampling?Integrand spacePCF is there but what else?e.g., more for strata alignmentRandom number 810-1010-12100!69101102103104105
Thank you for your attention!Questions ?!70
Power Spectrum of Importance 00123Frequency714012Frequency34
Power Spectrum of Importance requency341.125000123Frequency72400.81.62.43.2
Fourier Analysis of Correlated Monte Carlo Importance Sampling Gurprit Singh Kartic Subr David Coeurjolly Victor Ostromoukhov Wojciech Jarosz. 2 Monte Carlo Integration!3 Monte Carlo Integration f( x) I Z 1 0 f( x)d x!4 Monte Carlo Estimator f( x) I N 1 N XN k 1 f( x k) p( x
Singh et al. / Fourier Analysis of Correlated Monte Carlo Importance Sampling duces favorable correlations by minimizing a measure known as dis-crepancy. Such low discrepancy sampling methods [Nie78,KPR12] and the resulting QMC estimators are considered state of the art in renderin
Volume 37 (2018), Number 4 pp. 1–18 COMPUTER GRAPHICS forum Fourier Analysis of Correlated Monte Carlo Importance Sampling: Supplementary document Gurprit Singh1;4 Kartic Subr2 David Coeurjolly3 Victor Ostromoukhov3 Wojciech Jarosz4 1Max-Planck Institute for Informatics, Saarbrücken, 2University of Edinburgh, UK, 3U
Gambar 5. Koefisien Deret Fourier untuk isyarat kotak diskret dengan (2N1 1) 5, dan (a) N 10, (b) N 20, dan (c) N 40. 1.2 Transformasi Fourier 1.2.1 Transformasi Fourier untuk isyarat kontinyu Sebagaimana pada uraian tentang Deret Fourier, fungsi periodis yang memenuhi persamaan (1) dapat dinyatakan dengan superposisi fungsi sinus dan kosinus.File Size: 568KB
The Markov Chain Monte Carlo Revolution Persi Diaconis Abstract The use of simulation for high dimensional intractable computations has revolutionized applied math-ematics. Designing, improving and understanding the new tools leads to (and leans on) fascinating mathematics, from representation theory through micro-local analysis. 1 IntroductionCited by: 343Page Count: 24File Size: 775KBAuthor: Persi DiaconisExplore furtherA simple introduction to Markov Chain Monte–Carlo .link.springer.comHidden Markov Models - Tutorial And Examplewww.tutorialandexample.comA Gentle Introduction to Markov Chain Monte Carlo for .machinelearningmastery.comMarkov Chain Monte Carlo Lecture Noteswww.stat.umn.eduA Zero-Math Introduction to Markov Chain Monte Carlo .towardsdatascience.comRecommended to you b
Quasi Monte Carlo has been developed. While the convergence rate of classical Monte Carlo (MC) is O(n¡1 2), the convergence rate of Quasi Monte Carlo (QMC) can be made almost as high as O(n¡1). Correspondingly, the use of Quasi Monte Carlo is increasing, especially in the areas where it most readily can be employed. 1.1 Classical Monte Carlo
Chapter 9 Correlated Errors. Learning Objectives Demonstrate the problem of correlated errors and its implications Conduct and interpret tests for correlated errors Correct for correlated errors using Newey and West’s e
straightforward. The Fourier transform and inverse Fourier transform formulas for functions f: Rn!C are given by f ( ) Z Rn f(x)e ix dx; 2Rn; f(x) (2ˇ) n Z Rn f ( )eix d ; x2Rn: Like in the case of Fourier series, also the Fourier transform can be de ned on a large class of generalized functions (the space of tempered
The American Revolution, 1763-1783 By Pauline Maier This essay excerpt is provided courtesy of the Gilder Lehrman Institute of American History. INDEPENDENCE The Seven Years’ War had left Great Britain with a huge debt by the standards of the day. Moreover, thanks in part to Pontiac’s Rebellion, a massive American Indian uprising in the territories won from France, the British decided to .
