On average case complexity of linear problems with noisy information

DOI10.1016/0885-064X(90)90007-ZMaRDI QIDQ2638754zbMATH OpenOpenAlexFDO

Authors Leszek Plaskota

Publication date 1990

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0885-064x(90)90007-z

zbMATH Keywords

average errorBanach spacediscrete white noiseGaussian Borel measureHilbert spaceinformation operatorinformation-based complexitynoisy informationoptimal algorithmoptimal average radius

Mathematics Subject Classification ID

Set functions and measures and integrals in infinite-dimensional spaces (Wiener measure, Gaussian measure, etc.) (28C20) Linear operator approximation theory (47A58) General theory of numerical analysis in abstract spaces (65J05) Complexity and performance of numerical algorithms (65Y20) Theory of error-correcting codes and error-detecting codes (94B99)

Recommendations

• Average complexity for linear problems in a model with varying information noise
• Optimal average case estimation in Hilbert norms
• Optimal algorithms for linear problems with Gaussian measures
• Average case optimality for linear problems
• Worst case complexity of problems with random information noise

Cites work

• A clock synchronization problem with random delays
• A comparison of GCV and GML for choosing the smoothing parameter in the generalized spline smoothing problem
• A Correspondence Between Bayesian Estimation on Stochastic Processes and Smoothing by Splines
• A note on the trade-off between sampling and quantization in signal processing
• Best approximation of functions specified with an error at a finite number of points
• Designs for Regression Problems with Correlated Errors
• Error bounds for derivative estimates based on spline smoothing of exact or noisy data
• Gaussian measures in Banach spaces
• scientific article; zbMATH DE number 4112013 (Why is no real title available?)
• scientific article; zbMATH DE number 3176492 (Why is no real title available?)
• scientific article; zbMATH DE number 3755545 (Why is no real title available?)
• scientific article; zbMATH DE number 44104 (Why is no real title available?)
• scientific article; zbMATH DE number 3583145 (Why is no real title available?)
• scientific article; zbMATH DE number 3601500 (Why is no real title available?)
• Information of varying cardinality
• On adaption with noisy information
• On the Regression Design Problem of Sacks and Ylvisaker
• Optimal Bayesian experimental design for linear models
• Optimal Estimation of Linear Operators in Hilbert Spaces from Inaccurate Data
• Optimality of central and projection algorithms for bounded uncertainty
• Optimum Designs in Regression Problems
• Smoothing by spline functions. II
• Smoothing noisy data with spline functions
• Smoothing noisy data with spline functions: Estimating the correct degree of smoothing by the method of generalized cross-validation
• Spline smoothing and optimal rates of convergence in nonparametric regression models
• When is the optimal regularization parameter insensitive to the choice of the loss function?

Cited in

(20)

• Approximation of linear functionals on a Banach space with a Gaussian measure
• Probabilistic setting of information-based complexity
• Complexity of approximation with relative error criterion in worst, average, and probabilistic settings
• Function approximation and integration on the Wiener space with noisy data
• Average case L_-approximation in the presence of Gaussian noise
• A note on varying cardinality in the average case setting
• Asymptotically tight worst case complexity bounds for initial-value problems with nonadaptive information
• Information-based nonlinear approximation: an average case setting
• Optimal approximation of linear operators based on noisy data on functionals
• Optimal average case estimation in Hilbert norms
• Average complexity for linear problems in a model with varying information noise
• Complexity of approximating Hölder classes from information with varying Gaussian noise
• Worst case complexity of problems with random information noise
• Noisy information: optimality, complexity, tractability
• On the minimal cost of approximating linear problems based on information with deterministic noise
• scientific article; zbMATH DE number 4112013 (Why is no real title available?)
• Learning Curves for Gaussian Process Regression: Approximations and Bounds
• Average complexity for linear operators over bounded domains
• Can adaption help on the average?
• Noisy information for linear problems in the asymptotic setting

This page was built for publication: On average case complexity of linear problems with noisy information

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2638754)