Complexity of multilinear problems in the average case setting

DOI10.1016/0885-064X(91)90047-2MaRDI QIDQ1174451zbMATH OpenOpenAlexFDO

Authors Tomasz Jackowski

Publication date 25 June 1992

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

Full work available at URL https://doi.org/10.1016/0885-064x(91)90047-2

zbMATH Keywords

algorithmaverage case settingaverage performanceBanach spacesHilbert spacemultilinear problemsspline algorithmsworst case setting

Mathematics Subject Classification ID

Numerical linear algebra (65F99) Numerical solutions to equations with linear operators (65J10) Complexity and performance of numerical algorithms (65Y20) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Communication theory (94A05) Information theory (general) (94A15) Communication, information (94A99)

Review text

This is the second part of studies on multilinear problems devoted to the average case setting. The first part [J. Complexity 6, No. 4, 389-408 (1990; Zbl 0712.94001)] deals with the worst case setting. Let \(F_ i\) \((i=1,\dots,k)\) and \(G\) be separable Banach spaces. Denote \(F:= F_ 1\times\cdots\times F_ k\). Let \(S: F\to G\) be a \(k\)-linear operator. The aim is to approximate \(Sf\) for \(f\in F\) knowing only certain information about \(f\). In the average case, \(F\) is equipped with some measure \(\mu\). The error and cost of an algorithm are defined by average performance with respect to \(\mu\). If \(G\) is a Hilbert space, then it is shown that the spline algorithms are optimal. If \(G\) is a Banach space, then the multilinear problem can be reduced to linear subproblems. Optimality properties of spline algorithms are established.

Recommendations

• Average case complexity of linear multivariate problems
• Average case complexity of linear multivariate problems. II: Applications
• Average case complexity of linear multivariate problems. I: Theory
• A survey of average case complexity for linear multivariate problems
• On the average complexity of multivariate problems
• Complexity of multilinear problems in the worst case setting
• Tractability of linear multivariate problems in the average case setting
• Average case tractability of a multivariate approximation problem
• Polynomial-time algorithms for multivariate linear problems with finite-order weights: Average case setting
• Quasi-polynomial tractability of linear problems in the average case setting

Cites work

• Approximation of linear functionals on a Banach space with a Gaussian measure
• Can adaption help on the average?
• Complexity of multilinear problems in the worst case setting
• Elliptically contoured measures on infinite-dimensional Banach spaces
• scientific article; zbMATH DE number 3688714 (Why is no real title available?)
• scientific article; zbMATH DE number 44104 (Why is no real title available?)
• scientific article; zbMATH DE number 3245885 (Why is no real title available?)
• On the average complexity of multivariate problems
• Orthogonally invariant measures and best approximation of linear operators

Cited in

(10)

• Polynomial-time algorithms for multivariate linear problems with finite-order weights: Average case setting
• Average case tractability of a multivariate approximation problem
• Average case complexity of linear multivariate problems
• lnκ-weak tractability of general multivariate problems in the average case setting
• Average-case lower bounds for the plurality problem
• Complexity of multilinear problems in the worst case setting
• Information-based complexity: New questions for mathematicians
• On the average complexity of multivariate problems
• Average case optimality for linear problems
• Average-case complexity of the min-sum matrix product problem

This page was built for publication: Complexity of multilinear problems in the average case setting

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