Do Linear Problems Have Linear Optimal Algorithms?

DOI10.1137/1030091MaRDI QIDQ3357652zbMATH OpenOpenAlexFDO

Authors Edward W. Packel

Publication date 1988

Published in SIAM Review (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1030091

zbMATH Keywords

information-based complexityexampleslinear optimal algorithms

Mathematics Subject Classification ID

Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) Approximation by arbitrary linear expressions (41A45) Normed linear spaces and Banach spaces; Banach lattices (46B99) Numerical solutions to equations with linear operators (65J10)

Recommendations

• scientific article; zbMATH DE number 139625
• Are linear algorithms always good for linear problems?
• Recent developments in information-based complexity
• Some issues in the theory of optimal algorithms and informational complexity
• Average case optimality for linear problems

Cited in

(14)

• Linearity of algorithms and a result of Ando
• The algorithm designer versus nature: A game-theoretic approach to information-based complexity
• Mini-minimax uncertainty quantification for emulators
• Recent developments in information-based complexity
• Are linear algorithms always good for linear problems?
• There exists a linear problem with infinite combinatory complexity
• Full recovery from point values: an optimal algorithm for Chebyshev approximability prior
• scientific article; zbMATH DE number 822135 (Why is no real title available?)
• Learning from non-random data in Hilbert spaces: an optimal recovery perspective
• scientific article; zbMATH DE number 139625 (Why is no real title available?)
• Can linear superiorization be useful for linear optimization problems?
• Radius of information for two intersected centered hyperellipsoids and implications in optimal recovery from inaccurate data
• scientific article; zbMATH DE number 446839 (Why is no real title available?)
• Optimal residual algorithms for linear operator equations

This page was built for publication: Do Linear Problems Have Linear Optimal Algorithms?

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