Linear vs. nonlinear algorithms for linear problems

DOI10.1016/j.jco.2004.05.003zbMath1086.41017OpenAlexW1974621481MaRDI QIDQ706787

Jakob Creutzig, Przemysław Wojtaszczyk

Publication date: 9 February 2005

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

Full work available at URL: https://doi.org/10.1016/j.jco.2004.05.003

zbMATH Keywords

normed spaceslinear and non-linear approximation

Mathematics Subject Classification ID

Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) Multidimensional problems (41A63)

Related Items

Random sections of ellipsoids and the power of random information, Uniform recovery of high-dimensional \(C^r\)-functions, Computing a quantity of interest from observational data, Sampling numbers of smoothness classes via \(\ell^1\)-minimization, Some Results on the Complexity of Numerical Integration, Exponential tractability of \(L_2\)-approximation with function values, Approximation numbers of Sobolev embeddings-sharp constants and tractability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• s-numbers in information-based complexity
• Are linear algorithms always good for linear problems?
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Linear problems (with extended range) have linear optimal algorithms
• Deterministic and stochastic error bounds in numerical analysis
• Relations between some constants associated with finite dimensional Banach spaces
• Finite dimensional subspaces of $L_{p}$
• On the extension property for compact operators