A~survey of average case complexity for linear multivariate problems

G. W. Wasilkowski ; H. Woźniakowski

Izvestiâ vysših učebnyh zavedenij. Matematika, no. 4 (2009), pp. 3-19.

Résumé

We survey recent results on the average case complexity for linear multivariate problems. Our emphasis is on problems defined on spaces of functions of $d$ variables with large $d$. We present the sharp order of the average case complexity for a number of linear multivariate problems as well as necessary and sufficient conditions for the average case complexity not to be exponential in $d$.

Détail

Keywords: average case setting, minimal error, Wiener measure, complexity, Hilbert space, linear nultivariate problem, Wiener sheet, Banach space, tractability, tensor product, weighted approximation.

Bibliographie

[1] Aronszajn N., “Theory of reproducing kernels”, Trans. Amer. Math. Soc., 68 (1950), 337–404 | DOI | MR | Zbl

[2] Beck J., Chen W. W., Irregularities of distributions, Cambridge Tracts in Mathematics, 89, Cambridge University Press, 1987, xiv+294 pp. | MR | Zbl

[3] Chazelle B., The discrepancy method: randomness and complexity, Cambridge Univ. Press, 2002 | MR

[4] Ciesielski Z., “On Lévy's Brownian motion with several-dimensional time”, Lect. Notes Math., 472, Springer, 1975, 29–56 | MR

[5] Dobkin D. P., Mitchell D. P., “Random-edge discrepancy of suppersampling patterns”, Graphics Interface' 93, York, Ontario, 1993, 62–69

[6] Drmota M., Tichy R. F., Sequences, discrepancies and applications, Lect. Notes Math., 1651, Springer-Verlag, Berlin, 1997, xiii+503 pp. | MR | Zbl

[7] Hickernell F. J., Wasilkowski G. W., Woźniakowski H., “Tractability of linear multivariate problems in the average case setting”, Monte Carlo and Quasi-Monte Carlo Methods 2006, Springer, 2008, 461–494

[8] Hickernell F. J., Woźniakowski H., “Integration and approximation in arbitrary dimension”, Advances in Comput. Math., 12 (2000), 25–58 | DOI | MR | Zbl

[9] Hinrichs A., Novak E., Vybiral J., “Linear information versus function evaluations for $L_2$-approximation”, J. Approx. Theory (to appear) | MR

[10] Kimeldorf G. S., Wahba G., “A correspondence between Bayesian estimation on stochastic processes and smoothing by splines”, Ann. Math. Stat., 41 (1970), 495–502 | DOI | MR | Zbl

[11] Kimeldorf G. S., Wahba G., “Spline functions and stochastic processes”, Sankhya Ser. A, 32 (1970), 173–180 | MR | Zbl

[12] Kuo F. Y., Wasilkowski G. W., Woźniakowski H., “Multivariate $L_\infty$ approximation in the worst case setting over reproducing kernel Hilbert spaces”, J. Approx. Theory, 152 (2008), 135–160 | DOI | MR | Zbl

[13] Kuo F. Y., Wasilkowski G. W., Woźniakowski H., “On the power of standard information for multivariate approximation in the worst case setting”, J. Approx. Theory (to appear)

[14] Larkin F. M., “Gaussian measure in Hilbert space and application in numerical analysis”, Rocky Mount. J. Math., 2 (1972), 372–421 | MR

[15] Lévy P., Processus stochastique et mouvement Brownien, Gauthier-Villars, Paris, 1948, 365 pp. | MR | Zbl

[16] Li Y., “Applicability of Smolyak's algorithm to certain Banach spaces of multivariate functions”, J. Complexity, 18 (2002), 792–814 | DOI | MR | Zbl

[17] Matoušek J., Geometric discrepancy, Algorithms and Combinatorics, 18, Springer-Verlag, 1999, 288 pp. | MR | Zbl

