Questions tagged [approximation-theory]

Approximation theory is concerned with how functions can best be approximated with simpler functions, and with quantitatively characterizing the errors introduced thereby.

195 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
16 votes
1 answer
562 views

Approximating zero sets of real polynomials with "less complicated" polynomials

Let $K \subset \mathbb{R}^n$ be a compact subset, and let $P(x_1,\dots,x_n)$ be a real multivariable polynomial of degree $d$, whose vanishing set we denote by $Z_P$. Is it plausible to approximate $...
SMS's user avatar
  • 1,293
15 votes
0 answers
516 views

Functions approximated by rolling epicycle curves

Imagine a decreasing sequence of (positive) radii $r_1 > r_2 > r_3 > \cdots$ and a series of nested circles $C_1 \supset C_2 \supset C_3 \supset \cdots$ with these radii, initially each ...
Joseph O'Rourke's user avatar
11 votes
0 answers
200 views

Degree of 2-variable real polynomial that’s large on a square and small on a nearby “L”

I’d like to know what’s the minimum possible total degree of a real polynomial $p(x,y)$ such that: (1) $p(x,y)\in [0,1]$ whenever $x,y\in [0,1]$ with either $x$ or $y$ at most $\epsilon$, and (2) $p(...
Scott Aaronson's user avatar
9 votes
0 answers
546 views

Padé approximations of $e$

The following question came up in the analysis of some algorithm. Let $R_{s,t}(z)$ be the Padé approximants of $e^z$, and define $r_{s,t} = R_{s,t}(1)$. Using the explicit expression for the error ...
Yuval Filmus's user avatar
  • 1,886
8 votes
0 answers
146 views
+100

L^2 polynomial approximation in higher dimensions

Let $\mu$ be a measure on $\mathbb{R}^n$ I'm looking for known upper-bounds on $$\| f-P_m \|_{L^2(\mu)} $$ where $P_n$ is the orthogonal projection of $f$ onto the polynomials of degree less than $m$. ...
Gericault's user avatar
  • 225
8 votes
0 answers
513 views

Concave and other bounded functions: Series representation and converging polynomials

Main Question Suppose $f:[0,1]\to[0,1]$ is continuous, polynomially bounded, and belongs to a large class of functions (for example, the $k$-th derivative, $k\ge 0$, is continuous, Lipschitz ...
Peter O.'s user avatar
  • 637
8 votes
0 answers
167 views

Padé Approximants of Power Series with Natural Boundaries

Consider a power series $\sum_{n=0}^{\infty}c_{n}z^{n}$ for which $c_{n}\in\left\{ 0,1\right\}$ for all $n$. One can write this as: $$\varsigma_{V}\left(z\right)\overset{\textrm{def}}{=}\sum_{v\in V}...
MCS's user avatar
  • 1,256
8 votes
0 answers
682 views

The function space defined by deep neural nets

Given a deep net graph and the activation functions on the hidden vertices do we have a description of the function space spanned by it? (even if for some specific architectures and activation ...
gradstudent's user avatar
  • 2,136
8 votes
0 answers
637 views

Approximating Lie groups by finite groups

How can one approximate compact Lie groups by finite groups? My wish is something like this: Let $G$ be a compact Lie group. There is a sequence of nested finite subgroups $G_n$ so that $G_n\to G$...
Joonas Ilmavirta's user avatar
8 votes
0 answers
583 views

convergence rate in Wiener's approximation theorem

Wiener has the following fantastic results about approximations using translation families: Given a function $h: \mathbb{R} \to \mathbb{R}$, the set $\{\sum a_i h(\cdot - x_i): a_i, x_i \in \mathbb{...
gondolier's user avatar
  • 1,829
7 votes
0 answers
225 views

Uniform approximation of separately continuous functions on zero-dimensional spaces

For topological spaces $X,Y,Z$ а function $f:X\times Y\to Z$ is called separately continuous if for any $(x,y)\in X\times Y$ the restrictions of $f$ to the sets $\{x\}\times Y$ and $X\times \{y\}$ are ...
Taras Banakh's user avatar
  • 40.8k
7 votes
0 answers
172 views

On derivatives of polynomials majorized by $\max(1,|x|^d)$

In the course of generalizing the Bernstein-Markov theorem to normed space, Harris came up with the following question. Suppose that $p$ is a real polynomial satisfying $|p(x)| \leq (1+|x|)^d$. How ...
Yuval Filmus's user avatar
  • 1,886
6 votes
0 answers
400 views

Using the Lorentz operators to build polynomials that converge to a continuous function

Questions Let $f(\lambda):[0,1]\to (0,1)$ have a $\beta-\lfloor\beta\rfloor$)-Hölder continuous $\lfloor\beta\rfloor$-th derivative, where $\beta>0$. Find explicit bounds, with no hidden constants,...
Peter O.'s user avatar
  • 637
6 votes
0 answers
306 views

Can we approximate any eigenvalue of an infinite matrix via eigenvalues of some sequence of submatrices which approximates the matrix?

Let $T:\ell^2\to\ell^2$ be a compact linear operator. Let $[T]=(a_{i,j})_{i,j=1}^{\infty}$ be the representing infinite matrix of $T$ with respect to the canonical base. Let $T_n$ be the finite rank ...
Chilote's user avatar
  • 586
6 votes
0 answers
103 views

Uniform approximation of a continuous flow by a $\mathcal{C}^1$ flow

Setup: Consider a (smooth) compact Riemannian manifold $M$, whose distance is denoted by $d$. Let $\Phi$ be a continuous flow, namely a continuous application from $\mathbb{R} \times M $ to $M$ ...
Thibault Lefeuvre's user avatar
6 votes
0 answers
375 views

Basis functions for approximation of a convex function on unit simplex

Consider the unit $D$-simplex $S^D=\left\lbrace (x_0, x_1, \ldots, x_D) \in \mathbb{R}^{D+1} \mid \sum\limits_{i=0}^{D}x_i = 1, x_i \geq 0 \right\rbrace$. I have a bounded, convex function $f:S^D\to\...
mikkola's user avatar
  • 171
6 votes
0 answers
206 views

Degree of Chebyshev polynomial necessary

In general, given $0<a<1$, I want to find a polynomial $f(x)\in\Bbb R[x]$ such that $f(x)\in[1-\frac{a}2,1+\frac{a}2]$ at every $x\in[1-a,1+a]$ and $f(0)=0$. What is minimum degree that is ...
Turbo's user avatar
  • 13.7k
6 votes
0 answers
505 views

Which functions can be approximated by piecewise constant functions?

Let $\Omega \subset \mathbb{R}^d$ be a connected and bounded domain. We call a function $f\in L^\infty(\Omega)$ nice if for each $\epsilon>0$ there exist $n\in \mathbb{N}, a_1,\dots,a_n \in \mathbb{...
user35593's user avatar
  • 2,286
6 votes
0 answers
185 views

what books to read to quickly understand adiabatic approximation

Hi group, I'm a theoretical ecologist with fairly adequate training in applied math (ODE, linear algebra, applied probability, some PDEs). In my current work, I've encountered the use of adiabatic ...
user22624's user avatar
6 votes
0 answers
271 views

Polynomial upper approximation with respect to the Gaussian measure

Let $f = 1_{[a,+\infty)}$ be the indicator function of a half-line. Does there exist a sequence $(P_n)$ of polynomials such that $f(x) \leq P_n(x)$ for every real $x$ and $$ \lim_{n\to \infty} \int_{\...
Guillaume Aubrun's user avatar
5 votes
0 answers
165 views

Standard function spaces with the approximation property

A Banach space $\mathcal{X}$ is said to have the approximation property (AP) if, for every compact set $K \subset \mathcal{X}$, there is a sequence of finite rank operators $\{U_n : \mathcal{X} \to \...
Nikola Kovachki's user avatar
5 votes
0 answers
219 views

Can we construct a computable sequence of trigonometric polynomials that converges pointwise to a given continuous function defined on the torus?

Consider any continuous function $f$ on an $m$-dimensional torus $\mathbb{T}^m$. Can we construct a sequence of band limited functions (trigonometric plynomials), with the band width (degree of the ...
Rajesh D's user avatar
  • 704
5 votes
0 answers
257 views

$L^p$-convergence of truncated Legendre series approximation to inverse error function $\text{erfinv}$

Bounding the $L^p$-error for an $n$-th order Legendre series approximation I have function $f\,\colon (-1, 1) \to \mathbb{R}$ where $f \in L^q(-1, 1)$ for any $q \geq 1$. I approximate $f$ using a ...
oliversm's user avatar
  • 201
5 votes
0 answers
197 views

On effective constructions in the functional analysis of Volterra's integration operator

Let $V: L^2(0,1) \to L^2(0,1)$ be the Volterra integration operator: $V(f)(x) := \int_0^x f(t) \, dt$. Is there a universal function $C(L,\varepsilon) < \infty$ such that the following uniform ...
Vesselin Dimitrov's user avatar
5 votes
0 answers
195 views

What are the possible $L^{\infty}$ closures of an integration-invariant linear subspace of $C([0,1],\mathbb{R})$?

Let $S \subset C([0,1],\mathbb{R})$ be an $\mathbb{R}$-linear subspace that is invariant under the $T := \int_0^x$ integration operation: if $g \in S$ then the function $f = Tg$ defined pointwise by $...
Vesselin Dimitrov's user avatar
5 votes
0 answers
327 views

Are inclusions from spaces of $C^\infty$ sections into spaces of $C^k$ sections homotopy equivalences?

[EDIT: The answer to my original question was obviously no, as user56365 pointed out. Here is what I should have asked.] For finite-dimensional smooth manifolds $E,M$, let $E\to M$ be a smooth fibre ...
Marc Nardmann's user avatar
5 votes
0 answers
321 views

Approximation by polynomials

The following is a well-known theorem (see e.g. The Chebyshev Polynomial by Rivlin): If $p(x) = x^n + a_{n_1} x^{n-1} + \ldots + a_0$, then $\max_{-1\leq x \leq 1} |p(x)| \geq 2^{1-n}$ for $n \geq 1$ ...
Navin Goyal's user avatar
5 votes
0 answers
400 views

Approximations of negative Sobolev norms

Consider the standard Cahn-Hilliard free energy, augmented by a nonlocal interaction term which measures the $H^{-1}$ norm of a zero-mean function. Could someone point me to a reference where this ...
Nilima Nigam's user avatar
  • 1,161
4 votes
0 answers
98 views

Interpolation on Sobolev space on $[0, 1]^d$ over finite meshes

Let $\Omega = [0, 1]^d$ and suppose that $f \colon \Omega \to \mathbb{R}$ lies in order $m > d/2$ Sobolev space; i.e., $$ \|f\|_{H^m(\Omega)}^2 = \sum_{|\alpha| \leq m} \|D^\alpha f\|_{L^2(\Omega)}^...
Drew Brady's user avatar
4 votes
0 answers
542 views

Bounds on the expectation of a function of a hypergeometric random variable: A "Jensen gap"

Main Question Let $f:[0,1]\to [0,1]$ be continuous, let $B_n(f)$ be the $n$-th degree Bernstein polynomial of $f$, and let $r\ge 3$. Given certain assumptions on $f$, what is an explicit and tight ...
Peter O.'s user avatar
  • 637
4 votes
0 answers
102 views

Asymptotics in the Chebyshev-type optimization problem

Let $g(x)\colon [-2,2]\to \mathbb{R}$ be a continuous function. Let $f_n(x)$ be a polynomial of degree $n$ such that $\log |f_n(x)|\leqslant ng(x)$ for all $x\in [-2,2]$. Then the maximal possible ...
Fedor Petrov's user avatar
4 votes
0 answers
103 views

Walsh-Lebesgue type theorem in $\Bbb R^{2m}$ for $m>1$

Is someone aware of any analogue of the Walsh-Lebesgue theorem in $\mathbb{R}^{2m}$ for $m>1$ and dealing with polyharmonic polynomials? In this post, $\phi$ is said to be polyharmonic in $\mathbb{...
Pierre's user avatar
  • 41
4 votes
0 answers
154 views

Covering number of smooth functions from $\mathbb{R}^d$ to $\mathbb{R}$

Let $(\mathcal{X},d)$ be a space of function $f: \mathbb{R}^d \to \mathbb{R}$ where $d=\| \cdot \|_\infty$ (i.e., $d(f)= \sup_{x\in \mathbb{R}^d} |f(x)|$ ). Let $D_\alpha f= \frac{\partial^\alpha}{ \...
Lisa's user avatar
  • 141
4 votes
0 answers
479 views

analytic approximations of the min and max operators

Question: What is the state of the art on analytic approximations of $\min$ and $\max$? My hunch is that numerical analysts probably have a better solution than the one I propose here. For any $\...
Aidan Rocke's user avatar
  • 3,827
4 votes
0 answers
83 views

Can we approximate harmonic maps which are a.e. orientation-preserving with maps which preserve orientation globally?

Let $\mathbb{D}^n$ be the closed unit ball, and let $f:\mathbb{D}^n \to \mathbb{R}^n$ be harmonic; More precisely, I assume that $f$ is real-analytic and harmonic on the interior $(\mathbb{D}^n)^o$ ...
Asaf Shachar's user avatar
  • 6,611
4 votes
0 answers
227 views

Orthonormal Basis of Multi-Dimensional Sobolev Space of Different Orders without Reproducing Kernel

Let $\Omega$ be an open subset of $\mathbb{R}^d$. Under regularity conditions, we know that the $s$-th order Sobolev space $H^s(\Omega)$ with $s \geq d/2$ is a reproducing kernel Hilbert space. In ...
Minkov's user avatar
  • 1,117
4 votes
0 answers
282 views

When (if ever) are the weights from Smolyak (sparse grid) cubature positive?

Are there any $1$-dimensional quadrature rules of arbitrary accuracy, on either $[0,1]$ or $\mathbb{R}$, with any non-trivial weight function, such that the associated $N$-dimensional cubature rule ...
cfp's user avatar
  • 183
4 votes
0 answers
80 views

Polynomial approximations on the Boolean hypercube

Given $\vec{a} \in \mathbb{R}^n$ and $b \in \mathbb{R}$ consider the function $f(x) = Th[\vec{a}.\vec{x}+b]$ on $x \in \{-1,1\}^n$ such that the ``threshold function (Th)" gives $1$ when the argument ...
gradstudent's user avatar
  • 2,136
4 votes
0 answers
238 views

Algebras and $\sigma$-algebras associated to random variables

Let $\{v_\lambda:~\lambda\in\Lambda\}$ be a family of real-valued random variables on a (complete) probability space $(\Omega, \sigma, \mathbb{P})$. Assume the variables lie in $\bigcap_{p=1}^\infty L^...
Ollie's user avatar
  • 1,391
4 votes
0 answers
709 views

Estimating overshoot in spline interpolation

Say I have a spline space $\mathcal S$ of dimension $n$ with a set of unisolvent points $(\xi_i)_{i=1}^n$, i.e., points at which I can unambiguously interpolate within the spline space. So, given ...
cfh's user avatar
  • 278
4 votes
0 answers
144 views

The closures in $C^0(\mathbb C,\mathbb C)$ of the set of integer valued polynomials

This question is closely related to the thread The closures in $C^0(\mathbb R,\mathbb R)$ of the set of integer valued polynomials, resp, of polynomials with integer coefficients. (Recall that a ...
joaopa's user avatar
  • 3,655
4 votes
0 answers
130 views

The proximality of low rank function approximation

The paper "Best $n$-Dimensional approximation to sets of functions" by A. L. Brown in 1964 gave a negative answer to the following question: Q1: Is there for a given integer $n$ always a best ...
alext87's user avatar
  • 3,167
4 votes
0 answers
2k views

Approximation of continuous functions by Lipschitz functions in the topology of uniform convergence on compact sets

I was involved into this subject when I answered this question from MSE. Trying to generalize my answer, I am thinking about a following Question. Let $X$ and $Y$ be metric spaces. When each ...
Alex Ravsky's user avatar
  • 4,102
3 votes
0 answers
162 views

Rate of uniform approximation by piecewise constant functions

Definitions and Notation: Fix a positive constant $M>0$ with positive integers $m,n$ and the standard orthonormal basis $e_1,\dots,e_n$ of $\mathbb{R}^n$. For every positive integer $N$, define the ...
ABIM's user avatar
  • 5,019
3 votes
0 answers
355 views

A conjecture on consistent monotone sequences of polynomials in Bernstein form

A Conjecture In the following, a polynomial $P(x)$ is written in Bernstein form of degree $n$ if it is written as— $$P(x)=\sum_{k=0}^n a_k {n \choose k} x^k (1-x)^{n-k},$$ where $a_0, ..., a_n$ are ...
Peter O.'s user avatar
  • 637
3 votes
1 answer
196 views

Smooth cut-off in homogeneous Besov space

Given a Littlewood-Paley decomposition $$1 = \chi(\xi) + \sum_{j \geq 0}\varphi(2^{-j} \xi), \quad \xi \in \mathbb R^n$$ where $\chi$ is smooth, supported on a ball, and $\varphi$ is smooth, supported ...
Desura's user avatar
  • 211
3 votes
0 answers
139 views

Chebyshev Equioscillation Theorem in presence of extra conditions

Let $P_\ell$ be polynomials of degree $\ell$. For $f \in C[0,1]$, define the minimax error $E_\ell(f) = \min_{p \in P_\ell} \max_{x \in [0,1]} |f(x) - p(x)|$. We know that for the above scenario the ...
Rahul Sarkar's user avatar
3 votes
0 answers
34 views

Do higher-order splines with Lipschitz derivatives exist on finite sets?

Fix $k\in \mathbb{N}^+$ and let $E=(e_i,f_i)_{i=1}^I\subset \mathbb{R}^n\times \mathbb{R}^m$ be a non-empty finite set with $e_i\neq e_j$ whenever $i\neq j$. If $n=m=1$ then it's easy to see that: $$ ...
ABIM's user avatar
  • 5,019
3 votes
0 answers
61 views

How to find or approximate (e.g. using method of steepest descent ) integral?

Can you give any advice on how to find or approximate the following integral $$ F(t,y) = \int_{0}^{y}\frac{i e^{-\frac{3 t^2 \left(x^2+1\right)}{2 \left(9 x^2+1\right)}-i \frac{4 t^2 x}{9 x^2+1}}}{\...
InchyChyn's user avatar
3 votes
0 answers
289 views

Lower bound of the modulus $|\eta(s)|$ of the Dirichlet Eta function if $0.6 < \Re(s) < 0.9$

Let $s=\sigma + it$, with $0.6 < \sigma < 1$ and $\sigma=\Re(s)$. I am trying to get good enough approximations for $\eta(s)$, hoping something useful might come out of it. I stumbled upon a ...
Vincent Granville's user avatar