第5回　物理工学科教室談話会(講師：Prof. Yuji Nakatsukasa / 中務 佑治 氏)

---

概要：
Classical algorithms for numerical integration (quadrature/cubature) proceed by approximating the integrand with a simple function (e.g. a polynomial), and integrate the approximant exactly. In high-dimensional integration, such methods quickly become infeasible due to the curse of dimensionality.
A common alternative is the Monte Carlo method (MC), which simply takes the average of random samples, improving the estimate as more and more samples are taken. The main issue with MC is its slow “sqrt(variance/#samples)” convergence, and various techniques have been proposed to reduce the variance.
In this work we reveal a numerical analyst’s interpretation of MC: it approximates the integrand with a constant function, and integrates the constant exactly. This observation leads naturally to MC-like methods that combines MC with (high-dimensional) function approximation theory, including polynomial approximation, sparse grids and low-rank approximation. The resulting method can be regarded as another variance reduction technique for Monte Carlo. We also discuss methods that improve the approximation quality as more samples are taken, and thus can converge faster than 1/sqrt(#samples).
Talk will be in English.
ガウス積分を始めとする数値解析における古典的数値積分の方針は、被積分関数を多項式等で近似し、近似関数を厳密に積分する、というものである。1次元の積分では極めて有効であるが、高次元積分には「次元の呪い」を受け、計算量が次元と共に指数関数的に増加する。これに対し、モンテカルロ積分法は確率、統計学から生まれた乱択アルゴリズムであり、次元に依存しない収束性を持つという強い利点を持つ。しかし、1/sqrt(サンプル数)という収束性が遅いという問題点がある。本研究では、モンテカルロ積分の背景にも極めて単純な関数近似があることを観察する。これに基づいて、背景にある近似関数を改良することでモンテカルロ積分の収束も（時に大幅に）改良することができることを示す。多項式、スパースグリッドや低ランク近似等の関数近似論と、確率論やランダム行列理論を用い、数値積分とモンテカルロ積分の融合アルゴリズムを提案する。
紹介教員：山地 洋平 特任准教授、今田 正俊 教授（ともに物理工学専攻）