Probabilistic setting of information-based complexity
type: Item
instance of: scholarly article
title: Probabilistic setting of information-based complexity
zbMATH Open document ID: 0627.68040
DOI: 10.1016/0885-064X(86)90005-1
published in: Journal of Complexity
publication date: 1986-01-01T00:00:00Z
review text: We study the probabilistic (\(\epsilon\),\(\delta)\)-complexity for linear problems equipped with Gaussian measures. The probabilistic (\(\epsilon\),\(\delta)\)-complexity, \(comp^{prob}(\epsilon,\delta)\), is understood as the minimal cost required to compute approximations with error at most \(\epsilon\) on a set of measure at least 1-\(\delta\). We find estimates of \(comp^{prob}(\epsilon,\delta)\) in terms of eigenvalues of the correlation operator of the Gaussian measure over elements which we want to approximate. In particular, we study the approximation and integration problems.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 65D15
Mathematics Subject Classification ID: 65D30
zbMATH DE Number: 4020477
zbMATH Keywords: probabilistic epsilon-delta complexity
zbMATH Keywords: Gaussian measures
zbMATH Keywords: approximation
zbMATH Keywords: integration
author: H. Woźniakowski
MaRDI profile type: Publication
cites work: Gaussian measures in Banach spaces
cites work: Approximation of linear functionals on a Banach space with a Gaussian measure
cites work: On the average complexity of multivariate problems
cites work: Q5533878
cites work: Q4042533
cites work: Q3938928
cites work: Some nonlinear problems are as easy as the approximation problem
cites work: Information of varying cardinality
full work available at URL: 0885-064x(86)90005-1
OpenAlex ID: W2149205277
description: scientific article; zbMATH DE number 4020477