Search | arXiv e-print repository

<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"/> <meta name="viewport" content="width=device-width, initial-scale=1"/>  <link rel="apple-touch-icon" sizes="180x180" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/apple-touch-icon.png"> <link rel="icon" type="image/png" sizes="32x32" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon-32x32.png"> <link rel="icon" type="image/png" sizes="16x16" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon-16x16.png"> <link rel="manifest" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/site.webmanifest"> <link rel="mask-icon" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/safari-pinned-tab.svg" color="#b31b1b"> <link rel="shortcut icon" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon.ico"> <meta name="msapplication-TileColor" content="#b31b1b"> <meta name="msapplication-config" content="images/icons/browserconfig.xml"> <meta name="theme-color" content="#b31b1b">  <title>Search | arXiv e-print repository</title> <script defer src="https://static.arxiv.org/static/base/1.0.0a5/fontawesome-free-5.11.2-web/js/all.js"></script> <link rel="stylesheet" href="https://static.arxiv.org/static/base/1.0.0a5/css/arxivstyle.css" /> <script type="text/x-mathjax-config"> MathJax.Hub.Config({ messageStyle: "none", extensions: ["tex2jax.js"], jax: ["input/TeX", "output/HTML-CSS"], tex2jax: { inlineMath: [ ['$','$'], ["\$","\$"] ], displayMath: [ ['$$','$$'], ["\\[","\\]"] ], processEscapes: true, ignoreClass: '.*', processClass: 'mathjax.*' }, TeX: { extensions: ["AMSmath.js", "AMSsymbols.js", "noErrors.js"], noErrors: { inlineDelimiters: ["$","$"], multiLine: false, style: { "font-size": "normal", "border": "" } } }, "HTML-CSS": { availableFonts: ["TeX"] } }); </script> <script src='//static.arxiv.org/MathJax-2.7.3/MathJax.js'></script> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/notification.js"></script> <link rel="stylesheet" href="https://static.arxiv.org/static/search/0.5.6/css/bulma-tooltip.min.css" /> <link rel="stylesheet" href="https://static.arxiv.org/static/search/0.5.6/css/search.css" /> <script src="https://code.jquery.com/jquery-3.2.1.slim.min.js" integrity="sha256-k2WSCIexGzOj3Euiig+TlR8gA0EmPjuc79OEeY5L45g=" crossorigin="anonymous"></script> <script src="https://static.arxiv.org/static/search/0.5.6/js/fieldset.js"></script> <style> radio#cf-customfield_11400 { display: none; } </style> </head> <body> <header><a href="#main-container" class="is-sr-only">Skip to main content</a>  <div class="attribution level is-marginless" role="banner"> <div class="level-left"> <a class="level-item" href="https://cornell.edu/"><img src="https://static.arxiv.org/static/base/1.0.0a5/images/cornell-reduced-white-SMALL.svg" alt="Cornell University" width="200" aria-label="logo" /></a> </div> <div class="level-right is-marginless"><p class="sponsors level-item is-marginless"><span id="support-ack-url">We gratefully acknowledge support from<br /> the Simons Foundation, <a href="https://info.arxiv.org/about/ourmembers.html">member institutions</a>, and all contributors. <a href="https://info.arxiv.org/about/donate.html">Donate</a></span></p></div> </div>  <div class="identity level is-marginless"> <div class="level-left"> <div class="level-item"> <a class="arxiv" href="https://arxiv.org/" aria-label="arxiv-logo"> <img src="https://static.arxiv.org/static/base/1.0.0a5/images/arxiv-logo-one-color-white.svg" aria-label="logo" alt="arxiv logo" width="85" style="width:85px;"/> </a> </div> </div> <div class="search-block level-right"> <form class="level-item mini-search" method="GET" action="https://arxiv.org/search"> <div class="field has-addons"> <div class="control"> <input class="input is-small" type="text" name="query" placeholder="Search..." aria-label="Search term or terms" /> <p class="help"><a href="https://info.arxiv.org/help">Help</a> | <a href="https://arxiv.org/search/advanced">Advanced Search</a></p> </div> <div class="control"> <div class="select is-small"> <select name="searchtype" aria-label="Field to search"> <option value="all" selected="selected">All fields</option> <option value="title">Title</option> <option value="author">Author</option> <option value="abstract">Abstract</option> <option value="comments">Comments</option> <option value="journal_ref">Journal reference</option> <option value="acm_class">ACM classification</option> <option value="msc_class">MSC classification</option> <option value="report_num">Report number</option> <option value="paper_id">arXiv identifier</option> <option value="doi">DOI</option> <option value="orcid">ORCID</option> <option value="author_id">arXiv author ID</option> <option value="help">Help pages</option> <option value="full_text">Full text</option> </select> </div> </div> <input type="hidden" name="source" value="header"> <button class="button is-small is-cul-darker">Search</button> </div> </form> </div> </div>  <div class="container"> <div class="user-tools is-size-7 has-text-right has-text-weight-bold" role="navigation" aria-label="User menu"> <a href="https://arxiv.org/login">Login</a> </div> </div> </header> <main class="container" id="main-container"> <div class="level is-marginless"> <div class="level-left"> <h1 class="title is-clearfix"> Showing 1–48 of 48 results for author: <span class="mathjax">Ullrich, M</span> </h1> </div> <div class="level-right is-hidden-mobile">  <span class="help" style="display: inline-block;"><a href="https://github.com/arXiv/arxiv-search/releases">Search v0.5.6 released 2020-02-24</a>  </span> </div> </div> <div class="content"> <form method="GET" action="/search/math" aria-role="search"> Searching in archive <strong>math</strong>. <a href="/search/?searchtype=author&query=Ullrich%2C+M">Search in all archives.</a> <div class="field has-addons-tablet"> <div class="control is-expanded"> <label for="query" class="hidden-label">Search term or terms</label> <input class="input is-medium" id="query" name="query" placeholder="Search term..." type="text" value="Ullrich, M"> </div> <div class="select control is-medium"> <label class="is-hidden" for="searchtype">Field</label> <select class="is-medium" id="searchtype" name="searchtype"><option value="all">All fields</option><option value="title">Title</option><option selected value="author">Author(s)</option><option value="abstract">Abstract</option><option value="comments">Comments</option><option value="journal_ref">Journal reference</option><option value="acm_class">ACM classification</option><option value="msc_class">MSC classification</option><option value="report_num">Report number</option><option value="paper_id">arXiv identifier</option><option value="doi">DOI</option><option value="orcid">ORCID</option><option value="license">License (URI)</option><option value="author_id">arXiv author ID</option><option value="help">Help pages</option><option value="full_text">Full text</option></select> </div> <div class="control"> <button class="button is-link is-medium">Search</button> </div> </div> <div class="field"> <div class="control is-size-7"> <label class="radio"> <input checked id="abstracts-0" name="abstracts" type="radio" value="show"> Show abstracts </label> <label class="radio"> <input id="abstracts-1" name="abstracts" type="radio" value="hide"> Hide abstracts </label> </div> </div> <div class="is-clearfix" style="height: 2.5em"> <div class="is-pulled-right"> <a href="/search/advanced?terms-0-term=Ullrich%2C+M&terms-0-field=author&size=50&order=-announced_date_first">Advanced Search</a> </div> </div> <input type="hidden" name="order" value="-announced_date_first"> <input type="hidden" name="size" value="50"> </form> <div class="level breathe-horizontal"> <div class="level-left"> <form method="GET" action="/search/"> <div style="display: none;"> <select id="searchtype" name="searchtype"><option value="all">All fields</option><option value="title">Title</option><option selected value="author">Author(s)</option><option value="abstract">Abstract</option><option value="comments">Comments</option><option value="journal_ref">Journal reference</option><option value="acm_class">ACM classification</option><option value="msc_class">MSC classification</option><option value="report_num">Report number</option><option value="paper_id">arXiv identifier</option><option value="doi">DOI</option><option value="orcid">ORCID</option><option value="license">License (URI)</option><option value="author_id">arXiv author ID</option><option value="help">Help pages</option><option value="full_text">Full text</option></select> <input id="query" name="query" type="text" value="Ullrich, M"> <ul id="abstracts"><li><input checked id="abstracts-0" name="abstracts" type="radio" value="show"> <label for="abstracts-0">Show abstracts</label></li><li><input id="abstracts-1" name="abstracts" type="radio" value="hide"> <label for="abstracts-1">Hide abstracts</label></li></ul> </div> <div class="box field is-grouped is-grouped-multiline level-item"> <div class="control"> <span class="select is-small"> <select id="size" name="size"><option value="25">25</option><option selected value="50">50</option><option value="100">100</option><option value="200">200</option></select> </span> <label for="size">results per page</label>. </div> <div class="control"> <label for="order">Sort results by</label> <span class="select is-small"> <select id="order" name="order"><option selected value="-announced_date_first">Announcement date (newest first)</option><option value="announced_date_first">Announcement date (oldest first)</option><option value="-submitted_date">Submission date (newest first)</option><option value="submitted_date">Submission date (oldest first)</option><option value="">Relevance</option></select> </span> </div> <div class="control"> <button class="button is-small is-link">Go</button> </div> </div> </form> </div> </div> <ol class="breathe-horizontal" start="1"> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2412.06468">arXiv:2412.06468</a> <span> [<a href="https://arxiv.org/pdf/2412.06468">pdf</a>, <a href="https://arxiv.org/ps/2412.06468">ps</a>, <a href="https://arxiv.org/format/2412.06468">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> How many continuous measurements are needed to learn a vector? </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Krieg%2C+D">David Krieg</a>, <a href="/search/math?searchtype=author&query=Novak%2C+E">Erich Novak</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2412.06468v1-abstract-short" style="display: inline;"> One can recover vectors from $\mathbb{R}^m$ with arbitrary precision, using only $\lceil \log_2(m+1)\rceil +1$ continuous measurements that are chosen adaptively. This surprising result is explained and discussed, and we present applications to infinite-dimensional approximation problems. </span> <span class="abstract-full has-text-grey-dark mathjax" id="2412.06468v1-abstract-full" style="display: none;"> One can recover vectors from $\mathbb{R}^m$ with arbitrary precision, using only $\lceil \log_2(m+1)\rceil +1$ continuous measurements that are chosen adaptively. This surprising result is explained and discussed, and we present applications to infinite-dimensional approximation problems. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2412.06468v1-abstract-full').style.display = 'none'; document.getElementById('2412.06468v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 9 December, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">12 pages</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2406.07108">arXiv:2406.07108</a> <span> [<a href="https://arxiv.org/pdf/2406.07108">pdf</a>, <a href="https://arxiv.org/ps/2406.07108">ps</a>, <a href="https://arxiv.org/format/2406.07108">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Functional Analysis">math.FA</span> </div> </div> <p class="title is-5 mathjax"> On the power of adaption and randomization </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Krieg%2C+D">David Krieg</a>, <a href="/search/math?searchtype=author&query=Novak%2C+E">Erich Novak</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2406.07108v1-abstract-short" style="display: inline;"> We present bounds between different widths of convex subsets of Banach spaces, including Gelfand and Bernstein widths. Using this, and some relations between widths and minimal errors, we obtain bounds on the maximal gain of adaptive and randomized algorithms over non-adaptive, deterministic ones for approximating linear operators on convex sets. Our results also apply to the approximation of embe… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2406.07108v1-abstract-full').style.display = 'inline'; document.getElementById('2406.07108v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2406.07108v1-abstract-full" style="display: none;"> We present bounds between different widths of convex subsets of Banach spaces, including Gelfand and Bernstein widths. Using this, and some relations between widths and minimal errors, we obtain bounds on the maximal gain of adaptive and randomized algorithms over non-adaptive, deterministic ones for approximating linear operators on convex sets. Our results also apply to the approximation of embeddings into the space of bounded functions based on function evaluations, i.e., to sampling recovery in the uniform norm. We conclude with a list of open problems. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2406.07108v1-abstract-full').style.display = 'none'; document.getElementById('2406.07108v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 11 June, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2405.05509">arXiv:2405.05509</a> <span> [<a href="https://arxiv.org/pdf/2405.05509">pdf</a>, <a href="https://arxiv.org/ps/2405.05509">ps</a>, <a href="https://arxiv.org/format/2405.05509">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Functional Analysis">math.FA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Operator Algebras">math.OA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1007/s43036-024-00386-x">10.1007/s43036-024-00386-x <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Inequalities between s-numbers </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2405.05509v2-abstract-short" style="display: inline;"> Singular numbers of operators between Hilbert spaces were generalized to Banach spaces by s-numbers (in the sense of Pietsch). This allows for different choices, including approximation, Gelfand, Kolmogorov and Bernstein numbers. Here, we present an elementary proof of a bound between the smallest and the largest s-number. </span> <span class="abstract-full has-text-grey-dark mathjax" id="2405.05509v2-abstract-full" style="display: none;"> Singular numbers of operators between Hilbert spaces were generalized to Banach spaces by s-numbers (in the sense of Pietsch). This allows for different choices, including approximation, Gelfand, Kolmogorov and Bernstein numbers. Here, we present an elementary proof of a bound between the smallest and the largest s-number. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.05509v2-abstract-full').style.display = 'none'; document.getElementById('2405.05509v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 14 October, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 8 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">6 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 47B06; Secondary 46B50; 47B01 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Advances in Operator Theory 9:82 (2024) </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2401.02220">arXiv:2401.02220</a> <span> [<a href="https://arxiv.org/pdf/2401.02220">pdf</a>, <a href="https://arxiv.org/ps/2401.02220">ps</a>, <a href="https://arxiv.org/format/2401.02220">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Functional Analysis">math.FA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> </div> <p class="title is-5 mathjax"> Sampling projections in the uniform norm </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Krieg%2C+D">David Krieg</a>, <a href="/search/math?searchtype=author&query=Pozharska%2C+K">Kateryna Pozharska</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+T">Tino Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2401.02220v1-abstract-short" style="display: inline;"> We show that there are sampling projections on arbitrary $n$-dimensional subspaces of $B(D)$ with at most $2n$ samples and norm of order $\sqrt{n}$, where $B(D)$ is the space of complex-valued bounded functions on a set $D$. This gives a more explicit form of the Kadets-Snobar theorem for the uniform norm and improves upon Auerbach's lemma. We discuss consequences for optimal recovery in $L_p$. </span> <span class="abstract-full has-text-grey-dark mathjax" id="2401.02220v1-abstract-full" style="display: none;"> We show that there are sampling projections on arbitrary $n$-dimensional subspaces of $B(D)$ with at most $2n$ samples and norm of order $\sqrt{n}$, where $B(D)$ is the space of complex-valued bounded functions on a set $D$. This gives a more explicit form of the Kadets-Snobar theorem for the uniform norm and improves upon Auerbach's lemma. We discuss consequences for optimal recovery in $L_p$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2401.02220v1-abstract-full').style.display = 'none'; document.getElementById('2401.02220v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 4 January, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 41A65 (Primary) 41A50; 46B09 (Secondary) </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2310.12740">arXiv:2310.12740</a> <span> [<a href="https://arxiv.org/pdf/2310.12740">pdf</a>, <a href="https://arxiv.org/ps/2310.12740">ps</a>, <a href="https://arxiv.org/format/2310.12740">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.30970/ana.2023.1.88">10.30970/ana.2023.1.88 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> On the power of iid information for linear approximation </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Sonnleitner%2C+M">Mathias Sonnleitner</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2310.12740v2-abstract-short" style="display: inline;"> This survey is concerned with the power of random information for approximation in the (deterministic) worst-case setting, with special emphasis on information consisting of functionals selected independently and identically distributed (iid) at random on a class of admissible information functionals. We present a general result based on a weighted least squares method and derive consequences for… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2310.12740v2-abstract-full').style.display = 'inline'; document.getElementById('2310.12740v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2310.12740v2-abstract-full" style="display: none;"> This survey is concerned with the power of random information for approximation in the (deterministic) worst-case setting, with special emphasis on information consisting of functionals selected independently and identically distributed (iid) at random on a class of admissible information functionals. We present a general result based on a weighted least squares method and derive consequences for special cases. Improvements are available if the information is ``Gaussian'' or if we consider iid function values for Sobolev spaces. We include open questions to guide future research on the power of random information in the context of information-based complexity. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2310.12740v2-abstract-full').style.display = 'none'; document.getElementById('2310.12740v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 8 January, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 19 October, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">63 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 65-02; 41A25; 47B06; 68Q25; 94A20 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> JANA 1 (2023) 88-126 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2305.07539">arXiv:2305.07539</a> <span> [<a href="https://arxiv.org/pdf/2305.07539">pdf</a>, <a href="https://arxiv.org/ps/2305.07539">ps</a>, <a href="https://arxiv.org/format/2305.07539">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </div> </div> <p class="title is-5 mathjax"> Sampling recovery in $L_2$ and other norms </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Krieg%2C+D">David Krieg</a>, <a href="/search/math?searchtype=author&query=Pozharska%2C+K">Kateryna Pozharska</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+T">Tino Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2305.07539v3-abstract-short" style="display: inline;"> We study the recovery of functions in various norms, including $L_p$ with $1\le p\le\infty$, based on function evaluations. We obtain worst case error bounds for general classes of functions in terms of the best $L_2$-approximation from a given nested sequence of subspaces and the Christoffel function of these subspaces. In the case $p=\infty$, our results imply that linear sampling algorithms are… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.07539v3-abstract-full').style.display = 'inline'; document.getElementById('2305.07539v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2305.07539v3-abstract-full" style="display: none;"> We study the recovery of functions in various norms, including $L_p$ with $1\le p\le\infty$, based on function evaluations. We obtain worst case error bounds for general classes of functions in terms of the best $L_2$-approximation from a given nested sequence of subspaces and the Christoffel function of these subspaces. In the case $p=\infty$, our results imply that linear sampling algorithms are optimal up to a constant factor for many reproducing kernel Hilbert spaces. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.07539v3-abstract-full').style.display = 'none'; document.getElementById('2305.07539v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 1 November, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 12 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">The title has changed slightly. Some results from earlier versions are shifted to another publication</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 68Q25; 41A50; 46B09; 41A63; 47B06 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2205.04141">arXiv:2205.04141</a> <span> [<a href="https://arxiv.org/pdf/2205.04141">pdf</a>, <a href="https://arxiv.org/ps/2205.04141">ps</a>, <a href="https://arxiv.org/format/2205.04141">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1007/s10444-023-10021-7">10.1007/s10444-023-10021-7 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Exponential tractability of $L_2$-approximation with function values </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Krieg%2C+D">David Krieg</a>, <a href="/search/math?searchtype=author&query=Siedlecki%2C+P">Pawel Siedlecki</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a>, <a href="/search/math?searchtype=author&query=Wo%C5%BAniakowski%2C+H">Henryk Wo藕niakowski</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2205.04141v2-abstract-short" style="display: inline;"> We study the complexity of high-dimensional approximation in the $L_2$-norm when different classes of information are available; we compare the power of function evaluations with the power of arbitrary continuous linear measurements. Here, we discuss the situation when the number of linear measurements required to achieve an error $\varepsilon \in (0,1)$ in dimension $d\in\mathbb{N}$ depends only… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2205.04141v2-abstract-full').style.display = 'inline'; document.getElementById('2205.04141v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2205.04141v2-abstract-full" style="display: none;"> We study the complexity of high-dimensional approximation in the $L_2$-norm when different classes of information are available; we compare the power of function evaluations with the power of arbitrary continuous linear measurements. Here, we discuss the situation when the number of linear measurements required to achieve an error $\varepsilon \in (0,1)$ in dimension $d\in\mathbb{N}$ depends only poly-logarithmically on $\varepsilon^{-1}$. This corresponds to an exponential order of convergence of the approximation error, which often happens in applications. However, it does not mean that the high-dimensional approximation problem is easy, the main difficulty usually lies within the dependence on the dimension $d$. We determine to which extent the required amount of information changes, if we allow only function evaluation instead of arbitrary linear information. It turns out that in this case we only lose very little, and we can even restrict to linear algorithms. In particular, several notions of tractability hold simultaneously for both types of available information. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2205.04141v2-abstract-full').style.display = 'none'; document.getElementById('2205.04141v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 22 March, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 9 May, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2022. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 65Y20; 41A25; 41A65; 41A63 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Adv Comput Math 49, 18 (2023) </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2204.12621">arXiv:2204.12621</a> <span> [<a href="https://arxiv.org/pdf/2204.12621">pdf</a>, <a href="https://arxiv.org/ps/2204.12621">ps</a>, <a href="https://arxiv.org/format/2204.12621">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Functional Analysis">math.FA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1016/j.acha.2022.12.001">10.1016/j.acha.2022.12.001 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> A sharp upper bound for sampling numbers in $L_{2}$ </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Dolbeault%2C+M">Matthieu Dolbeault</a>, <a href="/search/math?searchtype=author&query=Krieg%2C+D">David Krieg</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2204.12621v2-abstract-short" style="display: inline;"> For a class $F$ of complex-valued functions on a set $D$, we denote by $g_n(F)$ its sampling numbers, i.e., the minimal worst-case error on $F$, measured in $L_2$, that can be achieved with a recovery algorithm based on $n$ function evaluations. We prove that there is a universal constant $c\in\mathbb{N}$ such that, if $F$ is the unit ball of a separable reproducing kernel Hilbert space, then \[ g… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2204.12621v2-abstract-full').style.display = 'inline'; document.getElementById('2204.12621v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2204.12621v2-abstract-full" style="display: none;"> For a class $F$ of complex-valued functions on a set $D$, we denote by $g_n(F)$ its sampling numbers, i.e., the minimal worst-case error on $F$, measured in $L_2$, that can be achieved with a recovery algorithm based on $n$ function evaluations. We prove that there is a universal constant $c\in\mathbb{N}$ such that, if $F$ is the unit ball of a separable reproducing kernel Hilbert space, then \[ g_{cn}(F)^2 \,\le\, \frac{1}{n}\sum_{k\geq n} d_k(F)^2, \] where $d_k(F)$ are the Kolmogorov widths (or approximation numbers) of $F$ in $L_2$. We also obtain similar upper bounds for more general classes $F$, including all compact subsets of the space of continuous functions on a bounded domain $D\subset \mathbb{R}^d$, and show that these bounds are sharp by providing examples where the converse inequality holds up to a constant. The results rely on the solution to the Kadison-Singer problem, which we extend to the subsampling of a sum of infinite rank-one matrices. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2204.12621v2-abstract-full').style.display = 'none'; document.getElementById('2204.12621v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 9 December, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 26 April, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2022. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 41A25; 41A45; 46B09; 46B15; 60B20 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Appl. Comput. Harmon. Anal. 63 (2023), 113 pp </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2011.01779">arXiv:2011.01779</a> <span> [<a href="https://arxiv.org/pdf/2011.01779">pdf</a>, <a href="https://arxiv.org/ps/2011.01779">ps</a>, <a href="https://arxiv.org/format/2011.01779">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1016/j.jco.2021.101569">10.1016/j.jco.2021.101569 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Function values are enough for $L_2$-approximation: Part II </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Krieg%2C+D">David Krieg</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2011.01779v2-abstract-short" style="display: inline;"> In the first part we have shown that, for $L_2$-approximation of functions from a separable Hilbert space in the worst-case setting, linear algorithms based on function values are almost as powerful as arbitrary linear algorithms if the approximation numbers are square-summable. That is, they achieve the same polynomial rate of convergence. In this sequel, we prove a similar result for separable B… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2011.01779v2-abstract-full').style.display = 'inline'; document.getElementById('2011.01779v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2011.01779v2-abstract-full" style="display: none;"> In the first part we have shown that, for $L_2$-approximation of functions from a separable Hilbert space in the worst-case setting, linear algorithms based on function values are almost as powerful as arbitrary linear algorithms if the approximation numbers are square-summable. That is, they achieve the same polynomial rate of convergence. In this sequel, we prove a similar result for separable Banach spaces and other classes of functions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2011.01779v2-abstract-full').style.display = 'none'; document.getElementById('2011.01779v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 11 March, 2021; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 3 November, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2020. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">18 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 41A25; 41A45; 41A65; 60B20; 41A63 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> J. Complexity 66 (2021), nr. 101569 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2003.11947">arXiv:2003.11947</a> <span> [<a href="https://arxiv.org/pdf/2003.11947">pdf</a>, <a href="https://arxiv.org/ps/2003.11947">ps</a>, <a href="https://arxiv.org/format/2003.11947">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1016/j.jco.2020.101484">10.1016/j.jco.2020.101484 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> On the worst-case error of least squares algorithms for $L_2$-approximation with high probability </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2003.11947v1-abstract-short" style="display: inline;"> It was recently shown in [4] that, for $L_2$-approximation of functions from a Hilbert space, function values are almost as powerful as arbitrary linear information, if the approximation numbers are square-summable. That is, we showed that \[ e_n \,\lesssim\, \sqrt{\frac{1}{k_n} \sum_{j\geq k_n} a_j^2} \qquad \text{ with }\quad k_n \asymp \frac{n}{\ln(n)}, \] where $e_n$ are the sampling numbers… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2003.11947v1-abstract-full').style.display = 'inline'; document.getElementById('2003.11947v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2003.11947v1-abstract-full" style="display: none;"> It was recently shown in [4] that, for $L_2$-approximation of functions from a Hilbert space, function values are almost as powerful as arbitrary linear information, if the approximation numbers are square-summable. That is, we showed that \[ e_n \,\lesssim\, \sqrt{\frac{1}{k_n} \sum_{j\geq k_n} a_j^2} \qquad \text{ with }\quad k_n \asymp \frac{n}{\ln(n)}, \] where $e_n$ are the sampling numbers and $a_k$ are the approximation numbers. In particular, if $(a_k)\in\ell_2$, then $e_n$ and $a_n$ are of the same polynomial order. For this, we presented an explicit (weighted least squares) algorithm based on i.i.d. random points and proved that this works with positive probability. This implies the existence of a good deterministic sampling algorithm. Here, we present a modification of the proof in [4] that shows that the same algorithm works with probability at least $1-{n^{-c}}$ for all $c>0$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2003.11947v1-abstract-full').style.display = 'none'; document.getElementById('2003.11947v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 24 March, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2020. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">7 pages. arXiv admin note: substantial text overlap with arXiv:1905.02516</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 41A25; 41A46; 60B20 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> J. Complexity 60 (2020) </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1908.04658">arXiv:1908.04658</a> <span> [<a href="https://arxiv.org/pdf/1908.04658">pdf</a>, <a href="https://arxiv.org/ps/1908.04658">ps</a>, <a href="https://arxiv.org/format/1908.04658">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> </div> <p class="title is-5 mathjax"> On the fixed volume discrepancy of the Fibonacci sets in the integral norms </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Temlyakov%2C+V">Vladimir Temlyakov</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1908.04658v1-abstract-short" style="display: inline;"> This paper is devoted to the study of a discrepancy-type characteristic -- the fixed volume discrepancy -- of the Fibonacci point set in the unit square. It was observed recently that this new characteristic allows us to obtain optimal rate of dispersion from numerical integration results. This observation motivates us to thoroughly study this new version of discrepancy, which seems to be interest… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1908.04658v1-abstract-full').style.display = 'inline'; document.getElementById('1908.04658v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1908.04658v1-abstract-full" style="display: none;"> This paper is devoted to the study of a discrepancy-type characteristic -- the fixed volume discrepancy -- of the Fibonacci point set in the unit square. It was observed recently that this new characteristic allows us to obtain optimal rate of dispersion from numerical integration results. This observation motivates us to thoroughly study this new version of discrepancy, which seems to be interesting by itself. The new ingredient of this paper is the use of the average over the shifts of hat functions instead of taking the supremum over the shifts. We show that this change in the setting results in an improvement of the upper bound for the smooth fixed volume discrepancy, similarly to the well-known results for the usual $L_p$-discrepancy. Interestingly, this shows that ``bad boxes'' for the usual discrepancy cannot be ``too small''. The known results on smooth discrepancy show that the obtained bounds cannot be improved in a certain sense. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1908.04658v1-abstract-full').style.display = 'none'; document.getElementById('1908.04658v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 13 August, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 2019. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">12 pages</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1905.02516">arXiv:1905.02516</a> <span> [<a href="https://arxiv.org/pdf/1905.02516">pdf</a>, <a href="https://arxiv.org/ps/1905.02516">ps</a>, <a href="https://arxiv.org/format/1905.02516">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1007/s10208-020-09481-w">10.1007/s10208-020-09481-w <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Function values are enough for $L_2$-approximation </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Krieg%2C+D">David Krieg</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1905.02516v5-abstract-short" style="display: inline;"> We study the $L_2$-approximation of functions from a Hilbert space and compare the sampling numbers with the approximation numbers. The sampling number $e_n$ is the minimal worst case error that can be achieved with $n$ function values, whereas the approximation number $a_n$ is the minimal worst case error that can be achieved with $n$ pieces of arbitrary linear information (like derivatives or Fo… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1905.02516v5-abstract-full').style.display = 'inline'; document.getElementById('1905.02516v5-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1905.02516v5-abstract-full" style="display: none;"> We study the $L_2$-approximation of functions from a Hilbert space and compare the sampling numbers with the approximation numbers. The sampling number $e_n$ is the minimal worst case error that can be achieved with $n$ function values, whereas the approximation number $a_n$ is the minimal worst case error that can be achieved with $n$ pieces of arbitrary linear information (like derivatives or Fourier coefficients). We show that \[ e_n \,\lesssim\, \sqrt{\frac{1}{k_n} \sum_{j\geq k_n} a_j^2}, \] where $k_n \asymp n/\log(n)$. This proves that the sampling numbers decay with the same polynomial rate as the approximation numbers and therefore that function values are basically as powerful as arbitrary linear information if the approximation numbers are square-summable. Our result applies, in particular, to Sobolev spaces $H^s_{\rm mix}(\mathbb{T}^d)$ with dominating mixed smoothness $s>1/2$ and we obtain \[ e_n \,\lesssim\, n^{-s} \log^{sd}(n). \] For $d>2s+1$, this improves upon all previous bounds and disproves the prevalent conjecture that Smolyak's (sparse grid) algorithm is optimal. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1905.02516v5-abstract-full').style.display = 'none'; document.getElementById('1905.02516v5-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 8 October, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 7 May, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2019. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">12 pages, accepted for publication in Foundations of Computational Mathematics</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 41A25; 41A46; 60B20; 41A63; 46E35 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Found. Comput. Math. 21 (2021), 1141-1151 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1903.00681">arXiv:1903.00681</a> <span> [<a href="https://arxiv.org/pdf/1903.00681">pdf</a>, <a href="https://arxiv.org/ps/1903.00681">ps</a>, <a href="https://arxiv.org/format/1903.00681">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> </div> </div> <p class="title is-5 mathjax"> On the power of random information </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Hinrichs%2C+A">Aicke Hinrichs</a>, <a href="/search/math?searchtype=author&query=Krieg%2C+D">David Krieg</a>, <a href="/search/math?searchtype=author&query=Novak%2C+E">Erich Novak</a>, <a href="/search/math?searchtype=author&query=Prochno%2C+J">Joscha Prochno</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1903.00681v1-abstract-short" style="display: inline;"> We study approximation and integration problems and compare the quality of optimal information with the quality of random information. For some problems random information is almost optimal and for some other problems random information is much worse than optimal information. We prove new results and give a short survey of known results. </span> <span class="abstract-full has-text-grey-dark mathjax" id="1903.00681v1-abstract-full" style="display: none;"> We study approximation and integration problems and compare the quality of optimal information with the quality of random information. For some problems random information is almost optimal and for some other problems random information is much worse than optimal information. We prove new results and give a short survey of known results. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1903.00681v1-abstract-full').style.display = 'none'; document.getElementById('1903.00681v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 2 March, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2019. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">20 pages</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1901.06702">arXiv:1901.06702</a> <span> [<a href="https://arxiv.org/pdf/1901.06702">pdf</a>, <a href="https://arxiv.org/ps/1901.06702">ps</a>, <a href="https://arxiv.org/format/1901.06702">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> </div> <p class="title is-5 mathjax"> Deterministic constructions of high-dimensional sets with small dispersion </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a>, <a href="/search/math?searchtype=author&query=Vyb%C3%ADral%2C+J">Jan Vyb铆ral</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1901.06702v1-abstract-short" style="display: inline;"> The dispersion of a point set $P\subset[0,1]^d$ is the volume of the largest box with sides parallel to the coordinate axes, which does not intersect $P$. Here, we show a construction of low-dispersion point sets, which can be deduced from solutions of certain $k$-restriction problems, which are well-known in coding theory. It was observed only recently that, for any $\varepsilon>0$, certain ran… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.06702v1-abstract-full').style.display = 'inline'; document.getElementById('1901.06702v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1901.06702v1-abstract-full" style="display: none;"> The dispersion of a point set $P\subset[0,1]^d$ is the volume of the largest box with sides parallel to the coordinate axes, which does not intersect $P$. Here, we show a construction of low-dispersion point sets, which can be deduced from solutions of certain $k$-restriction problems, which are well-known in coding theory. It was observed only recently that, for any $\varepsilon>0$, certain randomized constructions provide point sets with dispersion smaller than $\varepsilon$ and number of elements growing only logarithmically in $d$. Based on deep results from coding theory, we present explicit, deterministic algorithms to construct such point sets in time that is only polynomial in $d$. Note that, however, the running-time will be super-exponential in $\varepsilon^{-1}$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.06702v1-abstract-full').style.display = 'none'; document.getElementById('1901.06702v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 20 January, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2019. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1901.06639">arXiv:1901.06639</a> <span> [<a href="https://arxiv.org/pdf/1901.06639">pdf</a>, <a href="https://arxiv.org/ps/1901.06639">ps</a>, <a href="https://arxiv.org/format/1901.06639">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Functional Analysis">math.FA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Metric Geometry">math.MG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1090/tran/8502">10.1090/tran/8502 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Random sections of ellipsoids and the power of random information </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Hinrichs%2C+A">Aicke Hinrichs</a>, <a href="/search/math?searchtype=author&query=Krieg%2C+D">David Krieg</a>, <a href="/search/math?searchtype=author&query=Novak%2C+E">Erich Novak</a>, <a href="/search/math?searchtype=author&query=Prochno%2C+J">Joscha Prochno</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1901.06639v2-abstract-short" style="display: inline;"> We study the circumradius of the intersection of an $m$-dimensional ellipsoid $\mathcal E$ with semi-axes $蟽_1\geq\dots\geq 蟽_m$ with random subspaces of codimension $n$. We find that, under certain assumptions on $蟽$, this random radius $\mathcal{R}_n=\mathcal{R}_n(蟽)$ is of the same order as the minimal such radius $蟽_{n+1}$ with high probability. In other situations $\mathcal{R}_n$ is close to… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.06639v2-abstract-full').style.display = 'inline'; document.getElementById('1901.06639v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1901.06639v2-abstract-full" style="display: none;"> We study the circumradius of the intersection of an $m$-dimensional ellipsoid $\mathcal E$ with semi-axes $蟽_1\geq\dots\geq 蟽_m$ with random subspaces of codimension $n$. We find that, under certain assumptions on $蟽$, this random radius $\mathcal{R}_n=\mathcal{R}_n(蟽)$ is of the same order as the minimal such radius $蟽_{n+1}$ with high probability. In other situations $\mathcal{R}_n$ is close to the maximum $蟽_1$. The random variable $\mathcal{R}_n$ naturally corresponds to the worst-case error of the best algorithm based on random information for $L_2$-approximation of functions from a compactly embedded Hilbert space $H$ with unit ball $\mathcal E$. In particular, $蟽_k$ is the $k$th largest singular value of the embedding $H\hookrightarrow L_2$. In this formulation, one can also consider the case $m=\infty$, and we prove that random information behaves very differently depending on whether $蟽\in \ell_2$ or not. For $蟽\notin \ell_2$ random information is completely useless, i.e., $\mathbb E[\mathcal{R}_n] = 蟽_1$. For $蟽\in \ell_2$ the expected radius of random information tends to zero at least at rate $o(1/\sqrt{n})$ as $n\to\infty$. In the important case $蟽_k \asymp k^{-伪} \ln^{-尾}(k+1)$, where $伪> 0$ and $尾\in\mathbb R$, we obtain that $$ \mathbb E [\mathcal{R}_n(蟽)] \asymp \begin{cases} 蟽_1 & : 伪<1/2 \,\text{ or }\, 尾\leq伪=1/2 \\ 蟽_n \, \sqrt{\ln(n+1)} & : 尾>伪=1/2 \\ 蟽_{n+1} & : 伪>1/2. \end{cases} $$ In the proofs we use a comparison result for Gaussian processes 脿 la Gordon, exponential estimates for sums of chi-squared random variables, and estimates for the extreme singular values of (structured) Gaussian random matrices. The upper bound is constructive. It is proven for the worst case error of a least squares estimator. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.06639v2-abstract-full').style.display = 'none'; document.getElementById('1901.06639v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 9 April, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 20 January, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2019. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">25 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> Primary: 42B35; 52A23; 65Y20 Secondary: 65D15; 60B20; 60G15 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Trans. Amer. Math. Soc. 374 (2021), no. 12, 8691-8713 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1812.05300">arXiv:1812.05300</a> <span> [<a href="https://arxiv.org/pdf/1812.05300">pdf</a>, <a href="https://arxiv.org/ps/1812.05300">ps</a>, <a href="https://arxiv.org/format/1812.05300">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Analysis of PDEs">math.AP</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1137/120886984">10.1137/120886984 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Monotonicity based shape reconstruction in electrical impedance tomography </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Harrach%2C+B">Bastian Harrach</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Marcel Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1812.05300v1-abstract-short" style="display: inline;"> Current-voltage measurements in electrical impedance tomography can be partially ordered with respect to definiteness of the associated self-adjoint Neumann-to-Dirichlet operators (NtD). With this ordering, a point-wise larger conductivity leads to smaller current-voltage measurements, and smaller conductivities lead to larger measurements. We present a converse of this simple monotonicity relat… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1812.05300v1-abstract-full').style.display = 'inline'; document.getElementById('1812.05300v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1812.05300v1-abstract-full" style="display: none;"> Current-voltage measurements in electrical impedance tomography can be partially ordered with respect to definiteness of the associated self-adjoint Neumann-to-Dirichlet operators (NtD). With this ordering, a point-wise larger conductivity leads to smaller current-voltage measurements, and smaller conductivities lead to larger measurements. We present a converse of this simple monotonicity relation and use it to solve the shape reconstruction (aka inclusion detection) problem in EIT. The outer shape of a region where the conductivity differs from a known background conductivity can be found by simply comparing the measurements to that of smaller or larger test regions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1812.05300v1-abstract-full').style.display = 'none'; document.getElementById('1812.05300v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 13 December, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2018. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 35R30; 35Q60; 35J25; 35R05 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> SIAM J. Math. Anal. 45 (6), 3382-3403, 2013 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1811.06774">arXiv:1811.06774</a> <span> [<a href="https://arxiv.org/pdf/1811.06774">pdf</a>, <a href="https://arxiv.org/ps/1811.06774">ps</a>, <a href="https://arxiv.org/format/1811.06774">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Analysis of PDEs">math.AP</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1109/TMI.2015.2404133">10.1109/TMI.2015.2404133 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Resolution Guarantees in Electrical Impedance Tomography </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Harrach%2C+B">Bastian Harrach</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Marcel Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1811.06774v1-abstract-short" style="display: inline;"> Electrical impedance tomography (EIT) uses current-voltage measurements on the surface of an imaging subject to detect conductivity changes or anomalies. EIT is a promising new technique with great potential in medical imaging and non-destructive testing. However, in many applications, EIT suffers from inconsistent reliability due to its enormous sensitivity to modeling and measurement errors. I… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1811.06774v1-abstract-full').style.display = 'inline'; document.getElementById('1811.06774v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1811.06774v1-abstract-full" style="display: none;"> Electrical impedance tomography (EIT) uses current-voltage measurements on the surface of an imaging subject to detect conductivity changes or anomalies. EIT is a promising new technique with great potential in medical imaging and non-destructive testing. However, in many applications, EIT suffers from inconsistent reliability due to its enormous sensitivity to modeling and measurement errors. In this work we show that rigorous resolution guarantees are possible within a realistic EIT measurement setting including systematic and random errors. We derive a constructive criterion to decide whether a desired resolution can be achieved in a given measurement setup. Our result covers the detection of anomalies of a known minimal contrast using noisy measurements on a number of electrodes attached to a subject with imprecisely known background conductivity. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1811.06774v1-abstract-full').style.display = 'none'; document.getElementById('1811.06774v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 16 November, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2018. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> IEEE Trans. Med. Imaging 34(7), 1513-1521, 2015 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1810.05834">arXiv:1810.05834</a> <span> [<a href="https://arxiv.org/pdf/1810.05834">pdf</a>, <a href="https://arxiv.org/ps/1810.05834">ps</a>, <a href="https://arxiv.org/format/1810.05834">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Analysis of PDEs">math.AP</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1090/proc/12991">10.1090/proc/12991 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Local uniqueness for an inverse boundary value problem with partial data </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Harrach%2C+B">Bastian Harrach</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Marcel Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1810.05834v1-abstract-short" style="display: inline;"> In dimension $n\geq 3$, we prove a local uniqueness result for the potentials $q$ of the Schr枚dinger equation $-螖u+qu=0$ from partial boundary data. More precisely, we show that potentials $q_1,q_2\in L^\infty$ with positive essential infima can be distinguished by local boundary data if there is a neighborhood of a boundary part where $q_1\geq q_2$ and $q_1\not\equiv q_2$. </span> <span class="abstract-full has-text-grey-dark mathjax" id="1810.05834v1-abstract-full" style="display: none;"> In dimension $n\geq 3$, we prove a local uniqueness result for the potentials $q$ of the Schr枚dinger equation $-螖u+qu=0$ from partial boundary data. More precisely, we show that potentials $q_1,q_2\in L^\infty$ with positive essential infima can be distinguished by local boundary data if there is a neighborhood of a boundary part where $q_1\geq q_2$ and $q_1\not\equiv q_2$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1810.05834v1-abstract-full').style.display = 'none'; document.getElementById('1810.05834v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 13 October, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2018. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 35J10; 35R30 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Proc. Amer. Math. Soc. 145 (3), 1087-1095, 2017 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1810.04392">arXiv:1810.04392</a> <span> [<a href="https://arxiv.org/pdf/1810.04392">pdf</a>, <a href="https://arxiv.org/format/1810.04392">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Analysis of PDEs">math.AP</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1088/0266-5611/31/9/095003">10.1088/0266-5611/31/9/095003 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Combining frequency-difference and ultrasound modulated electrical impedance tomography </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Harrach%2C+B">Bastian Harrach</a>, <a href="/search/math?searchtype=author&query=Lee%2C+E">Eunjung Lee</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Marcel Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1810.04392v1-abstract-short" style="display: inline;"> Electrical impedance tomography (EIT) is highly affected by modeling errors regarding electrode positions and the shape of the imaging domain. In this work, we propose a new inclusion detection technique that is completely independent of such errors. Our new approach is based on a combination of frequency-difference and ultrasound modulated EIT measurements. </span> <span class="abstract-full has-text-grey-dark mathjax" id="1810.04392v1-abstract-full" style="display: none;"> Electrical impedance tomography (EIT) is highly affected by modeling errors regarding electrode positions and the shape of the imaging domain. In this work, we propose a new inclusion detection technique that is completely independent of such errors. Our new approach is based on a combination of frequency-difference and ultrasound modulated EIT measurements. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1810.04392v1-abstract-full').style.display = 'none'; document.getElementById('1810.04392v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 10 October, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2018. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 35R30; 35J25 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Inverse Problems 31 (9), 095003, 2015 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1809.05672">arXiv:1809.05672</a> <span> [<a href="https://arxiv.org/pdf/1809.05672">pdf</a>, <a href="https://arxiv.org/ps/1809.05672">ps</a>, <a href="https://arxiv.org/format/1809.05672">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Number Theory">math.NT</span> </div> </div> <p class="title is-5 mathjax"> On a multi-dimensional Poissonian pair correlation concept and uniform distribution </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Hinrichs%2C+A">Aicke Hinrichs</a>, <a href="/search/math?searchtype=author&query=Kaltenb%C3%B6ck%2C+L">Lisa Kaltenb枚ck</a>, <a href="/search/math?searchtype=author&query=Larcher%2C+G">Gerhard Larcher</a>, <a href="/search/math?searchtype=author&query=Stockinger%2C+W">Wolfgang Stockinger</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1809.05672v1-abstract-short" style="display: inline;"> The aim of the present article is to introduce a concept which allows to generalise the notion of Poissonian pair correlation, a second-order equidistribution property, to higher dimensions. Roughly speaking, in the one-dimensional setting, the pair correlation statistics measures the distribution of spacings between sequence elements in the unit interval at distances of order of the mean spacing… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1809.05672v1-abstract-full').style.display = 'inline'; document.getElementById('1809.05672v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1809.05672v1-abstract-full" style="display: none;"> The aim of the present article is to introduce a concept which allows to generalise the notion of Poissonian pair correlation, a second-order equidistribution property, to higher dimensions. Roughly speaking, in the one-dimensional setting, the pair correlation statistics measures the distribution of spacings between sequence elements in the unit interval at distances of order of the mean spacing $1/N$. In the $d$-dimensional case, of course, the order of the mean spacing is $1/N^{\frac{1}{d}}$, and --in our concept-- the distance of sequence elements will be measured by the supremum-norm. Additionally, we show that, in some sense, almost all sequences satisfy this new concept and we examine the link to uniform distribution. The metrical pair correlation theory is investigated and it is proven that a class of typical low-discrepancy sequences in the high-dimensional unit cube do not have Poissonian pair correlations, which fits the existing results in the one-dimensional case. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1809.05672v1-abstract-full').style.display = 'none'; document.getElementById('1809.05672v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 15 September, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2018. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">16 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 11K06; 11K31 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1807.01492">arXiv:1807.01492</a> <span> [<a href="https://arxiv.org/pdf/1807.01492">pdf</a>, <a href="https://arxiv.org/ps/1807.01492">ps</a>, <a href="https://arxiv.org/format/1807.01492">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Classical Analysis and ODEs">math.CA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1016/j.jco.2018.10.001">10.1016/j.jco.2018.10.001 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> The minimal $k$-dispersion of point sets in high-dimensions </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Hinrichs%2C+A">Aicke Hinrichs</a>, <a href="/search/math?searchtype=author&query=Prochno%2C+J">Joscha Prochno</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a>, <a href="/search/math?searchtype=author&query=Vybiral%2C+J">Jan Vybiral</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1807.01492v1-abstract-short" style="display: inline;"> In this manuscript we introduce and study an extended version of the minimal dispersion of point sets, which has recently attracted considerable attention. Given a set $\mathscr P_n=\{x_1,\dots,x_n\}\subset [0,1]^d$ and $k\in\{0,1,\dots,n\}$, we define the $k$-dispersion to be the volume of the largest box amidst a point set containing at most $k$ points. The minimal $k$-dispersion is then given b… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1807.01492v1-abstract-full').style.display = 'inline'; document.getElementById('1807.01492v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1807.01492v1-abstract-full" style="display: none;"> In this manuscript we introduce and study an extended version of the minimal dispersion of point sets, which has recently attracted considerable attention. Given a set $\mathscr P_n=\{x_1,\dots,x_n\}\subset [0,1]^d$ and $k\in\{0,1,\dots,n\}$, we define the $k$-dispersion to be the volume of the largest box amidst a point set containing at most $k$ points. The minimal $k$-dispersion is then given by the infimum over all possible point sets of cardinality $n$. We provide both upper and lower bounds for the minimal $k$-dispersion that coincide with the known bounds for the classical minimal dispersion for a surprisingly large range of $k$'s. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1807.01492v1-abstract-full').style.display = 'none'; document.getElementById('1807.01492v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 4 July, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2018. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">9 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 68U05; 68Q25; 03D15 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1804.03957">arXiv:1804.03957</a> <span> [<a href="https://arxiv.org/pdf/1804.03957">pdf</a>, <a href="https://arxiv.org/ps/1804.03957">ps</a>, <a href="https://arxiv.org/format/1804.03957">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Functional Analysis">math.FA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1016/j.jco.2018.08.003">10.1016/j.jco.2018.08.003 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> The curse of dimensionality for numerical integration on general domains </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Hinrichs%2C+A">Aicke Hinrichs</a>, <a href="/search/math?searchtype=author&query=Prochno%2C+J">Joscha Prochno</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1804.03957v1-abstract-short" style="display: inline;"> We prove the curse of dimensionality in the worst case setting for multivariate numerical integration for various classes of smooth functions. We prove the results when the domains are isotropic convex bodies with small diameter satisfying a universal $蠄_2$-estimate. In particular, we obtain the result for the important class of volume-normalized $\ell_p^d$-balls in the complete regime… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.03957v1-abstract-full').style.display = 'inline'; document.getElementById('1804.03957v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1804.03957v1-abstract-full" style="display: none;"> We prove the curse of dimensionality in the worst case setting for multivariate numerical integration for various classes of smooth functions. We prove the results when the domains are isotropic convex bodies with small diameter satisfying a universal $蠄_2$-estimate. In particular, we obtain the result for the important class of volume-normalized $\ell_p^d$-balls in the complete regime $2\leq p \leq \infty$. This extends a result in a work of A. Hinrichs, E. Novak, M. Ullrich and H. Wo藕niakowski [J. Complexity, 30(2), 117-143, 2014] to the whole range $2\leq p \leq \infty$, and additionally provides a unified approach. The key ingredient in the proof is a deep result from the theory of Asymptotic Geometric Analysis, the thin-shell volume concentration estimate due to O. Gu茅don and E. Milman. The connection of Asymptotic Geometric Analysis and Information-based Complexity revealed in this work seems promising and is of independent interest. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.03957v1-abstract-full').style.display = 'none'; document.getElementById('1804.03957v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 11 April, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2018. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">19 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 65D30; 65Y20; 52A23; 41A63; 41A55; 46B06 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1802.08666">arXiv:1802.08666</a> <span> [<a href="https://arxiv.org/pdf/1802.08666">pdf</a>, <a href="https://arxiv.org/format/1802.08666">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> </div> <p class="title is-5 mathjax"> Numerical performance of optimized Frolov lattices in tensor product reproducing kernel Sobolev spaces </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Kacwin%2C+C">Christopher Kacwin</a>, <a href="/search/math?searchtype=author&query=Oettershagen%2C+J">Jens Oettershagen</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+T">Tino Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1802.08666v1-abstract-short" style="display: inline;"> In this paper, we deal with several aspects of the universal Frolov cubature method, that is known to achieve optimal asymptotic convergence rates in a broad range of function spaces. Even though every admissible lattice has this favorable asymptotic behavior, there are significant differences concerning the precise numerical behavior of the worst-case error. To this end, we propose new generating… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1802.08666v1-abstract-full').style.display = 'inline'; document.getElementById('1802.08666v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1802.08666v1-abstract-full" style="display: none;"> In this paper, we deal with several aspects of the universal Frolov cubature method, that is known to achieve optimal asymptotic convergence rates in a broad range of function spaces. Even though every admissible lattice has this favorable asymptotic behavior, there are significant differences concerning the precise numerical behavior of the worst-case error. To this end, we propose new generating polynomials that promise a significant reduction of the integration error compared to the classical polynomials. Moreover, we develop a new algorithm to enumerate the Frolov points from non-orthogonal lattices for numerical cubature in the $d$-dimensional unit cube $[0,1]^d$. Finally, we study Sobolev spaces with anisotropic mixed smoothness and compact support in $[0,1]^d$ and derive explicit formulas for their reproducing kernels. This allows for the simulation of exact worst-case errors which numerically validate our theoretical results. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1802.08666v1-abstract-full').style.display = 'none'; document.getElementById('1802.08666v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 23 February, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2018. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1712.06831">arXiv:1712.06831</a> <span> [<a href="https://arxiv.org/pdf/1712.06831">pdf</a>, <a href="https://arxiv.org/ps/1712.06831">ps</a>, <a href="https://arxiv.org/format/1712.06831">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Number Theory">math.NT</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1016/j.ffa.2018.02.004">10.1016/j.ffa.2018.02.004 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Digital net properties of a polynomial analogue of Frolov's construction </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Dick%2C+J">Josef Dick</a>, <a href="/search/math?searchtype=author&query=Pillichshammer%2C+F">Friedrich Pillichshammer</a>, <a href="/search/math?searchtype=author&query=Suzuki%2C+K">Kosuke Suzuki</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a>, <a href="/search/math?searchtype=author&query=Yoshiki%2C+T">Takehito Yoshiki</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1712.06831v2-abstract-short" style="display: inline;"> Frolov's cubature formula on the unit hypercube has been considered important since it attains an optimal rate of convergence for various function spaces. Its integration nodes are given by shrinking a suitable full rank $\mathbb{Z}$-lattice in $\mathbb{R}^d$ and taking all points inside the unit cube. The main drawback of these nodes is that they are hard to find computationally, especially in hi… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1712.06831v2-abstract-full').style.display = 'inline'; document.getElementById('1712.06831v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1712.06831v2-abstract-full" style="display: none;"> Frolov's cubature formula on the unit hypercube has been considered important since it attains an optimal rate of convergence for various function spaces. Its integration nodes are given by shrinking a suitable full rank $\mathbb{Z}$-lattice in $\mathbb{R}^d$ and taking all points inside the unit cube. The main drawback of these nodes is that they are hard to find computationally, especially in high dimensions.In such situations, quasi-Monte Carlo (QMC) rules based on digital nets have proven to be successful. However, there is still no construction known that leads to QMC rules which are optimal in the same generality as Frolov's. In this paper we investigate a polynomial analog of Frolov's cubature formula, which we expect to be important in this respect. This analog is defined in a field of Laurent series with coefficients in a finite field. A similar approach was previously studied in [M.~B.~Levin. Adelic constructions of low discrepancy sequences. Online Journal of Analytic Combinatorics. Issue 5, 2010.]. We show that our construction is a $(t,m,d)$-net, which also implies bounds on its star-discrepancy and the error of the corresponding cubature rule. Moreover, we show that our cubature rule is a QMC rule, whereas Frolov's is not, and provide an algorithm to determine its integration nodes explicitly. To this end we need to extend the notion of $(t,m,d)$-nets to fit the situation that the points can have infinite digit expansion and develop a duality theory. Additionally, we adapt the notion of admissible lattices to our setting and prove its significance. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1712.06831v2-abstract-full').style.display = 'none'; document.getElementById('1712.06831v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 14 February, 2018; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 19 December, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2017. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 11K31; 11K38; 11P21; 65D30 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1710.08694">arXiv:1710.08694</a> <span> [<a href="https://arxiv.org/pdf/1710.08694">pdf</a>, <a href="https://arxiv.org/ps/1710.08694">ps</a>, <a href="https://arxiv.org/format/1710.08694">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Geometry">cs.CG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1016/j.dam.2018.08.032">10.1016/j.dam.2018.08.032 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> A note on the dispersion of admissible lattices </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1710.08694v1-abstract-short" style="display: inline;"> In this note we show that the volume of axis-parallel boxes in $\mathbb{R}^d$ which do not intersect an admissible lattice $\mathbb{L}\subset\mathbb{R}^d$ is uniformly bounded. In particular, this implies that the dispersion of the dilated lattices $N^{-1/d}\mathbb{L}$ restricted to the unit cube is of the (optimal) order $N^{-1}$ as $N$ goes to infinity. This result was obtained independently b… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1710.08694v1-abstract-full').style.display = 'inline'; document.getElementById('1710.08694v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1710.08694v1-abstract-full" style="display: none;"> In this note we show that the volume of axis-parallel boxes in $\mathbb{R}^d$ which do not intersect an admissible lattice $\mathbb{L}\subset\mathbb{R}^d$ is uniformly bounded. In particular, this implies that the dispersion of the dilated lattices $N^{-1/d}\mathbb{L}$ restricted to the unit cube is of the (optimal) order $N^{-1}$ as $N$ goes to infinity. This result was obtained independently by V.N. Temlyakov (arXiv:1709.08158). <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1710.08694v1-abstract-full').style.display = 'none'; document.getElementById('1710.08694v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 24 October, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2017. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">4 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Discrete Applied Mathematics 257 (2019), 385-387 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1710.06754">arXiv:1710.06754</a> <span> [<a href="https://arxiv.org/pdf/1710.06754">pdf</a>, <a href="https://arxiv.org/ps/1710.06754">ps</a>, <a href="https://arxiv.org/format/1710.06754">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Classical Analysis and ODEs">math.CA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1016/j.jco.2017.11.003">10.1016/j.jco.2017.11.003 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> An upper bound on the minimal dispersion </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a>, <a href="/search/math?searchtype=author&query=Vyb%C3%ADral%2C+J">Jan Vyb铆ral</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1710.06754v2-abstract-short" style="display: inline;"> For $\varepsilon\in(0,1/2)$ and a natural number $d\ge 2$, let $N$ be a natural number with \[ N \,\ge\, 2^9\,\log_2(d)\, \left(\frac{\log_2(1/\varepsilon)}{\varepsilon}\right)^2. \] We prove that there is a set of $N$ points in the unit cube $[0,1]^d$, which intersects all axis-parallel boxes with volume $\varepsilon$. That is, the dispersion of this point set is bounded from above by… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1710.06754v2-abstract-full').style.display = 'inline'; document.getElementById('1710.06754v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1710.06754v2-abstract-full" style="display: none;"> For $\varepsilon\in(0,1/2)$ and a natural number $d\ge 2$, let $N$ be a natural number with \[ N \,\ge\, 2^9\,\log_2(d)\, \left(\frac{\log_2(1/\varepsilon)}{\varepsilon}\right)^2. \] We prove that there is a set of $N$ points in the unit cube $[0,1]^d$, which intersects all axis-parallel boxes with volume $\varepsilon$. That is, the dispersion of this point set is bounded from above by $\varepsilon$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1710.06754v2-abstract-full').style.display = 'none'; document.getElementById('1710.06754v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 28 October, 2017; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 28 September, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2017. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1709.02568">arXiv:1709.02568</a> <span> [<a href="https://arxiv.org/pdf/1709.02568">pdf</a>, <a href="https://arxiv.org/ps/1709.02568">ps</a>, <a href="https://arxiv.org/format/1709.02568">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Functional Analysis">math.FA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1142/S0219530518500094">10.1142/S0219530518500094 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Reproducing Kernels of Sobolev Spaces on $\mathbb{R}^d$ and Applications to Embedding Constants and Tractability </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Novak%2C+E">Erich Novak</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a>, <a href="/search/math?searchtype=author&query=Wo%C5%BAniakowski%2C+H">Henryk Wo藕niakowski</a>, <a href="/search/math?searchtype=author&query=Zhang%2C+S">Shun Zhang</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1709.02568v1-abstract-short" style="display: inline;"> The standard Sobolev space $W^s_2(\mathbb{R}^d)$, with arbitrary positive integers $s$ and $d$ for which $s>d/2$, has the reproducing kernel $$ K_{d,s}(x,t)=\int_{\mathbb{R}^d}\frac{\prod_{j=1}^d\cos\left(2蟺\,(x_j-t_j)u_j\right)} {1+\sum_{0<|伪|_1\le s}\prod_{j=1}^d(2蟺\,u_j)^{2伪_j}}\,{\rm d}u $$ for all $x,t\in\mathbb{R}^d$, where $x_j,t_j,u_j,伪_j$ are components of $d$-variate $x,t,u,伪$, and… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1709.02568v1-abstract-full').style.display = 'inline'; document.getElementById('1709.02568v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1709.02568v1-abstract-full" style="display: none;"> The standard Sobolev space $W^s_2(\mathbb{R}^d)$, with arbitrary positive integers $s$ and $d$ for which $s>d/2$, has the reproducing kernel $$ K_{d,s}(x,t)=\int_{\mathbb{R}^d}\frac{\prod_{j=1}^d\cos\left(2蟺\,(x_j-t_j)u_j\right)} {1+\sum_{0<|伪|_1\le s}\prod_{j=1}^d(2蟺\,u_j)^{2伪_j}}\,{\rm d}u $$ for all $x,t\in\mathbb{R}^d$, where $x_j,t_j,u_j,伪_j$ are components of $d$-variate $x,t,u,伪$, and $|伪|_1=\sum_{j=1}^d伪_j$ with non-negative integers $伪_j$. We obtain a more explicit form for the reproducing kernel $K_{1,s}$ and find a closed form for the kernel $K_{d, \infty}$. Knowing the form of $K_{d,s}$, we present applications on the best embedding constants between the Sobolev space $W^s_2(\mathbb{R}^d)$ and $L_\infty(\mathbb{R}^d)$, and on strong polynomial tractability of integration with an arbitrary probability density. We prove that the best embedding constants are exponentially small in $d$, whereas worst case integration errors of algorithms using $n$ function values are also exponentially small in $d$ and decay at least like $n^{-1/2}$. This yields strong polynomial tractability in the worst case setting for the absolute error criterion. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1709.02568v1-abstract-full').style.display = 'none'; document.getElementById('1709.02568v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 8 September, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2017. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">26 pages, 1 figure</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 65Y20; 46E22; 65D30; 68Q25 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1706.04502">arXiv:1706.04502</a> <span> [<a href="https://arxiv.org/pdf/1706.04502">pdf</a>, <a href="https://arxiv.org/ps/1706.04502">ps</a>, <a href="https://arxiv.org/format/1706.04502">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1016/j.jat.2018.09.011">10.1016/j.jat.2018.09.011 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Lattice rules with random $n$ achieve nearly the optimal $\mathcal{O}(n^{-伪-1/2})$ error independently of the dimension </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Kritzer%2C+P">Peter Kritzer</a>, <a href="/search/math?searchtype=author&query=Kuo%2C+F+Y">Frances Y. Kuo</a>, <a href="/search/math?searchtype=author&query=Nuyens%2C+D">Dirk Nuyens</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1706.04502v3-abstract-short" style="display: inline;"> We analyze a new random algorithm for numerical integration of $d$-variate functions over $[0,1]^d$ from a weighted Sobolev space with dominating mixed smoothness $伪\ge 0$ and product weights $1\ge纬_1\ge纬_2\ge\cdots>0$, where the functions are continuous and periodic when $伪>1/2$. The algorithm is based on rank-$1$ lattice rules with a random number of points~$n$. For the case $伪>1/2$, we prove th… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1706.04502v3-abstract-full').style.display = 'inline'; document.getElementById('1706.04502v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1706.04502v3-abstract-full" style="display: none;"> We analyze a new random algorithm for numerical integration of $d$-variate functions over $[0,1]^d$ from a weighted Sobolev space with dominating mixed smoothness $伪\ge 0$ and product weights $1\ge纬_1\ge纬_2\ge\cdots>0$, where the functions are continuous and periodic when $伪>1/2$. The algorithm is based on rank-$1$ lattice rules with a random number of points~$n$. For the case $伪>1/2$, we prove that the algorithm achieves almost the optimal order of convergence of $\mathcal{O}(n^{-伪-1/2})$, where the implied constant is independent of the dimension~$d$ if the weights satisfy $\sum_{j=1}^\infty 纬_j^{1/伪}<\infty$. The same rate of convergence holds for the more general case $伪>0$ by adding a random shift to the lattice rule with random $n$. This shows, in particular, that the exponent of strong tractability in the randomized setting equals $1/(伪+1/2)$, if the weights decay fast enough. We obtain a lower bound to indicate that our results are essentially optimal. This paper is a significant advancement over previous related works with respect to the potential for implementation and the independence of error bounds on the problem dimension. Other known algorithms which achieve the optimal error bounds, such as those based on Frolov's method, are very difficult to implement especially in high dimensions. Here we adapt a lesser-known randomization technique introduced by Bakhvalov in 1961. This algorithm is based on rank-$1$ lattice rules which are very easy to implement given the integer generating vectors. A simple probabilistic approach can be used to obtain suitable generating vectors. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1706.04502v3-abstract-full').style.display = 'none'; document.getElementById('1706.04502v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 1 August, 2018; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 14 June, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2017. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">17 pages</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1608.08687">arXiv:1608.08687</a> <span> [<a href="https://arxiv.org/pdf/1608.08687">pdf</a>, <a href="https://arxiv.org/ps/1608.08687">ps</a>, <a href="https://arxiv.org/format/1608.08687">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1007/s10231-017-0670-3">10.1007/s10231-017-0670-3 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Lattice based integration algorithms: Kronecker sequences and rank-1 lattices </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Dick%2C+J">Josef Dick</a>, <a href="/search/math?searchtype=author&query=Pillichshammer%2C+F">Friedrich Pillichshammer</a>, <a href="/search/math?searchtype=author&query=Suzuki%2C+K">Kosuke Suzuki</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a>, <a href="/search/math?searchtype=author&query=Yoshiki%2C+T">Takehito Yoshiki</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1608.08687v1-abstract-short" style="display: inline;"> We prove upper bounds on the order of convergence of lattice based algorithms for numerical integration in function spaces of dominating mixed smoothness on the unit cube with homogeneous boundary condition. More precisely, we study worst-case integration errors for Besov spaces of dominating mixed smoothness $\mathring{\mathbf{B}}^s_{p,胃}$, which also comprise the concept of Sobolev spaces of dom… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1608.08687v1-abstract-full').style.display = 'inline'; document.getElementById('1608.08687v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1608.08687v1-abstract-full" style="display: none;"> We prove upper bounds on the order of convergence of lattice based algorithms for numerical integration in function spaces of dominating mixed smoothness on the unit cube with homogeneous boundary condition. More precisely, we study worst-case integration errors for Besov spaces of dominating mixed smoothness $\mathring{\mathbf{B}}^s_{p,胃}$, which also comprise the concept of Sobolev spaces of dominating mixed smoothness $\mathring{\mathbf{H}}^s_{p}$ as special cases. The considered algorithms are quasi-Monte Carlo rules with underlying nodes from $T_N(\mathbb{Z}^d) \cap [0,1)^d$, where $T_N$ is a real invertible generator matrix of size $d$. For such rules the worst-case error can be bounded in terms of the Zaremba index of the lattice $\mathbb{X}_N=T_N(\mathbb{Z}^d)$. We apply this result to Kronecker lattices and to rank-1 lattice point sets, which both lead to optimal error bounds up to $\log N$-factors for arbitrary smoothness $s$. The advantage of Kronecker lattices and classical lattice point sets is that the run-time of algorithms generating these point sets is very short. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1608.08687v1-abstract-full').style.display = 'none'; document.getElementById('1608.08687v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 30 August, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 2016. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">19 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 65D30; 65D32; 11K31 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Annali di Matematica (2018) 197: 109 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1604.06008">arXiv:1604.06008</a> <span> [<a href="https://arxiv.org/pdf/1604.06008">pdf</a>, <a href="https://arxiv.org/ps/1604.06008">ps</a>, <a href="https://arxiv.org/format/1604.06008">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1137/16M1075557">10.1137/16M1075557 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> A Monte Carlo method for integration of multivariate smooth functions </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1604.06008v2-abstract-short" style="display: inline;"> We study a Monte Carlo algorithm that is based on a specific (randomly shifted and dilated) lattice point set. The main result of this paper is that the mean squared error for a given compactly supported, square-integrable function is bounded by $n^{-1/2}$ times the $L_2$-norm of the Fourier transform outside a region around the origin, where $n$ is the expected number of function evaluations. As… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1604.06008v2-abstract-full').style.display = 'inline'; document.getElementById('1604.06008v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1604.06008v2-abstract-full" style="display: none;"> We study a Monte Carlo algorithm that is based on a specific (randomly shifted and dilated) lattice point set. The main result of this paper is that the mean squared error for a given compactly supported, square-integrable function is bounded by $n^{-1/2}$ times the $L_2$-norm of the Fourier transform outside a region around the origin, where $n$ is the expected number of function evaluations. As corollaries we obtain the optimal order of convergence for functions from the Sobolev spaces $H^s_p$ with isotropic, anisotropic, or mixed smoothness with given compact support for all values of the parameters. If the region of integration is the unit cube, we obtain the same optimal orders for functions without boundary conditions. This proves, in particular, that the optimal order of convergence in the latter case is $n^{-s-1/2}$ for $p\ge2$, which is, in contrast to the case of deterministic algorithms, independent of the dimension. This shows that Monte Carlo algorithms can improve the order by more than $n^{-1/2}$ for a whole class of natural function spaces. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1604.06008v2-abstract-full').style.display = 'none'; document.getElementById('1604.06008v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 21 June, 2017; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 20 April, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2016. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">The numbering of the theorems differs from the published version</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 65D30; 65C05; 68Q25; 46E35; 42B10 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> SIAM J. Numer. Anal., 55(3), 1188-1200, 2017 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1604.00261">arXiv:1604.00261</a> <span> [<a href="https://arxiv.org/pdf/1604.00261">pdf</a>, <a href="https://arxiv.org/ps/1604.00261">ps</a>, <a href="https://arxiv.org/format/1604.00261">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1016/j.jco.2016.09.001">10.1016/j.jco.2016.09.001 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Product rules are optimal for numerical integration in classical smoothness spaces </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Hinrichs%2C+A">Aicke Hinrichs</a>, <a href="/search/math?searchtype=author&query=Novak%2C+E">Erich Novak</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a>, <a href="/search/math?searchtype=author&query=Wozniakowski%2C+H">Henryk Wozniakowski</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1604.00261v1-abstract-short" style="display: inline;"> We mainly study numerical integration of real valued functions defined on the $d$-dimensional unit cube with all partial derivatives up to some finite order $r\ge1$ bounded by one. It is well known that optimal algorithms that use $n$ function values achieve the error rate $n^{-r/d}$, where the hidden constant depends on $r$ and $d$. Here we prove explicit error bounds without hidden constants and… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1604.00261v1-abstract-full').style.display = 'inline'; document.getElementById('1604.00261v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1604.00261v1-abstract-full" style="display: none;"> We mainly study numerical integration of real valued functions defined on the $d$-dimensional unit cube with all partial derivatives up to some finite order $r\ge1$ bounded by one. It is well known that optimal algorithms that use $n$ function values achieve the error rate $n^{-r/d}$, where the hidden constant depends on $r$ and $d$. Here we prove explicit error bounds without hidden constants and, in particular, show that the optimal order of the error is $\min \bigl\{1, d \, n^{-r/d}\bigr\}$, where now the hidden constant only depends on $r$, not on $d$. For $n=m^d$, this optimal order can be achieved by (tensor) product rules. We also provide lower bounds for integration defined over an arbitrary open domain of volume one. We briefly discuss how lower bounds for integration may be applied for other problems such as multivariate approximation and optimization. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1604.00261v1-abstract-full').style.display = 'none'; document.getElementById('1604.00261v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 1 April, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2016. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">17 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Journal of Complexity 38 (2017), 39-49 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1511.05414">arXiv:1511.05414</a> <span> [<a href="https://arxiv.org/pdf/1511.05414">pdf</a>, <a href="https://arxiv.org/ps/1511.05414">ps</a>, <a href="https://arxiv.org/format/1511.05414">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1007/s10444-016-9496-6">10.1007/s10444-016-9496-6 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Complexity of Oscillatory Integrals on the Real Line </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Novak%2C+E">Erich Novak</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a>, <a href="/search/math?searchtype=author&query=Wo%C5%BAniakowski%2C+H">Henryk Wo藕niakowski</a>, <a href="/search/math?searchtype=author&query=Zhang%2C+S">Shun Zhang</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1511.05414v2-abstract-short" style="display: inline;"> We analyze univariate oscillatory integrals defined on the real line for functions from the standard Sobolev space $H^s({\mathbb{R}})$ and from the space $C^s({\mathbb{R}})$ with an arbitrary integer $s\ge1$. We find tight upper and lower bounds for the worst case error of optimal algorithms that use $n$ function values. More specifically, we study integrals of the form \[ I_k^蟻(f) = \int_{ {\math… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1511.05414v2-abstract-full').style.display = 'inline'; document.getElementById('1511.05414v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1511.05414v2-abstract-full" style="display: none;"> We analyze univariate oscillatory integrals defined on the real line for functions from the standard Sobolev space $H^s({\mathbb{R}})$ and from the space $C^s({\mathbb{R}})$ with an arbitrary integer $s\ge1$. We find tight upper and lower bounds for the worst case error of optimal algorithms that use $n$ function values. More specifically, we study integrals of the form \[ I_k^蟻(f) = \int_{ {\mathbb{R}}} f(x) \,e^{-i\,kx} 蟻(x) \, {\rm d} x\ \ \ \mbox{for}\ \ f\in H^s({\mathbb{R}})\ \ \mbox{or}\ \ f\in C^s({\mathbb{R}}) \] with $k\in {\mathbb{R}}$ and a smooth density function $蟻$ such as $ 蟻(x) = \frac{1}{\sqrt{2 蟺}} \exp( -x^2/2) $. The optimal error bounds are $螛((n+\max(1,|k|))^{-s})$ with the factors in the $螛$ notation dependent only on $s$ and $蟻$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1511.05414v2-abstract-full').style.display = 'none'; document.getElementById('1511.05414v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 November, 2015; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 17 November, 2015; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2015. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">21 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 65Y20; 42B20; 65D30; 68Q25 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Adv. Comput. Math. 43, 537-553 (2017) </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1511.02036">arXiv:1511.02036</a> <span> [<a href="https://arxiv.org/pdf/1511.02036">pdf</a>, <a href="https://arxiv.org/ps/1511.02036">ps</a>, <a href="https://arxiv.org/format/1511.02036">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Functional Analysis">math.FA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1007/s00365-017-9371-9">10.1007/s00365-017-9371-9 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Change of variable in spaces of mixed smoothness and numerical integration of multivariate functions on the unit cube </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Nguyen%2C+V+K">Van Kien Nguyen</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+T">Tino Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1511.02036v1-abstract-short" style="display: inline;"> In a recent article by two of the present authors it turned out that Frolov's cubature formulae are optimal and universal for various settings (Besov-Triebel-Lizorkin spaces) of functions with dominating mixed smoothness. Those cubature formulae go well together with functions supported inside the unit cube $[0,1]^d$. The question for the optimal numerical integration of multivariate functions wit… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1511.02036v1-abstract-full').style.display = 'inline'; document.getElementById('1511.02036v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1511.02036v1-abstract-full" style="display: none;"> In a recent article by two of the present authors it turned out that Frolov's cubature formulae are optimal and universal for various settings (Besov-Triebel-Lizorkin spaces) of functions with dominating mixed smoothness. Those cubature formulae go well together with functions supported inside the unit cube $[0,1]^d$. The question for the optimal numerical integration of multivariate functions with non-trivial boundary data, in particular non-periodic functions, arises. In this paper we give a general result that the asymptotic rate of the minimal worst-case integration error is not affected by boundary conditions in the above mentioned spaces. In fact, we propose two tailored modifications of Frolov's cubature formulae suitable for functions supported on the cube (not in the cube) which provide the same minimal worst-case error up to a constant. This constant involves the norms of a ``change of variable'' and a ``pointwise multiplication'' mapping, respectively, between the function spaces of interest. In fact, we complement, extend and improve classical results by Bykovskii, Dubinin and Temlyakov on the boundedness of change of variable mappings in Besov-Sobolev spaces of mixed smoothness. Our proof technique relies on a new characterization via integral means of mixed differences and maximal function techniques, general enough to treat Besov and Triebel-Lizorkin spaces at once. The second modification, which only tackles the case of periodic functions, is based on a pointwise multiplication and is therefore most likely more suitable for applications than the (traditional) ``change of variable'' approach. These new theoretical insights are expected to be useful for the design of new (and robust) cubature rules for multivariate functions on the cube. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1511.02036v1-abstract-full').style.display = 'none'; document.getElementById('1511.02036v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 6 November, 2015; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2015. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">33 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Constr Approx (2017) 46: 69 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1510.04617">arXiv:1510.04617</a> <span> [<a href="https://arxiv.org/pdf/1510.04617">pdf</a>, <a href="https://arxiv.org/format/1510.04617">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1016/j.matcom.2015.12.005">10.1016/j.matcom.2015.12.005 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> A lower bound for the dispersion on the torus </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1510.04617v1-abstract-short" style="display: inline;"> We consider the volume of the largest axis-parallel box in the $d$-dimensional torus that contains no point of a given point set $\mathcal{P}_n$ with $n$ elements. We prove that, for all natural numbers $d, n$ and every point set $\mathcal{P}_n$, this volume is bounded from below by $\min\{1,d/n\}$. This implies the same lower bound for the discrepancy on the torus. </span> <span class="abstract-full has-text-grey-dark mathjax" id="1510.04617v1-abstract-full" style="display: none;"> We consider the volume of the largest axis-parallel box in the $d$-dimensional torus that contains no point of a given point set $\mathcal{P}_n$ with $n$ elements. We prove that, for all natural numbers $d, n$ and every point set $\mathcal{P}_n$, this volume is bounded from below by $\min\{1,d/n\}$. This implies the same lower bound for the discrepancy on the torus. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1510.04617v1-abstract-full').style.display = 'none'; document.getElementById('1510.04617v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 15 October, 2015; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2015. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">6 pages</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1505.00579">arXiv:1505.00579</a> <span> [<a href="https://arxiv.org/pdf/1505.00579">pdf</a>, <a href="https://arxiv.org/ps/1505.00579">ps</a>, <a href="https://arxiv.org/format/1505.00579">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Statistics Theory">math.ST</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1017/jpr.2018.78">10.1017/jpr.2018.78 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Comparison of hit-and-run, slice sampling and random walk Metropolis </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Rudolf%2C+D">Daniel Rudolf</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1505.00579v3-abstract-short" style="display: inline;"> Different Markov chains can be used for approximate sampling of a distribution given by an unnormalized density function with respect to the Lebesgue measure. The hit-and-run, (hybrid) slice sampler and random walk Metropolis algorithm are popular tools to simulate such Markov chains. We develop a general approach to compare the efficiency of these sampling procedures by the use of a partial order… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1505.00579v3-abstract-full').style.display = 'inline'; document.getElementById('1505.00579v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1505.00579v3-abstract-full" style="display: none;"> Different Markov chains can be used for approximate sampling of a distribution given by an unnormalized density function with respect to the Lebesgue measure. The hit-and-run, (hybrid) slice sampler and random walk Metropolis algorithm are popular tools to simulate such Markov chains. We develop a general approach to compare the efficiency of these sampling procedures by the use of a partial ordering of their Markov operators, the covariance ordering. In particular, we show that the hit-and-run and the simple slice sampler are more efficient than a hybrid slice sampler based on hit-and-run which, itself, is more efficient than a (lazy) random walk Metropolis algorithm. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1505.00579v3-abstract-full').style.display = 'none'; document.getElementById('1505.00579v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 August, 2018; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 4 May, 2015; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2015. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">18 pages, Accepted for publication by the Applied Probability Trust (http://www.appliedprobability.org) in J. Appl. Prob</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 60J22; 65C05; 60J05 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1503.08846">arXiv:1503.08846</a> <span> [<a href="https://arxiv.org/pdf/1503.08846">pdf</a>, <a href="https://arxiv.org/ps/1503.08846">ps</a>, <a href="https://arxiv.org/format/1503.08846">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1137/15M1014814">10.1137/15M1014814 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> The role of Frolov's cubature formula for functions with bounded mixed derivative </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+T">Tino Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1503.08846v2-abstract-short" style="display: inline;"> We prove upper bounds on the order of convergence of Frolov's cubature formula for numerical integration in function spaces of dominating mixed smoothness on the unit cube with homogeneous boundary condition. More precisely, we study worst-case integration errors for Besov $\mathbf{B}^s_{p,胃}$ and Triebel-Lizorkin spaces $\mathbf{F}^s_{p,胃}$ and our results treat the whole range of admissible para… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1503.08846v2-abstract-full').style.display = 'inline'; document.getElementById('1503.08846v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1503.08846v2-abstract-full" style="display: none;"> We prove upper bounds on the order of convergence of Frolov's cubature formula for numerical integration in function spaces of dominating mixed smoothness on the unit cube with homogeneous boundary condition. More precisely, we study worst-case integration errors for Besov $\mathbf{B}^s_{p,胃}$ and Triebel-Lizorkin spaces $\mathbf{F}^s_{p,胃}$ and our results treat the whole range of admissible parameters $(s\geq 1/p)$. In particular, we obtain upper bounds for the difficult the case of small smoothness which is given for Triebel-Lizorkin spaces $\mathbf{F}^s_{p,胃}$ in case $1<胃<p<\infty$ with $1/p<s\leq 1/胃$. The presented upper bounds on the worst-case error show a completely different behavior compared to "large" smoothness $s>1/胃$. In the latter case the presented upper bounds are optimal, i.e., they can not be improved by any other cubature formula. The optimality for "small" smoothness is open. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1503.08846v2-abstract-full').style.display = 'none'; document.getElementById('1503.08846v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 6 April, 2016; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 30 March, 2015; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2015. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">23 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 46E35; 65D30; 65D32 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> SIAM J. Numer. Anal., 54(2), 969-993, 2016 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1404.5457">arXiv:1404.5457</a> <span> [<a href="https://arxiv.org/pdf/1404.5457">pdf</a>, <a href="https://arxiv.org/ps/1404.5457">ps</a>, <a href="https://arxiv.org/format/1404.5457">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1007/978-3-319-33507-0_31">10.1007/978-3-319-33507-0_31 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> On "Upper error bounds for quadrature formulas on function classes" by K. K. Frolov </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1404.5457v1-abstract-short" style="display: inline;"> This is a tutorial paper that gives the complete proof of a result of Frolov [2] that shows the optimal order of convergence for numerical integration of functions with bounded mixed derivatives. The presentation follows Temlyakov [8], see also [7]. </span> <span class="abstract-full has-text-grey-dark mathjax" id="1404.5457v1-abstract-full" style="display: none;"> This is a tutorial paper that gives the complete proof of a result of Frolov [2] that shows the optimal order of convergence for numerical integration of functions with bounded mixed derivatives. The presentation follows Temlyakov [8], see also [7]. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1404.5457v1-abstract-full').style.display = 'none'; document.getElementById('1404.5457v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 22 April, 2014; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2014. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">11 pages</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1311.1528">arXiv:1311.1528</a> <span> [<a href="https://arxiv.org/pdf/1311.1528">pdf</a>, <a href="https://arxiv.org/ps/1311.1528">ps</a>, <a href="https://arxiv.org/format/1311.1528">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1016/j.jco.2014.07.001">10.1016/j.jco.2014.07.001 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Complexity of Oscillatory Integration for Univariate Sobolev Spaces </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Novak%2C+E">Erich Novak</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a>, <a href="/search/math?searchtype=author&query=Wo%C5%BAniakowski%2C+H">Henryk Wo藕niakowski</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1311.1528v2-abstract-short" style="display: inline;"> We analyze univariate oscillatory integrals for the standard Sobolev spaces $H^s$ of periodic and non-periodic functions with an arbitrary integer $s\ge1$. We find matching lower and upper bounds on the minimal worst case error of algorithms that use $n$ function or derivative values. We also find sharp bounds on the information complexity which is the minimal $n$ for which the absolute or normali… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1311.1528v2-abstract-full').style.display = 'inline'; document.getElementById('1311.1528v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1311.1528v2-abstract-full" style="display: none;"> We analyze univariate oscillatory integrals for the standard Sobolev spaces $H^s$ of periodic and non-periodic functions with an arbitrary integer $s\ge1$. We find matching lower and upper bounds on the minimal worst case error of algorithms that use $n$ function or derivative values. We also find sharp bounds on the information complexity which is the minimal $n$ for which the absolute or normalized error is at most $\varepsilon$. We show surprising relations between the information complexity and the oscillatory weight. We also briefly consider the case of $s=\infty$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1311.1528v2-abstract-full').style.display = 'none'; document.getElementById('1311.1528v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 24 October, 2014; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 6 November, 2013; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2013. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">40 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> J. Complexity 31 (2015), 15-41 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1309.0360">arXiv:1309.0360</a> <span> [<a href="https://arxiv.org/pdf/1309.0360">pdf</a>, <a href="https://arxiv.org/ps/1309.0360">ps</a>, <a href="https://arxiv.org/format/1309.0360">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1016/j.jat.2014.03.012">10.1016/j.jat.2014.03.012 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> On Weak Tractability of the Clenshaw-Curtis Smolyak Algorithm </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Hinrichs%2C+A">Aicke Hinrichs</a>, <a href="/search/math?searchtype=author&query=Novak%2C+E">Erich Novak</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1309.0360v2-abstract-short" style="display: inline;"> We consider the problem of integration of d-variate analytic functions defined on the unit cube with directional derivatives of all orders bounded by 1. We prove that the Clenshaw Curtis Smolyak algorithm leads to weak tractability of the problem. This seems to be the first positive tractability result for the Smolyak algorithm for a normalized and unweighted problem. The space of integrands is no… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1309.0360v2-abstract-full').style.display = 'inline'; document.getElementById('1309.0360v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1309.0360v2-abstract-full" style="display: none;"> We consider the problem of integration of d-variate analytic functions defined on the unit cube with directional derivatives of all orders bounded by 1. We prove that the Clenshaw Curtis Smolyak algorithm leads to weak tractability of the problem. This seems to be the first positive tractability result for the Smolyak algorithm for a normalized and unweighted problem. The space of integrands is not a tensor product space and therefore we have to develop a different proof technique. We use the polynomial exactness of the algorithm as well as an explicit bound on the operator norm of the algorithm. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1309.0360v2-abstract-full').style.display = 'none'; document.getElementById('1309.0360v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 22 April, 2014; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 2 September, 2013; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2013. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">18 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> J. Approx. Theory 183 (2014), 31-44 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1304.3372">arXiv:1304.3372</a> <span> [<a href="https://arxiv.org/pdf/1304.3372">pdf</a>, <a href="https://arxiv.org/ps/1304.3372">ps</a>, <a href="https://arxiv.org/format/1304.3372">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1016/j.jco.2013.10.007">10.1016/j.jco.2013.10.007 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> The Curse of Dimensionality for Numerical Integration of Smooth Functions II </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Hinrichs%2C+A">Aicke Hinrichs</a>, <a href="/search/math?searchtype=author&query=Novak%2C+E">Erich Novak</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a>, <a href="/search/math?searchtype=author&query=Wozniakowski%2C+H">Henryk Wozniakowski</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1304.3372v2-abstract-short" style="display: inline;"> We prove the curse of dimensionality in the worst case setting for numerical integration for a number of classes of smooth $d$-variate functions. Roughly speaking, we consider different bounds for the derivatives of $f \in C^k(D_d)$ and ask whether the curse of dimensionality holds for the respective classes of functions. We always assume that $D_d \subset \mathbb{R}^d$ has volume one and consider… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1304.3372v2-abstract-full').style.display = 'inline'; document.getElementById('1304.3372v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1304.3372v2-abstract-full" style="display: none;"> We prove the curse of dimensionality in the worst case setting for numerical integration for a number of classes of smooth $d$-variate functions. Roughly speaking, we consider different bounds for the derivatives of $f \in C^k(D_d)$ and ask whether the curse of dimensionality holds for the respective classes of functions. We always assume that $D_d \subset \mathbb{R}^d$ has volume one and consider various values of $k$ including the case $k=\infty$ which corresponds to infinitely many differentiable functions. We obtain necessary and sufficient conditions, and in some cases a full characterization for the curse of dimensionality. For infinitely many differentiable functions we prove the curse if the bounds on the successive derivatives are appropriately large. The proof technique is based on a volume estimate of a neighborhood of the convex hull of $n$ points which decays exponentially fast if $n$ is small relative to $d$. For $k=\infty$, we also also study conditions for quasi-polynomial, weak and uniform weak tractability. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1304.3372v2-abstract-full').style.display = 'none'; document.getElementById('1304.3372v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 12 November, 2013; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 11 April, 2013; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2013. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">39 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 65D30; 65Y20; 41A63; 41A55 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> J. Complexity 30 (2014), no. 2, 117-143 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1301.4055">arXiv:1301.4055</a> <span> [<a href="https://arxiv.org/pdf/1301.4055">pdf</a>, <a href="https://arxiv.org/ps/1301.4055">ps</a>, <a href="https://arxiv.org/format/1301.4055">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1016/j.laa.2014.04.018">10.1016/j.laa.2014.04.018 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Structure and eigenvalues of heat-bath Markov chains </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Dyer%2C+M">Martin Dyer</a>, <a href="/search/math?searchtype=author&query=Greenhill%2C+C">Catherine Greenhill</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1301.4055v3-abstract-short" style="display: inline;"> We prove that heat-bath chains (which we define in a general setting) have no negative eigenvalues. Two applications of this result are presented: one to single-site heat-bath chains for spin systems and one to a heat-bath Markov chain for sampling contingency tables. Some implications of our main result for the analysis of the mixing time of heat-bath Markov chains are discussed. We also prove an… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1301.4055v3-abstract-full').style.display = 'inline'; document.getElementById('1301.4055v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1301.4055v3-abstract-full" style="display: none;"> We prove that heat-bath chains (which we define in a general setting) have no negative eigenvalues. Two applications of this result are presented: one to single-site heat-bath chains for spin systems and one to a heat-bath Markov chain for sampling contingency tables. Some implications of our main result for the analysis of the mixing time of heat-bath Markov chains are discussed. We also prove an alternative characterisation of heat-bath chains, and consider possible generalisations. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1301.4055v3-abstract-full').style.display = 'none'; document.getElementById('1301.4055v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 9 April, 2014; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 17 January, 2013; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2013. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">15 pages. Minor edits to address referee's comments</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Linear Algebra Appl. 454 (2014), 57-71 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1212.4908">arXiv:1212.4908</a> <span> [<a href="https://arxiv.org/pdf/1212.4908">pdf</a>, <a href="https://arxiv.org/ps/1212.4908">ps</a>, <a href="https://arxiv.org/format/1212.4908">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Mathematical Physics">math-ph</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.4064/dm502-0-1">10.4064/dm502-0-1 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Rapid mixing of Swendsen-Wang dynamics in two dimensions </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1212.4908v2-abstract-short" style="display: inline;"> We prove comparison results for the Swendsen-Wang (SW) dynamics, the heat-bath (HB) dynamics for the Potts model and the single-bond (SB) dynamics for the random-cluster model on arbitrary graphs. In particular, we prove that rapid mixing of HB implies rapid mixing of SW on graphs with bounded maximum degree and that rapid mixing of SW and rapid mixing of SB are equivalent. Additionally, the spect… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1212.4908v2-abstract-full').style.display = 'inline'; document.getElementById('1212.4908v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1212.4908v2-abstract-full" style="display: none;"> We prove comparison results for the Swendsen-Wang (SW) dynamics, the heat-bath (HB) dynamics for the Potts model and the single-bond (SB) dynamics for the random-cluster model on arbitrary graphs. In particular, we prove that rapid mixing of HB implies rapid mixing of SW on graphs with bounded maximum degree and that rapid mixing of SW and rapid mixing of SB are equivalent. Additionally, the spectral gap of SW and SB on planar graphs is bounded from above and from below by the spectral gap of these dynamics on the corresponding dual graph with suitably changed temperature. As a consequence we obtain rapid mixing of the Swendsen-Wang dynamics for the Potts model on the two-dimensional square lattice at all non-critical temperatures as well as rapid mixing for the two-dimensional Ising model at all temperatures. Furthermore, we obtain new results for general graphs at high or low enough temperatures. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1212.4908v2-abstract-full').style.display = 'none'; document.getElementById('1212.4908v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 14 May, 2014; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 19 December, 2012; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2012. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Ph.D. thesis, 66 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 60K35; 60J10; 82C20 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Dissertationes Math. 502 (2014), 64 pp </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1212.4512">arXiv:1212.4512</a> <span> [<a href="https://arxiv.org/pdf/1212.4512">pdf</a>, <a href="https://arxiv.org/format/1212.4512">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1214/ECP.v18-2507">10.1214/ECP.v18-2507 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Positivity of hit-and-run and related algorithms </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Rudolf%2C+D">Daniel Rudolf</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1212.4512v2-abstract-short" style="display: inline;"> We prove positivity of the Markov operators that correspond to the hit-and-run algorithm, random scan Gibbs sampler, slice sampler and an Metropolis algorithm with positive proposal. In all of these cases the positivity is independent of the state space and the stationary distribution. In particular, the results show that it is not necessary to consider the lazy versions of these Markov chains. Th… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1212.4512v2-abstract-full').style.display = 'inline'; document.getElementById('1212.4512v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1212.4512v2-abstract-full" style="display: none;"> We prove positivity of the Markov operators that correspond to the hit-and-run algorithm, random scan Gibbs sampler, slice sampler and an Metropolis algorithm with positive proposal. In all of these cases the positivity is independent of the state space and the stationary distribution. In particular, the results show that it is not necessary to consider the lazy versions of these Markov chains. The proof relies on a well known lemma which relates the positivity of the product M T M^*, for some operators M and T, to the positivity of T. It remains to find that kind of representation of the Markov operator with a positive operator T. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1212.4512v2-abstract-full').style.display = 'none'; document.getElementById('1212.4512v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 12 November, 2013; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 18 December, 2012; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2012. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 60J05 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Electron. Commun. Probab. 18 (2013), no. 49, 1-8 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1211.0871">arXiv:1211.0871</a> <span> [<a href="https://arxiv.org/pdf/1211.0871">pdf</a>, <a href="https://arxiv.org/ps/1211.0871">ps</a>, <a href="https://arxiv.org/format/1211.0871">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Numerical Analysis">math.NA</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1090/S0025-5718-2014-02855-X">10.1090/S0025-5718-2014-02855-X <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> The Curse of Dimensionality for Numerical Integration of Smooth Functions </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Hinrichs%2C+A">Aicke Hinrichs</a>, <a href="/search/math?searchtype=author&query=Novak%2C+E">Erich Novak</a>, <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a>, <a href="/search/math?searchtype=author&query=Wozniakowski%2C+H">Henryk Wozniakowski</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1211.0871v2-abstract-short" style="display: inline;"> We prove the curse of dimensionality for multivariate integration of C^r functions: The number of needed function values to achieve an error 蔚 is larger than c_r (1+纬)^d for 蔚\le 蔚_0, where c_r,纬>0 and d is the dimension. The proofs are based on volume estimates for r=1 together with smoothing by convolution. This allows us to obtain smooth fooling functions for r>1. </span> <span class="abstract-full has-text-grey-dark mathjax" id="1211.0871v2-abstract-full" style="display: none;"> We prove the curse of dimensionality for multivariate integration of C^r functions: The number of needed function values to achieve an error 蔚 is larger than c_r (1+纬)^d for 蔚\le 蔚_0, where c_r,纬>0 and d is the dimension. The proofs are based on volume estimates for r=1 together with smoothing by convolution. This allows us to obtain smooth fooling functions for r>1. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1211.0871v2-abstract-full').style.display = 'none'; document.getElementById('1211.0871v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 16 April, 2013; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 5 November, 2012; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2012. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">15 pages, minor revision</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 65D30; 65Y20; 41A63; 41A55 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Math. Comp. 83 (2014), 2853-2863 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1202.6321">arXiv:1202.6321</a> <span> [<a href="https://arxiv.org/pdf/1202.6321">pdf</a>, <a href="https://arxiv.org/ps/1202.6321">ps</a>, <a href="https://arxiv.org/format/1202.6321">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Mathematical Physics">math-ph</span> </div> </div> <p class="title is-5 mathjax"> Rapid mixing of Swendsen-Wang and single-bond dynamics in two dimensions </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1202.6321v1-abstract-short" style="display: inline;"> We prove that the spectral gap of the Swendsen-Wang dynamics for the random-cluster model on arbitrary graphs with m edges is bounded above by 16 m log m times the spectral gap of the single-bond (or heat-bath) dynamics. This and the corresponding lower bound imply that rapid mixing of these two dynamics is equivalent. Using the known lower bound on the spectral gap of the Swendsen-Wang dynamics… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1202.6321v1-abstract-full').style.display = 'inline'; document.getElementById('1202.6321v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1202.6321v1-abstract-full" style="display: none;"> We prove that the spectral gap of the Swendsen-Wang dynamics for the random-cluster model on arbitrary graphs with m edges is bounded above by 16 m log m times the spectral gap of the single-bond (or heat-bath) dynamics. This and the corresponding lower bound imply that rapid mixing of these two dynamics is equivalent. Using the known lower bound on the spectral gap of the Swendsen-Wang dynamics for the two dimensional square lattice $Z_L^2$ of side length L at high temperatures and a result for the single-bond dynamics on dual graphs, we obtain rapid mixing of both dynamics on $\Z_L^2$ at all non-critical temperatures. In particular this implies, as far as we know, the first proof of rapid mixing of a classical Markov chain for the Ising model on $\Z_L^2$ at all temperatures. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1202.6321v1-abstract-full').style.display = 'none'; document.getElementById('1202.6321v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 28 February, 2012; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2012. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">20 pages</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1201.5793">arXiv:1201.5793</a> <span> [<a href="https://arxiv.org/pdf/1201.5793">pdf</a>, <a href="https://arxiv.org/ps/1201.5793">ps</a>, <a href="https://arxiv.org/format/1201.5793">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Mathematical Physics">math-ph</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1137/120864003">10.1137/120864003 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Swendsen-Wang is faster than single-bond dynamics </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1201.5793v2-abstract-short" style="display: inline;"> We prove that the spectral gap of the Swendsen-Wang dynamics for the random-cluster model is larger than the spectral gap of a single-bond dynamics, that updates only a single edge per step. For this we give a representation of the algorithms on the joint (Potts/random-cluster) model. Furthermore we obtain upper and lower bounds on the mixing time of the single-bond dynamics on the discrete $d$-di… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1201.5793v2-abstract-full').style.display = 'inline'; document.getElementById('1201.5793v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1201.5793v2-abstract-full" style="display: none;"> We prove that the spectral gap of the Swendsen-Wang dynamics for the random-cluster model is larger than the spectral gap of a single-bond dynamics, that updates only a single edge per step. For this we give a representation of the algorithms on the joint (Potts/random-cluster) model. Furthermore we obtain upper and lower bounds on the mixing time of the single-bond dynamics on the discrete $d$-dimensional torus of side length $L$ at the Potts transition temperature for $q$ large enough that are exponential in $L^{d-1}$, complementing a result of Borgs, Chayes and Tetali. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1201.5793v2-abstract-full').style.display = 'none'; document.getElementById('1201.5793v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 January, 2014; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 27 January, 2012; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2012. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">17 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> Primary; 60J10; Secondary; 60K35; 68Q87 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> SIAM J. Discrete Math. 28 (2014), pp. 37-48 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1105.3665">arXiv:1105.3665</a> <span> [<a href="https://arxiv.org/pdf/1105.3665">pdf</a>, <a href="https://arxiv.org/ps/1105.3665">ps</a>, <a href="https://arxiv.org/format/1105.3665">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Mathematical Physics">math-ph</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1002/rsa.20431">10.1002/rsa.20431 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Comparison of Swendsen-Wang and Heat-Bath Dynamics </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1105.3665v2-abstract-short" style="display: inline;"> We prove that the spectral gap of the Swendsen-Wang process for the Potts model on graphs with bounded degree is bounded from below by some constant times the spectral gap of any single-spin dynamics. This implies rapid mixing of the Swendsen-Wang process for the two-dimensional Potts model at all temperatures above the critical one, as well as rapid mixing at the critical temperature for the Isin… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1105.3665v2-abstract-full').style.display = 'inline'; document.getElementById('1105.3665v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1105.3665v2-abstract-full" style="display: none;"> We prove that the spectral gap of the Swendsen-Wang process for the Potts model on graphs with bounded degree is bounded from below by some constant times the spectral gap of any single-spin dynamics. This implies rapid mixing of the Swendsen-Wang process for the two-dimensional Potts model at all temperatures above the critical one, as well as rapid mixing at the critical temperature for the Ising model. After this we introduce a modified version of the Swendsen-Wang algorithm for planar graphs and prove rapid mixing for the two-dimensional Potts models at all non-critical temperatures. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1105.3665v2-abstract-full').style.display = 'none'; document.getElementById('1105.3665v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 22 May, 2013; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 18 May, 2011; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2011. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">22 pages, 1 figure</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Random Struct. Algorithms 42 (2013), 520-535 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1012.3944">arXiv:1012.3944</a> <span> [<a href="https://arxiv.org/pdf/1012.3944">pdf</a>, <a href="https://arxiv.org/ps/1012.3944">ps</a>, <a href="https://arxiv.org/format/1012.3944">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Mathematical Physics">math-ph</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1515/9783110293586.223">10.1515/9783110293586.223 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Exact Sampling for the Ising Model at all Temperatures </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/math?searchtype=author&query=Ullrich%2C+M">Mario Ullrich</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1012.3944v2-abstract-short" style="display: inline;"> We give a survey of the known results on mixing time of Glauber dynamics for the Ising model on the square lattice and present a technique that makes exact sampling of the Ising model at all temperatures possible in polynomial time. At high temperatures this is well-known and although this seems to be known also in the low temperature case since Kramer and Waniers paper from the 1950s, we did not… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1012.3944v2-abstract-full').style.display = 'inline'; document.getElementById('1012.3944v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1012.3944v2-abstract-full" style="display: none;"> We give a survey of the known results on mixing time of Glauber dynamics for the Ising model on the square lattice and present a technique that makes exact sampling of the Ising model at all temperatures possible in polynomial time. At high temperatures this is well-known and although this seems to be known also in the low temperature case since Kramer and Waniers paper from the 1950s, we did not found any reference that describes exact sampling for the Ising model at low temperatures. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1012.3944v2-abstract-full').style.display = 'none'; document.getElementById('1012.3944v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 11 May, 2011; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 17 December, 2010; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2010. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">12 pages, title and abstract changed</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Monte Carlo methods and applications, Proceedings of 8th IMACS Seminar on Monte Carlo Methods, 223-233, De Gruyter Proc. Math., De Gruyter, Berlin, 2013 </p> </li> </ol> <div class="is-hidden-tablet">  <span class="help" style="display: inline-block;"><a href="https://github.com/arXiv/arxiv-search/releases">Search v0.5.6 released 2020-02-24</a>  </span> </div> </div> </main> <footer> <div class="columns is-desktop" role="navigation" aria-label="Secondary">  <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/about">About</a></li> <li><a href="https://info.arxiv.org/help">Help</a></li> </ul> </div> <div class="column"> <ul class="nav-spaced"> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>contact arXiv</title><desc>Click here to contact arXiv</desc><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg> <a href="https://info.arxiv.org/help/contact.html"> Contact</a> </li> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>subscribe to arXiv mailings</title><desc>Click here to subscribe</desc><path d="M476 3.2L12.5 270.6c-18.1 10.4-15.8 35.6 2.2 43.2L121 358.4l287.3-253.2c5.5-4.9 13.3 2.6 8.6 8.3L176 407v80.5c0 23.6 28.5 32.9 42.5 15.8L282 426l124.6 52.2c14.2 6 30.4-2.9 33-18.2l72-432C515 7.8 493.3-6.8 476 3.2z"/></svg> <a href="https://info.arxiv.org/help/subscribe"> Subscribe</a> </li> </ul> </div> </div> </div>   <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/license/index.html">Copyright</a></li> <li><a href="https://info.arxiv.org/help/policies/privacy_policy.html">Privacy Policy</a></li> </ul> </div> <div class="column sorry-app-links"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/web_accessibility.html">Web Accessibility Assistance</a></li> <li> <p class="help"> <a class="a11y-main-link" href="https://status.arxiv.org" target="_blank">arXiv Operational Status <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 256 512" class="icon filter-dark_grey" role="presentation"><path d="M224.3 273l-136 136c-9.4 9.4-24.6 9.4-33.9 0l-22.6-22.6c-9.4-9.4-9.4-24.6 0-33.9l96.4-96.4-96.4-96.4c-9.4-9.4-9.4-24.6 0-33.9L54.3 103c9.4-9.4 24.6-9.4 33.9 0l136 136c9.5 9.4 9.5 24.6.1 34z"/></svg></a><br> Get status notifications via <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/email/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg>email</a> or <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/slack/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512" class="icon filter-black" role="presentation"><path d="M94.12 315.1c0 25.9-21.16 47.06-47.06 47.06S0 341 0 315.1c0-25.9 21.16-47.06 47.06-47.06h47.06v47.06zm23.72 0c0-25.9 21.16-47.06 47.06-47.06s47.06 21.16 47.06 47.06v117.84c0 25.9-21.16 47.06-47.06 47.06s-47.06-21.16-47.06-47.06V315.1zm47.06-188.98c-25.9 0-47.06-21.16-47.06-47.06S139 32 164.9 32s47.06 21.16 47.06 47.06v47.06H164.9zm0 23.72c25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06H47.06C21.16 243.96 0 222.8 0 196.9s21.16-47.06 47.06-47.06H164.9zm188.98 47.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06h-47.06V196.9zm-23.72 0c0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06V79.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06V196.9zM283.1 385.88c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06v-47.06h47.06zm0-23.72c-25.9 0-47.06-21.16-47.06-47.06 0-25.9 21.16-47.06 47.06-47.06h117.84c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06H283.1z"/></svg>slack</a> </p> </li> </ul> </div> </div> </div>  </div> </footer> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/member_acknowledgement.js"></script> </body> </html>

CINXE.COM

Search | arXiv e-print repository