On average case complexity of linear problems with noisy information

DOI10.1016/0885-064X(90)90007-ZzbMath0717.65119OpenAlexW2086055782MaRDI QIDQ2638754

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

Hilbert spaceBanach spaceoptimal algorithminformation-based complexitynoisy informationdiscrete white noiseaverage errorinformation operatorGaussian Borel measureoptimal average radius

Mathematics Subject Classification ID

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

Related Items

Learning Curves for Gaussian Process Regression: Approximations and Bounds ⋮ On the minimal cost of approximating linear problems based on information with deterministic noise ⋮ Function approximation and integration on the Wiener space with noisy data ⋮ Noisy information for linear problems in the asymptotic setting

Cites Work

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