[18] Micchelli C. A., Wahba G., “Design problems for optimal surface interpolation”, Approximation Theory and Applic., Academic Press, New York, 1981, 329–347 | MR

[19] von Mises R., “Zur mechanischen Quadratur”, Z. Angew. Math. Mech., 13 (1933), 53–56 | DOI | Zbl

[20] Molchan G. M., “O nekotorykh zadachakh, svyazannykh s brounovskim dvizheniem Levi”, Teor. veroyatn. i ee primenen., 12:4 (1967), 747–755 | Zbl

[21] Niederreiter H., Random number generation and quasi-Monte Carlo methods, CBMS-NSF Reg. Conf. Series Appl. Math., 63, SIAM, Philadelphia, PA, 1992 | MR | Zbl

[22] Novak E., Deterministic and stochastic error bounds in numerical analysis, Lect. Notes Math., 1349, Springer, 1988, 113 pp. | MR | Zbl

[23] Novak E., Woźniakowski H., “Intractability results for integration and discrepancy”, J. Complexity, 17 (2001), 388–441 | DOI | MR | Zbl

[24] Novak E., Woźniakowski H., Tractability of multivariate problems, EMS Tracts in Mathematics, 6, European Math. Society, Zürich, 2008 | MR | Zbl

[25] Papageorgiou A., Wasilkowski G. W., “On the average case complexity of multivariate problems”, J. Complexity, 6 (1990), 1–23 | DOI | MR | Zbl

[26] Paskov S., “Average case complexity of multivariate integration for smooth functions”, J. Complexity, 9 (1993), 291–321 | DOI | MR

[27] Plaskota L., “A note on varying cardinality in the average case setting”, J. Complexity, 9 (1993), 458–470 | DOI | MR | Zbl

[28] Plaskota L., Noisy information and computational complexity, Cambridge Univ. Press, Cambridge, 1996 | MR | Zbl

[29] Plaskota L., Ritter K., Wasilkowski G. W., “Average case complexity of weighted approximation and integration over $\mathbb R_+$”, J. Complexity, 18 (2002), 517–544 | DOI | MR | Zbl

[30] Plaskota L., Ritter K., Wasilkowski G. W., “Average case complexity of weighted integration and approximation over $\mathbb R^d$ for isotropic weight”, Monte Carlo and Quasi-Monte Carlo Methods 2000, Springer, 2002, 446–459 | MR | Zbl

[31] Ritter K., Average-case analysis of numerical problems, Lect. Notes Math., 1733, Springer, 2000, 254 pp. | MR | Zbl

[32] Ritter K., Wasilkowski G. W., “Integration and $L_2$-approximation: average case complexity with isotropic Wiener measure for smooth functions”, Rocky Mountain J. Math., 26 (1997), 1541–1557 | DOI | MR

[33] Ritter K., Wasilkowski G. W., “On the average case complexity of solving Poisson equations”, Lect. in Appl. Math., 32, 1996, 677–687 | MR | Zbl

[34] Ritter K., Wasilkowski G. W., Woźniakowski H., “On multivariate integration for stochastic processes”, Numerical integration, IV, International Series on Numer. Math., 112, Birkhäuser, Basel, 1993, 331–347 | MR | Zbl

[35] Ritter K., Wasilkowski G. W., Woźniakowski H., “Multivariate integration and approximation for random fields satisfying Sacks–Ylvisaker conditions”, Ann. Appl. Probability, 5 (1995), 518–540 | DOI | MR | Zbl

[36] Sacks J., Ylvisaker D., “Design for regression problems with correlated errors. III”, Ann. Math. Stat., 41 (1970), 2057–2074 | DOI | MR | Zbl

[37] Sacks J., Ylvisaker D., “Statistical design and integral approximation”, Proc. 12th Bienn. Semin. Can. Math. Congr., 1970, 115–136 | MR | Zbl

[38] Sloan I. H., Joe S., Lattice methods for multiple integration, Oxford University Press, 1994 | MR | Zbl

