Source author record

Tino Ullrich

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Catalog footprint

Research overview

21works
6topics
4close collaborators

Published work

21 publications

preprint2021arXiv

A new upper bound for sampling numbers

We provide a new upper bound for sampling numbers (gn)n∈N(g_n)_{n\in \mathbb{N}} associated to the compact embedding of a separable reproducing kernel Hilbert space into the space of square integrable functions. There are universal constants C,c>0C,c>0 (which are specified in the paper) such that gn2≤Clog⁡(n)n∑k≥⌊cn⌋σk2,n≥2 , g^2_n \leq \frac{C\log(n)}{n}\sum\limits_{k\geq \lfloor cn \rfloor} σ_k^2\quad,\quad n\geq 2\,, where (σk)k∈N(σ_k)_{k\in \mathbb{N}} is the sequence of singular numbers (approximation numbers) of the Hilbert-Schmidt embedding Id:H(K)→L2(D,ϱD)\text{Id}:H(K) \to L_2(D,\varrho_D). The algorithm which realizes the bound is a least squares algorithm based on a specific set of sampling nodes. These are constructed out of a random draw in combination with a down-sampling procedure coming from the celebrated proof of Weaver's conjecture, which was shown to be equivalent to the Kadison-Singer problem. Our result is non-constructive since we only show the existence of a linear sampling operator realizing the above bound. The general result can for instance be applied to the well-known situation of Hmixs(Td)H^s_{\text{mix}}(\mathbb{T}^d) in L2(Td)L_2(\mathbb{T}^d) with s>1/2s>1/2. We obtain the asymptotic bound gn≤Cs,dn−slog⁡(n)(d−1)s+1/2 , g_n \leq C_{s,d}n^{-s}\log(n)^{(d-1)s+1/2}\,, which improves on very recent results by shortening the gap between upper and lower bound to log⁡(n)\sqrt{\log(n)}.

preprint2020arXiv

A higher order Faber spline basis for sampling discretization of functions

This paper is devoted to the question of constructing a higher order Faber spline basis for the sampling discretization of functions with higher regularity than Lipschitz. The basis constructed in this paper has similar properties as the piecewise linear classical Faber-Schauder basis except for the compactness of the support. Although the new basis functions are supported on the real line they are very well localized (exponentially decaying) and the main parts are concentrated on a segment. This construction gives a complete answer to Problem 3.13 in Triebel's monograph (see References [47]) by extending the classical Faber basis to higher orders. Roughly, the crucial idea to obtain a higher order Faber spline basis is to apply Taylor's remainder formula to the dual Chui-Wang wavelets. As a first step we explicitly determine these dual wavelets which may be of independent interest. Using this new basis we provide sampling characterizations for Besov and Triebel-Lizorkin spaces and overcome the smoothness restriction coming from the classical piecewise linear Faber-Schauder system. This basis is unconditional and coefficient functionals are computed from discrete function values similar as for the Faber-Schauder situation.

preprint2020arXiv

Adaptive sampling recovery of functions with higher mixed regularity

We tensorize the Faber spline system from [14] to prove sequence space isomorphisms for multivariate function spaces with higher mixed regularity. The respective basis coefficients are local linear combinations of discrete function values similar as for the classical Faber Schauder system. This allows for a sparse representation of the function using a truncated series expansion by only storing discrete (finite) set of function values. The set of nodes where the function values are taken depends on the respective function in a non-linear way. Indeed, if we choose the basis functions adaptively it requires significantly less function values to represent the initial function up to accuracy ε>0\varepsilon>0 (say in L∞L_\infty) compared to hyperbolic cross projections. In addition, due to the higher regularity of the Faber splines we overcome the (mixed) smoothness restriction r<2r<2 and benefit from higher mixed regularity of the function. As a byproduct we present the solution of Problem 3.13 in the Triebel monograph [46] for the multivariate setting.

preprint2020arXiv

