Journal
SIAM-ASA JOURNAL ON UNCERTAINTY QUANTIFICATION
Volume 3, Issue 1, Pages 61-90Publisher
SIAM PUBLICATIONS
DOI: 10.1137/14096311X
Keywords
randomized algorithms; inverse problems; Monte Carlo methods; trace estimation; gamma random variable; extremal probability; large scale simulation
Funding
- NSERC [84306]
Ask authors/readers for more resources
This paper considers stochastic algorithms for efficiently solving a class of large scale nonlinear least squares (NLS) problems which frequently arise in applications. We propose eight variants of a practical randomized algorithm where the uncertainties in the major stochastic steps are quantified. Such stochastic steps involve approximating the NLS objective function using Monte Carlo methods, and this is equivalent to the estimation of the trace of corresponding symmetric positive semidefinite matrices. For the latter, we prove tight necessary and sufficient conditions on the sample size (which translates to cost) to satisfy the prescribed probabilistic accuracy. We show that these conditions are practically computable and yield small sample sizes. They are then incorporated in our stochastic algorithm to quantify the uncertainty in each randomized step. The bounds we use are applications of more general results regarding extremal tail probabilities of linear combinations of gamma distributed random variables. We derive and prove new results concerning the maximal and minimal tail probabilities of such linear combinations, which can be considered independently of the rest of this paper.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available