dc.contributor.advisor Venkatapathi, Murugesan dc.contributor.author Arun, I dc.date.accessioned 2021-10-26T04:06:20Z dc.date.available 2021-10-26T04:06:20Z dc.date.submitted 2020 dc.identifier.uri https://etd.iisc.ac.in/handle/2005/5475 dc.description.abstract Sampling, estimation and integration in high dimensional continuous spaces is required in diverse areas ranging from modeling multi-particle physical systems and optimization to inference from data. When the number of independent parameters increases, analytical methods are not always tractable and numerical methods require exponentially increasing computational effort (NP-hardness). In the first and the major part of the thesis, we propose a general Monte Carlo sampling method to estimate n-volumes and integrals even over non-convex domains. Deterministic sampling methods such as the Quasi-Monte Carlo are very efficient when the integrand can be reduced to a function of a single effective variable. Similarly, the naive Monte Carlo is very effective when the independent variables are sampled uniformly over an n-orthotope (a rectangle for n=2, cuboid for n=3, etc.). In problems where some function defines the boundary of the domain or its membership, and in problems where the independent variables are sampled with an implicit probability distribution, correctly sampling the n-volume of the domain in itself amounts to be NP-hard in general. en_US Markov Chain Monte Carlo (MCMC) methods are suited for convex domains and scale as O(n^4) in samples required for the estimation of volume. The proposed n-sphere Monte Carlo (NSMC) method not only has lower computational complexity but also preserves the independence of the random samples making it well suited for parallel computing. The proposed method decomposes the estimated volume into volumes of weighted n-spheres, and these weights are trivially estimated by sampling the extents of the domain. While other methods typically scale well only for relatively smooth convex bodies, the performance of the proposed method is only dependent on the variance of the distribution of extents and is independent of the roughness and the convexity of the body. The required number of samples to estimate n-volumes scales linearly with the number of dimensions for a fixed distribution of extents, while the total computing effort scales quadratically. We show a straight-forward adaptation of this method for estimating arbitrary integrals. Even in the case of convex shapes which are not defined by a fixed distribution of extents, our numerical results show that the naive NSMC has significant advantages over MCMC for number of dimensions n < 100. But this approach has challenges with highly eccentric volumes given by tailed distributions, and the large front constants of the linear scaling in such cases can be reduced by an appropriate non-uniform importance sampling of the extents. The challenges in such a non-uniform sampling in high dimensional spaces are described along with the proposed solution. With this geometric importance sampling, we show that the O(n) scaling in samples can be achieved even for highly eccentric spheroids, where the tail of the distribution of extents contributes significant volume. Future work is aimed at demonstrating this favorable scaling in samples for other challenging shapes as well. In the second and minor part of the thesis, we propose a non-sampling method to compute functions of scalar random variables using their moments. This method, while restricted in applicability to simple functions, can be applied to augment the NSMC approach to integration and also provides semi-analytical expressions for evaluating the moments of functions of random variables. dc.language.iso en_US en_US dc.rights I grant Indian Institute of Science the right to archive and to make available my thesis or dissertation in whole or in part in all forms of media, now hereafter known. I retain all proprietary rights, such as patent rights. I also retain the right to use in future works (such as articles or books) all or part en_US of this thesis or dissertation dc.subject Monte Carlo method en_US dc.subject high dimensionality en_US dc.subject integral en_US dc.subject arbitrary bodies en_US dc.subject continuous spaces en_US dc.subject.classification Research Subject Categories::MATHEMATICS en_US dc.subject.classification Research Subject Categories::TECHNOLOGY en_US dc.title Algorithms for Estimating Integrals in High Dimensional Spaces en_US dc.type Thesis en_US dc.degree.name PhD en_US dc.degree.level Doctoral en_US dc.degree.grantor Indian Institute of Science en_US dc.degree.discipline Engineering en_US
﻿