Entropy numbers of finite dimensional mixed-norm balls and function space embeddings with small mixed smoothness

We study the embedding id:ℓpb(ℓqd)→ℓrb(ℓud)\text{id}: \ell_p^b(\ell_q^d) \to \ell_r^b(\ell_u^d) and prove matching bounds for the entropy numbers ek(id)e_k(\text{id}) provided that 0<p<r≤∞0<p<r\leq \infty and 0<q≤u≤∞0<q\leq u\leq \infty. Based on this finding, we establish optimal dimension-free asymptotic rates for the entropy numbers of embeddings of Besov and Triebel-Lizorkin spaces of small dominating mixed smoothness which settles an open question in the literature. Both results rely on a novel covering construction recently found by Edmunds and Netrusov.

preprint2020arXiv

Gelfand numbers related to structured sparsity and Besov space embeddings with small mixed smoothness

We consider the problem of determining the asymptotic order of the Gelfand numbers of mixed-(quasi-)norm embeddings ℓpb(ℓqd)↪ℓrb(ℓud)\ell^b_p(\ell^d_q) \hookrightarrow \ell^b_r(\ell^d_u) given that p≤rp \leq r and q≤uq \leq u, with emphasis on cases with p≤1p\leq 1 and/or q≤1q\leq 1. These cases turn out to be related to structured sparsity. We obtain sharp bounds in a number of interesting parameter constellations. Our new matching bounds for the Gelfand numbers of the embeddings of ℓ1b(ℓ2d)\ell_1^b(\ell_2^d) and ℓ2b(ℓ1d)\ell_2^b(\ell_1^d) into ℓ2b(ℓ2d)\ell_2^b(\ell_2^d) imply optimality assertions for the recovery of block-sparse and sparse-in-levels vectors, respectively. In addition, we apply the sharp estimates for ℓpb(ℓqd)\ell^b_p(\ell^d_q)-spaces to obtain new two-sided estimates for the Gelfand numbers of multivariate Besov space embeddings in regimes of small mixed smoothness. It turns out that in some particular cases these estimates show the same asymptotic behaviour as in the univariate situation. In the remaining cases they differ at most by a log⁡log⁡\log\log factor from the univariate bound.

preprint2020arXiv

The Haar System in Triebel-Lizorkin Spaces: Endpoint Results

We characterize the Schauder and unconditional basis properties for the Haar system in the Triebel-Lizorkin spaces Fp,qs(Rd)F^s_{p,q}(\Bbb R^d), at the endpoint cases s=1s=1, s=d/p−ds=d/p-d and p=∞p=\infty. Together with the earlier results in [10], [4], this completes the picture for such properties in the Triebel-Lizorkin scale, and complements a similar study for the Besov spaces given in [5].

preprint2016arXiv

Counting via entropy: new preasymptotics for the approximation numbers of Sobolev embeddings

In this paper, we reveal a new connection between approximation numbers of periodic Sobolev type spaces, where the smoothness weights on the Fourier coefficients are induced by a (quasi-)norm ∥⋅∥\|\cdot\| on Rd\mathbb{R}^d, and entropy numbers of the embedding id:ℓ∥⋅∥d→ℓ∞d\textrm{id}: \ell_{\|\cdot\|}^d \to \ell_\infty^d. This connection yields preasymptotic error bounds for approximation numbers of isotropic Sobolev spaces, spaces of analytic functions, and spaces of Gevrey type in L2L_2 and H1H^1, which find application in the context of Galerkin methods. Moreover, we observe that approximation numbers of certain Gevrey type spaces behave preasymptotically almost identical to approximation numbers of spaces of dominating mixed smoothness. This observation can be exploited, for instance, for Galerkin schemes for the electronic Schrödinger equation, where mixed regularity is present.

preprint2016arXiv

General coorbit space theory for quasi-Banach spaces and inhomogeneous function spaces with variable smoothness and integrability