[39] Smolyak S. A., “Kvadraturnye i interpolyatsionnye formuly na tenzornykh proizvedeniyakh nekotorykh klassov funktsii”, DAN SSSR, 148:5 (1963), 1042–1045 | Zbl

[40] Suldin A. V., “Mera Vinera i ee prilozheniya k priblizhennym formulam. I”, Izv. vuzov. Matematika, 1959, no. 6, 145–158 | MR

[41] Suldin A. V., “Mera Vinera i ee prilozheniya k priblizhennym formulam. II”, Izv. vuzov. Matematika, 1960, no. 5, 165–179 | MR

[42] Tezuka S., Uniform random numbers: theory and practice, Kluwer Academic Publishers, Boston, 1995 | Zbl

[43] Traub J. F., Wasilkowski G. W., Woźniakowski H., “Average case optimality for linear problems”, J. Theor. Comput. Sci., 29 (1984), 1–24 | DOI | MR

[44] Traub J. F., Wasilkowski G. W., Woźniakowski H., Information-based complexity, Academic Press, New York, 1988 | MR | Zbl

[45] Wahba G., “On the regression design problem of Sacks and Ylvisaker”, Ann. Math. Stat., 42 (1971), 1035–1043 | DOI | MR

[46] Wahba G., Spline models for observational data, CBMS-NSF Regional Conference Series in Appl. Math., 59, SIAM, Philadelphia, PA, 1990 | MR | Zbl

[47] Wasilkowski G. W., “Information of varying cardinality”, J. Complexity, 2 (1986), 204–228 | DOI | MR | Zbl

[48] Wasilkowski G. W., “Optimal algorithms for linear problems with Gaussian measures”, Rocky Mount. J. Math., 16 (1986), 727–749 | MR | Zbl

[49] Wasilkowski G. W., “Integration and approximation of multivariate functions: average case complexity with isotropic Wiener measure”, Bull. Amer. Math. Soc., 28 (1993), 308–314 ; Full version: J. Approx. Theory, 77 (1994), 212–227 | DOI | MR | Zbl | DOI | MR | Zbl

[50] Wasilkowski G. W., Gao F., “On the power of adaptive information for functions with singularities”, Math. Comp., 58 (1992), 285–304 | DOI | MR | Zbl

[51] Wasilkowski G. W., Woźniakowski H., “Can adaption help to the average?”, Numer. Math., 44 (1984), 169–190 | DOI | MR | Zbl

[52] Wasilkowski G. W., Woźniakowski H., “Explicit cost bounds for multivariate tensor product problems”, J. Complexity, 11 (1995), 1–56 | DOI | MR | Zbl

[53] Wasilkowski G. W., Woźniakowski H., “Weighted tensor-product algorithms for linear multivariate problems”, J. Complexity, 15 (1999), 402–447 | DOI | MR | Zbl

[54] Wasilkowski G. W., Woźniakowski H., “Finite-order weights imply tractability of linear multivariate problems”, J. Approx. Theory, 130 (2004), 57–77 | DOI | MR | Zbl

[55] Wasilkowski G. W., Woźniakowski H., Polynomial-time algorithms for multivariate problems with finite-order weights; average case setting, Foundations of Computational Mathematics, 2008 (to appear)

[56] Woźniakowski H., “Average case complexity of multivariate integration”, Bull. Amer. Math. Soc., 24 (1991), 185–194 | DOI | MR | Zbl

[57] Woźniakowski H., “Average case complexity of linear multivariate problems. Part 1: Theory”, J. Complexity, 8 (1992), 337–372 ; “Average case complexity of linear multivariate problems. Part 2: Applications”, 373–392 | DOI | MR | Zbl | MR | Zbl

[58] Ylvisaker D., “Designs on random fields”, Survey of Statistical Design and Linear Models, North-Holland, Amsterdam, 1975, 593–607 | MR