Advanced Courses in Mathematics CRM Barcelona Dinh D ng Vladimir Temlyakov Tino Ullrich Hyperbolic Cross Approximation Advanced Courses in Mathematics CRM Barcelona Centre de Recerca Matemàtica Managing Editor: Enric Ventura More information about this series at http://www.springer.com/series/5038 Dinh D(cid:458)ng • Vladimir Temlyakov • Tino Ullrich Hyperbolic Cross Approximation Editor for this volume: Sergey Tikhonov, Centre de Recerca Matemàtica Dinh D(cid:458)ng Vladimir Temlyakov Information Technology Institute Department of Mathematics Vietnam National University University of South Carolina Hanoi, Vietnam Columbia, SC, USA and Tino Ullrich Faculty of Mathematics Steklov Institute of Mathematics and Technical University of Chemnitz Lomonosov Moscow State University 09126 Chemnitz, Germany Moscow, Russia ISSN 2297-0304 ISSN 2297-0312 (electronic) Advanced Courses in Mathematics - CRM Barcelona ISBN 978-3-319-92239-3 ISBN 978-3-319-92240-9 (eBook) https://doi.org/10.1007/978-3-319-92240-9 Library of Congress Control Number: 2018958719 Mathematics Subject Classification (2010): 41A15, 41A17, 41A46, 41A63, 42A05, 42A10, 42B05, 42B25, 42B99, 65D30, 65D32 © Springer Nature Switzerland AG 2018 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broad- casting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. This book is published under the imprint Birkhäuser, www.birkhauser-science.com by the registered company Springer Nature Switzerland AG. The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland Contents Foreword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Trigonometric Polynomials. . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.1 Univariate polynomials . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Multivariate polynomials . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 Hyperbolic cross polynomials . . . . . . . . . . . . . . . . . . . . 21 2.4 The Bernstein–Nikol’skii inequalities . . . . . . . . . . . . . . . . 24 2.5 Volume estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.6 Riesz products and the small ball inequality . . . . . . . . . . . . 31 2.7 Comments and open problems . . . . . . . . . . . . . . . . . . . . 33 3 Function Spaces on Td . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.1 Spaces of functions with bounded mixed derivative . . . . . . . . 35 3.2 Spaces of functions with bounded mixed difference . . . . . . . . 37 3.3 Characterizationvia Fourier transform . . . . . . . . . . . . . . . 39 3.4 Embeddings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4 Linear Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.2 Approximation by the hyperbolic cross polynomials . . . . . . . . 48 4.3 The Kolmogorovwidths . . . . . . . . . . . . . . . . . . . . . . . 54 4.4 Orthowidths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.5 The linear widths . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.6 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5 Sampling Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.1 The univariate de la Vall´ee Poussin interpolation . . . . . . . . . 75 5.2 Frequency-limited sampling representations – discrete Littlewood–Paley . . . . . . . . . . . . . . . . . . . . . . 77 5.3 Sampling on the Smolyak grids . . . . . . . . . . . . . . . . . . . 79 5.4 Sampling widths . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 v vi Contents 5.5 Time-limited sampling representations B-splines . . . . . . . . . . 87 5.6 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6 Entropy Numbers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 6.1 General notions and inequalities . . . . . . . . . . . . . . . . . . . 95 6.2 Entropy numbers for W classes in L . . . . . . . . . . . . . . . . 99 q 6.3 Entropy numbers for H and B classes in L . . . . . . . . . . . . 102 q 6.4 Entropy numbers and the small ball problem . . . . . . . . . . . 104 6.5 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 7 Best m-Term Approximation . . . . . . . . . . . . . . . . . . . . . . . . 107 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 7.2 Orthogonal bases . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 7.3 Some related problems . . . . . . . . . . . . . . . . . . . . . . . . 113 7.4 A comment on Stechkin’s lemma . . . . . . . . . . . . . . . . . . 114 7.5 Sparse trigonometric approximation . . . . . . . . . . . . . . . . 116 7.6 Different types of greedy algorithms . . . . . . . . . . . . . . . . 124 7.7 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 8 Numerical Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 8.1 The problem setting . . . . . . . . . . . . . . . . . . . . . . . . . 127 8.2 Lower bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 8.3 Cubature on Smolyak grids . . . . . . . . . . . . . . . . . . . . . 130 8.4 The Fibonacci cubature formulas . . . . . . . . . . . . . . . . . . 132 8.5 The Frolov cubature formulas . . . . . . . . . . . . . . . . . . . . 134 8.6 Modifications of Frolov’s method . . . . . . . . . . . . . . . . . . 138 8.7 Quasi Monte Carlo cubature . . . . . . . . . . . . . . . . . . . . . 140 8.8 Discrepancy and numerical integration . . . . . . . . . . . . . . . 143 8.9 Open problems and historical comments . . . . . . . . . . . . . . 150 9 Related Problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 9.1 Why classes with mixed smoothness? . . . . . . . . . . . . . . . . 153 9.2 Universality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 9.3 Further generalizations . . . . . . . . . . . . . . . . . . . . . . . . 158 9.4 Direct and inverse theorems . . . . . . . . . . . . . . . . . . . . . 159 9.5 Kolmogorovwidths of the intersection of function classes . . . . . 159 9.6 Further s-numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 161 9.7 The quasi Banach situation . . . . . . . . . . . . . . . . . . . . . 164 9.8 Sampling along lattices . . . . . . . . . . . . . . . . . . . . . . . . 167 9.9 Sampling recovery in energy norm . . . . . . . . . . . . . . . . . 168 9.10 Continuous algorithms in m-term approximation and nonlinear widths . . . . . . . . . . . . . . . . . . . . . . . . . 169 Contents vii 10 High-Dimensional Approximation. . . . . . . . . . . . . . . . . . . . . . 171 10.1 Anisotropic mixed smoothness. . . . . . . . . . . . . . . . . . . . 171 10.2 Explicit constants and preasymptotics . . . . . . . . . . . . . . . 173 10.3 Approximation in the energy norm . . . . . . . . . . . . . . . . . 175 10.4 ε-dimension and approximation in infinite dimensions. . . . . . . 176 11 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 11.1 General notation . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 11.2 Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 11.3 Duality in L spaces . . . . . . . . . . . . . . . . . . . . . . . . . 183 p 11.4 Fourier series of functions in L . . . . . . . . . . . . . . . . . . . 184 p Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 Foreword This book contains expository lecture notes for the course given at the Advanced CoursesonConstructiveApproximationandHarmonicAnalysis,whichtookplace in the Centre de Recerca Matem`atica (CRM) in Bellaterra(Barcelona)May 30th to June 3th, 2016.These courseswereone ofthe mainactivities ofthe five-month Research Programme on Approximation Theory and Fourier Analysis. Expanded versions of the lectures “Hyperbolic Cross Approximation” given byVladimirTemlyakov(UniversityofSouthCarolina)andTinoUllrich(Technical University of Chemnitz,Germany)are presented here. We gather a survey on multivariate approximation. The 20th century was a period of transition from univariate problems to multivariate problems in a number of areas of mathematics. For instance, it is a step from Gaussian sums to Weil’s sums in number theory, a step from ordinary differential equations to PDEs, a step from univariate trigonometric series to multivariate trigonometric seriesinharmonicanalysis,astepfromquadratureformulastocubatureformulas in numerical integration, a step from univariate function classes to multivariate functionclassesinapproximationtheory.Inmanycasesthisstepbroughtnotonly new phenomena but also required new techniques to handle the corresponding multivariateproblems.Insomecasesevenaformulationofamultivariateproblem requiresa nontrivialmodification ofa univariate problem. Forinstance, the prob- lemofconvergenceofthemultivariatetrigonometricseriesimmediatelyencounters aquestionofwhichpartialsums weshouldconsider–there isno naturalordering in the multivariate case. In other words: What is a natural multivariate analog of the univariate trigonometric polynomials? Answering this questionmathemati- ciansstudieddifferentgeneralizationsoftheunivariatetrigonometricpolynomials: with frequencies from a ball, a cube or, most importantly, a hyperbolic cross. Results discussedin this survey demonstratethat polynomials with frequen- cies from hyperbolic crosses play the same role in the multivariate approximation astheunivariatetrigonometricpolynomialsplayintheapproximationoffunctions onasinglevariable.Resultsobtainedinthemultivariateapproximationtheoryfor thelast50yearsestablishedadeepconnectionbetweentrigonometricpolynomials with frequencies from the hyperbolic crossesand classes of functions defined with the help ofeither mixed derivativesormixeddifferences. The importance ofthese classes was understood in the beginning of the 1960s. The multivariate problems ix x Foreword of hyperbolic cross approximation turn out to be much more involved than their univariate counterparts. Approximation of classes of functions with bounded mixed derivative and functions with a restriction on mixed differences have been developed following classical tradition. A systematic study of different asymptotic characteristics of these classes dates back to the beginning of the 1960s. In the book the authors considerboth linear approximationproblems – the problems of approximationby elementsofagivenfinite-dimensionallinearsubspaceandnonlinearapproximation problems. They discuss a number of the most important asymptotic characteris- tics related to the linear approximation. In addition to the Kolmogorov n-width, the authors also study the asymptotic behavior of the linear widths and the or- thowidths.Inthe definitionoflinearwidthweallowalllinearoperatorsofrankm to compete in the minimization problem.Clearly, we wouldlike to workwith nice andsimple linear operators.This idea motivated researchersto impose additional restrictions on the linear operators in the definitions of the corresponding modifi- cationsofthe linearwidth. Oneverynaturalrestrictionisthatthe approximating rank m operator is an orthogonal projection operator. This leads to the concept ofthe orthowidth(Fourier width). Another natural restrictionis that the approx- imating rank m operator is a recovering operator, which uses function values at m points. Recently, driven by applications in engineering, biology, medicine and other areas of science, nonlinear approximation began to play an important role. Non- linear approximation is important in applications because of its concise represen- tations and increased computational efficiency. In the book the authors discuss a typicalproblemofnonlinearapproximation–them-termapproximation.Another name for m-term approximation is sparse approximation. Discretizationisaveryimportantstepinmakingacontinuousproblemcom- putationallyfeasible.Theproblemofconstructionofgoodsetsofpointsinamulti- dimensionaldomainisafundamental problemofmathematicsandcomputational mathematics. Aprominentexampleofclassicaldiscretizationproblemisaproblemofmet- ricentropy(coveringnumbers,entropynumbers).Theauthorsdiscussthisproblem in detail. Bounds for the entropy of function classes are important by themselves andalsohaveimportantconnectionstootherfundamentalproblems.Forinstance, theproblemoftheentropyofsomeclassesoffunctionswithboundedmixedderiva- tive is equivalent to the fundamental small ball problem from probability theory. Another prominent example of a discretization problem, which is discussed in the book, is the problem of numerical integration. It turns out that contrary to the numerical integrationin the univariate case and in the multivariate case of the anisotropic smoothness classes, where regular grids methods are optimal (in the sense of order), in the case of numerical integration of functions with mixed smoothnessthe regulargrids methods are veryfar frombeing optimal. Numerical integration in the mixed smoothness classes requires deep number theoretical re-