In this paper we propose a general coorbit space theory suitable to define coorbits of quasi-Banach spaces using an abstract continuous frame, indexed by a locally compact Hausdorff space, and an associated generalized voice transform. The proposed theory realizes a further step in the development of a universal abstract theory towards various function spaces and their atomic decompositions which has been initiated by Feichtinger and Gr{ö}chenig in the late 1980ies. We combine the recent approaches in Rauhut, Ullrich and Rauhut to identify, in particular, various inhomogeneous (quasi-Banach) spaces of Besov-Lizorkin-Triebel type. To prove the potential of our new theory we apply it to spaces with variable smoothness and integrability which have attracted significant interest in the last 10 years. From the abstract discretization machinery we obtain atomic decompositions as well as wavelet frame isomorphisms for these spaces.

preprint2016arXiv

On the orthogonality of the Chebyshev-Frolov lattice and applications

We deal with lattices that are generated by the Vandermonde matrices associated to the roots of Chebyshev-polynomials. If the dimension dd of the lattice is a power of two, i.e. d=2m,m∈Nd=2^m, m \in \mathbb{N}, the resulting lattice is an admissible lattice in the sense of Skriganov. Those are related to the Frolov cubature formulas, which recently drew attention due to their optimal convergence rates in a broad range of function spaces with mixed smoothness. We prove that the resulting lattices are orthogonal and possess a lattice representation matrix with entries not larger than 22 (in modulus). This allows for an efficient enumeration of the Frolov cubature nodes in the dd-cube [−1/2,1/2]d[-1/2,1/2]^d up to dimension d=16d=16.

preprint2016arXiv

The role of Frolov's cubature formula for functions with bounded mixed derivative

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 Bp,θs\mathbf{B}^s_{p,θ} and Triebel-Lizorkin spaces Fp,θs\mathbf{F}^s_{p,θ} and our results treat the whole range of admissible parameters (s≥1/p)(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 Fp,θs\mathbf{F}^s_{p,θ} in case 1<θ<p<∞1<θ<p<\infty with 1/p<s≤1/θ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/θ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.

preprint2016arXiv

Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness

We consider the approximate recovery of multivariate periodic functions from a discrete set of function values taken on a rank-ss integration lattice. The main result is the fact that any (non-)linear reconstruction algorithm taking function values on a rank-ss lattice of size MM has a dimension-independent lower bound of 2−(α+1)/2M−α/22^{-(α+1)/2} M^{-α/2} when considering the optimal worst-case error with respect to function spaces of (hybrid) mixed smoothness α>0α>0 on the dd-torus. We complement this lower bound with upper bounds that coincide up to logarithmic terms. These upper bounds are obtained by a detailed analysis of a rank-1 lattice sampling strategy, where the rank-1 lattices are constructed by a component-by-component (CBC) method. This improves on earlier results obtained in [25] and [27]. The lattice (group) structure allows for an efficient approximation of the underlying function from its sampled values using a single one-dimensional fast Fourier transform. This is one reason why these algorithms keep attracting significant interest. We compare our results to recent (almost) optimal methods based upon samples on sparse grids.

preprint2015arXiv

Optimal quasi-Monte Carlo rules on order 2 digital nets for the numerical integration of multivariate periodic functions

We investigate quasi-Monte Carlo rules for the numerical integration of multivariate periodic functions from Besov spaces Sp,qrB(Td)S^r_{p,q}B(\mathbb{T}^d) with dominating mixed smoothness 1/p<r<21/p<r<2. We show that order 2 digital nets achieve the optimal rate of convergence N−r(log⁡N)(d−1)(1−1/q)N^{-r} (\log N)^{(d-1)(1-1/q)}. The logarithmic term does not depend on rr and hence improves the known bound provided by J. Dick for the special case of Sobolev spaces Hmixr(Td)H^r_{\text{mix}}(\mathbb{T}^d). Secondly, the rate of convergence is independent of the integrability pp of the Besov space, which allows for sacrificing integrability in order to gain Besov regularity. Our method combines characterizations of periodic Besov spaces with dominating mixed smoothness via Faber bases with sharp estimates of Haar coefficients for the discrepancy function of higher order digital nets. Moreover, we provide numerical computations which indicate that this bound also holds for the case r=2r=2.

preprint2014arXiv

A new framework for generalized Besov-type and Triebel-Lizorkin-type spaces

In this paper, the authors propose a new framework under which a theory of generalized Besov-type and Triebel-Lizorkin-type function spaces is developed. Many function spaces appearing in harmonic analysis fall under the scope of this new framework. Among others, the boundedness of the Hardy-Littlewood maximal operator or the related vector-valued maximal function on any of these function spaces is not required to construct these generalized scales of smoothness spaces. Instead of this, a key idea used in this framework is an application of the Peetre maximal function. This idea originates from recent findings in the abstract coorbit space theory obtained by Holger Rauhut and Tino Ullrich. Under this new setting, the authors establish the boundedness of pseudo-differential operators based on atomic and molecular characterizations and also the boundedness of the Fourier multipliers. The characterizations of these function spaces by means of differences and oscillations are also established. As further applications of this new framework, the authors reexamine and polish some existing results for many different scales of function spaces.

preprint2014arXiv

Lower bounds for the integration error for multivariate functions with mixed smoothness and optimal Fibonacci cubature for functions on the square

We prove lower bounds for the error of optimal cubature formulae for dd-variate functions from Besov spaces of mixed smoothness Bp,θα(Gd)B^α_{p,θ}({\mathbb G}^d) in the case 0<p,θ≤∞0 < p, θ\le \infty and α>1/pα> 1/p, where Gd{\mathbb G}^d is either the dd-dimensional torus Td{\mathbb T}^d or the dd-dimensional unit cube Id{\mathbb I}^d. We prove upper bounds for QMC methods of integration on the Fibonacci lattice for bivariate periodic functions from Bp,θα(T2)B^α_{p,θ}({\mathbb T}^2) in the case 1≤p≤∞1\leq p \leq \infty, 0<θ≤∞0 < θ\leq \infty, α>1/pα>1/p. A non-periodic modification of this classical formula yields upper bounds for Bp,θα(I2)B^α_{p,θ}({\mathbb I}^2) if 1/p<α<1+1/p1/p<α<1+1/p. In combination these results yield the correct asymptotic error of optimal cubature formulae for functions from Bp,θα(G2)B^α_{p,θ}({\mathbb G}^2) and indicate that a corresponding result is most likely also true in case d>2d>2. This is compared to the correct asymptotic of optimal cubature formulae on Smolyak grids which results in the observation that any cubature formula on Smolyak grids is never optimal for the general setting.

preprint2014arXiv

Sampling on energy-norm based sparse grids for the optimal recovery of Sobolev type functions in HγH^γ

We investigate the rate of convergence of linear sampling numbers of the embedding Hα,β(Td)↪Hγ(Td)H^{α,β} (\mathbb{T}^d) \hookrightarrow H^γ(\mathbb{T}^d). Here αα governs the mixed smoothness and ββ the isotropic smoothness in the space Hα,β(Td)H^{α,β}(\mathbb{T}^d) of hybrid smoothness, whereas Hγ(Td)H^γ(\mathbb{T}^d) denotes the isotropic Sobolev space. If γ>βγ>β we obtain sharp polynomial decay rates for the first embedding realized by sampling operators based on "energy-norm based sparse grids" for the classical trigonometric interpolation. This complements earlier work by Griebel, Knapek and Dũng, Ullrich, where general linear approximations have been considered. In addition, we study the embedding Hmixα(Td)↪Hmixγ(Td)H^α_{mix} (\mathbb{T}^d) \hookrightarrow H^γ_{mix}(\mathbb{T}^d) and achieve optimality for Smolyak's algorithm applied to the classical trigonometric interpolation. This can be applied to investigate the sampling numbers for the embedding Hmixα(Td)↪Lq(Td)H^α_{mix} (\mathbb{T}^d) \hookrightarrow L_q(\mathbb{T}^d) for 2<q≤∞2<q\leq \infty where again Smolyak's algorithm yields the optimal order. The precise decay rates for the sampling numbers in the mentioned situations always coincide with those for the approximation numbers, except probably in the limiting situation β=γβ= γ (including the embedding into L2(Td)L_2(\mathbb{T}^d)). The best what we could prove there is a (probably) non-sharp results with a logarithmic gap between lower and upper bound.

preprint2013arXiv

Approximation of mixed order Sobolev functions on the dd-torus -- Asymptotics, preasymptotics and dd-dependence

We investigate the approximation of dd-variate periodic functions in Sobolev spaces of dominating mixed (fractional) smoothness s>0s>0 on the dd-dimensional torus, where the approximation error is measured in the L2−L_2-norm. In other words, we study the approximation numbers of the Sobolev embeddings Hmixs(Td)↪L2(Td)H^s_{\rm mix}(\mathbb{T}^d)\hookrightarrow L_2(\mathbb{T}^d), with particular emphasis on the dependence on the dimension dd. For any fixed smoothness s>0s>0, we find the exact asymptotic behavior of the constants as d→∞d\to\infty. We observe super-exponential decay of the constants in dd, if nn, the number of linear samples of ff, is large. In addition, motivated by numerical implementation issues, we also focus on the error decay that can be achieved by low rank approximations. We present some surprising results for the so-called ``preasymptotic'' decay and point out connections to the recently introduced notion of quasi-polynomial tractability of approximation problems.

preprint2013arXiv

Entropy and sampling numbers of classes of ridge functions

We study properties of ridge functions f(x)=g(a⋅x)f(x)=g(a\cdot x) in high dimensions dd from the viewpoint of approximation theory. The considered function classes consist of ridge functions such that the profile gg is a member of a univariate Lipschitz class with smoothness α>0α> 0 (including infinite smoothness), and the ridge direction aa has pp-norm ∥a∥p≤1\|a\|_p \leq 1. First, we investigate entropy numbers in order to quantify the compactness of these ridge function classes in L∞L_{\infty}. We show that they are essentially as compact as the class of univariate Lipschitz functions. Second, we examine sampling numbers and face two extreme cases. In case p=2p=2, sampling ridge functions on the Euclidean unit ball faces the curse of dimensionality. It is thus as difficult as sampling general multivariate Lipschitz functions, a result in sharp contrast to the result on entropy numbers. When we additionally assume that all feasible profiles have a first derivative uniformly bounded away from zero in the origin, then the complexity of sampling ridge functions reduces drastically to the complexity of sampling univariate Lipschitz functions. In between, the sampling problem's degree of difficulty varies, depending on the values of αα and pp. Surprisingly, we see almost the entire hierarchy of tractability levels as introduced in the recent monographs by Novak and Woźniakowski.

preprint2012arXiv

New Characterizations of Besov-Triebel-Lizorkin-Hausdorff Spaces Including Coorbits and Wavelets

In this paper, the authors establish new characterizations of the recently introduced Besov-type spaces B˙p,qs,τ(Rn)\dot{B}^{s,τ}_{p,q}({\mathbb R}^n) and Triebel-Lizorkin-type spaces F˙p,qs,τ(Rn)\dot{F}^{s,τ}_{p,q}({\mathbb R}^n) with p∈(0,∞]p\in (0,\infty], s∈Rs\in{\mathbb R}, τ∈[0,∞)τ\in [0,\infty), and q∈(0,∞]q\in (0,\infty], as well as their preduals, the Besov-Hausdorff spaces BH˙p,qs,τ(Rn)B\dot{H}^{s,τ}_{p,q}(\R^n) and Triebel-Lizorkin-Hausdorff spaces FH˙p,qs,τ(Rn)F\dot{H}^{s,τ}_{p,q}(\R^n), in terms of the local means, the Peetre maximal function of local means, and the tent space (the Lusin area function) in both discrete and continuous types. As applications, the authors then obtain interpretations as coorbits in the sense of H. Rauhut in [Studia Math. 180 (2007), 237-253] and discretizations via the biorthogonal wavelet bases for the full range of parameters of these function spaces. Even for some special cases of this setting such as F˙∞,qs(Rn)\dot F^s_{\infty,q}({\mathbb R}^n) for s∈Rs\in{\mathbb R}, q∈(0,∞]q\in (0,\infty] (including BMO(Rn)\mathop\mathrm{BMO} ({\mathbb R}^n) when s=0s=0, q=2q=2), the QQ space Qα(Rn)Q_α({\mathbb R}^n), the Hardy-Hausdorff space HH−α(Rn)HH_{-α}({\mathbb R}^n) for α∈(0,min⁡{n2,1})α\in (0,\min\{\frac n2,1\}), the Morrey space Mpu(Rn){\mathcal M}^u_p({\mathbb R}^n) for 1<p≤u<∞1<p\le u<\infty, and the Triebel-Lizorkin-Morrey space E˙upqs(Rn)\dot{\mathcal{E}}^s_{upq}({\mathbb R}^n) for 0<p≤u<∞0<p\le u<\infty, s∈Rs\in{\mathbb R} and q∈(0,∞]q\in(0,\infty], some of these results are new.

preprint2010arXiv

Continuous characterizations of Besov-Lizorkin-Triebel spaces and new interpretations as coorbits

We give characterizations for homogeneous and inhomogeneous Besov-Lizorkin-Triebel spaces in terms of continuous local means for the full range of parameters. In particular, we prove characterizations in terms of Lusin functions and spaces involving the Peetre maximal function to apply the classical coorbit space theory due to Feichtinger and Gröchenig. This results in atomic decompositions and wavelet bases for homogeneous spaces. In particular we give sufficient conditions for suitable wavelets in terms of moment, decay and smoothness conditions.

preprint2010arXiv

Generalized coorbit space theory and inhomogeneous function spaces of Besov-Lizorkin-Triebel type

Coorbit space theory is an abstract approach to function spaces and their atomic decompositions. The original theory developed by Feichtinger and Gr{ö}chenig in the late 1980ies heavily uses integrable representations of locally compact groups. Their theory covers, in particular, homogeneous Besov-Lizorkin-Triebel spaces, modulation spaces, Bergman spaces, and the recent shearlet spaces. However, inhomogeneous Besov-Lizorkin-Triebel spaces cannot be covered by their group theoretical approach. Later it was recognized by Fornasier and the first named author that one may replace coherent states related to the group representation by more general abstract continuous frames. In the first part of the present paper we significantly extend this abstract generalized coorbit space theory to treat a wider variety of coorbit spaces. A unified approach towards atomic decompositions and Banach frames with new results for general coorbit spaces is presented. In the second part we apply the abstract setting to a specific framework and study coorbits of what we call Peetre spaces. They allow to recover inhomogeneous Besov-Lizorkin-Triebel spaces of various types of interest as coorbits. We obtain several old and new wavelet characterizations based on precise smoothness, decay, and vanishing moment assumptions of the respective wavelet. As main examples we obtain results for weighted spaces (Muckenhoupt, doubling), general 2-microlocal spaces, Besov-Lizorkin-Triebel-Morrey spaces, spaces of dominating mixed smoothness, and even mixtures of the mentioned ones. Due to the generality of our approach, there are many more examples of interest where the abstract coorbit space theory is applicable.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.