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.
599 questions
8
votes
2
answers
486
views
Inductive definition of Bernstein polynomials
For $n\in \mathbb{N}$ let $B_n$ be the linear operator taking a function $f$ on the unit interval $I=[0,1]$ to its $n$-th Bernstein polynomial $B_nf$,
$$ B_nf(x):=\sum_{k=0}^n\binom{n}{k} f\Big(\...
- 60.6k
3
votes
0
answers
118
views
Hardness results for approximating Hölder continuous functions
Let $f \in \mathrm{Lip}^{L,\alpha}[a,b]$, and let $f_{h} \in C^{L}$ be a spline which interpolates $f$ at $a + ih$. Then standard theorems (Daubechies & Lagarias, SIAM J. Math. Anal. 22 (1991) ...
- 221
3
votes
0
answers
89
views
Reference request: Projection operators in metric spaces
Given a metric space $(X,d)$ and a subset $S\subset X$, the projection $P_S$ onto $S$ is well-defined as a set valued function. I am interested in learning more about properties of these projections ...
- 710
1
vote
1
answer
114
views
Example of a nonconvex Chebyshev set in a metric space with continuous projection?
Question: Is there an example of a nonconvex Chebyshev set $S$ in a metric space $(X,d)$ whose projection map is continuous?
For convexity to be well-defined, we need to assume that $X$ is a vector ...
- 710
4
votes
0
answers
509
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 $\...
- 3,871
4
votes
1
answer
386
views
Lower-bound for $\Pr[X \geq m]$ subject to $E[X]>m$ where $X$ is a binomial random variable
Given an integer number $m>0$ and a real number $\alpha\in [1, 2]$, I am interested in finding a lower-bound for $\Pr[X\geq m]$ subject to $X \sim \text{Binomial}(n, m\alpha/n)$.
For large values ...
- 189
5
votes
0
answers
294
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 ...
- 201
3
votes
2
answers
622
views
Interpolation nodes for linear spline (piecewise-linear) interpolation of $x \ln x$
I need to approximate $x \ln x$ on $[0,1]$ as a piecewise-linear function. If $P(x)$ is a piecewise-linear approximation, I want to minimize
$$
\max_{0 \le x \le 1} |P(x) - x \ln x| \rightarrow \min_P....
- 367
0
votes
0
answers
52
views
Probabilistic Approximation of non-linear Dynamical System by Diffusion Process
Setting
Suppose I have a discrete dynamical system given by:
$$
X^{n+1} = f(X^{n})
\qquad X^0 =x
,
$$
where $f$ is some diffeomorphism from $\mathbb{R}^{d}$ to itself, and some $x \in \mathbb{R}^d$. ...
- 5,405
5
votes
1
answer
347
views
Polynomial approximation (in $L^1$ norm) at minimal cost
Define the cost of a polynomial $\sum_{i=0}^N a_i x^n$ to be $\sum_{i=0}^N |a_i|$. Let $g:[0,1]\to \mathbb{R}$ be a function to be approximated — say, $g(x)=0$ if $0\leq x < e^{-1}$, $g(x)= 1/x$ ...
- 20.2k
0
votes
1
answer
488
views
Convergence of Chebyshev interpolation in L^1
Let $f\in C^0([-1,1])$ and $P_n(f)$ its interpolation polynomial at the Chebyshev nodes.
I would be interested to know about any existing results (positive or negative) about the convergence of $P_n(...
- 98
0
votes
0
answers
206
views
Any good references on the decay rate of Legendre coefficient?
Let $P_n:[-1,1]\rightarrow\mathbb{R}$ be the $n$-th Legendre Polynomial. and, let
$$a_n:=\int_{-1}^1 f(t) P_n(t)\, dt$$
for some $f:[-1,1]\rightarrow\mathbb{R}$.
Are there any good references on the ...
- 469
4
votes
1
answer
182
views
On the set of good approximators in the sense of Dirichlet's theorem
This question came up when thinking about an older question that hasn't been answered as of now.
Let $\mathbb{N}$ be the set of positive integers. If $\alpha\in\mathbb{R}$, we say $q\in\mathbb{N}$ is ...
- 48.9k
1
vote
1
answer
175
views
Density of the set of numbers that are "good approximators" to a given real in the sense of Dirichlet's approximation theorem
Let $\mathbb{N}$ be the set of positive integers. Given a set $A\subseteq \mathbb{N}$ we let the (upper) density of $A$ be defined by $$\mu^+(A) = \lim\sup_{n\to\infty}\frac{|A\cap\{1,\ldots,n\}|}{n}.$...
- 48.9k
0
votes
1
answer
163
views
Terminology and approximation to logarithm of a sum of products of binomial coefficients
Denote $$T(m)=\sum_{1\leq n_m\leq n_{m-1}\leq\dots\leq n_2\leq n_1\leq m}\prod_{i=1}^{m}\binom{n_i}{n_{i+1}}.$$
Is there a name for this kind of summation and is there a good estimate for $\ln T(m)$ ...
- 1,836
0
votes
1
answer
234
views
Logarithm of an integral involving generalized real binomial coefficients
I could not find a closed form for this integral although I think it should have been studied.
What is a good approximation to $I$ in
$$I=\ln\Bigg(\int_{0}^y\binom{2m}{m(1+x)}dx\Bigg)$$ where $0\...
- 1,836
0
votes
1
answer
407
views
Criteria for $\epsilon$-Density
Let $Y$ be a compact, separable metric space and $X=C(Y)$ Banach space. There are many criteria for a linear subspace $Z\subseteq X$ to be dense; notably the Stone-Weierstraß theorem.
Are there ...
- 5,405
2
votes
0
answers
194
views
Extension of universal approximation theorem
Let $I_d:=[0,1]^d$ with $d\ge 2$. Define $C(I_d):=\{F: I_d\to\mathbb R \mbox{ is continuous}\}$ and
$$N(I_d):=\{F\in C(I_d): F(x)=\sum_{k=1}^n f_k(v_k\cdot x), \mbox{ where } n\ge 1 \mbox{ and } f_1,\...
user128095
6
votes
1
answer
182
views
Can we approximate a vector field on the plane with non-vanishing vector fields in $W^{1,2}$?
Let $V$ be a compactly-supported vector field on $\mathbb{R}^2$, whose zeros inside some open neighbourhood of the closed unit disk $\mathbb{D}^2$ are isolated.
Does there exist a sequence of ...
- 6,741
1
vote
0
answers
145
views
An integral involving many exponential terms with quadratic exponents in the denominator
Given $k$ points $\{p_1,\cdots, p_k\}$ in $\mathbb{R}^n$ and positive constants $r_1, ..., r_k$ and another positive constant $\alpha>0$. Is there a way to compute/approximate the following (...
- 461
8
votes
1
answer
600
views
Can we perturb a map $\mathbb{R}^n \to \mathbb{R}^n$ to have distinct singular values?
$\newcommand{\SO}[1]{\text{SO}(#1)}$
$\newcommand{\dist}{\operatorname{dist}}$
Let $\mathbb{D}^n$ be the closed $n$-dimensional unit ball, and let $f:\mathbb{D}^n \to \mathbb{R}^n$ be smooth.
Set
$$...
- 6,741
2
votes
0
answers
1k
views
bounds on derivatives of mollifiers/mollified functions
Consider the standard mollifier
$$
\phi(x) = C\exp\left(-\frac{1}{1-x^2}\right), \quad -1<x<1.
$$
such that $\int\phi(x) = 1$.
Let $f(x) = |x|$ and consider the convolution $f\ast \phi$. I am ...
- 640
3
votes
1
answer
1k
views
Approximation of the indicator function of an interval by polynomials
Suppose $f:[-1, 1]\rightarrow\mathbb{R}$ is a polynomial. I am curious what the minimal degree of $f$ can be such that for $0<a<b<1$, $f$ satisfies the following two properties:
1) $\forall ...
- 31
8
votes
2
answers
397
views
Best constant approximation in $L^p(\Omega)$
For $\Omega$ a bounded open set of $\mathbf{R}^d$ and $f\in L^p(\Omega)$ the infimum
\begin{align*}
\inf_{C\in\mathbf{R}} \|f-C\|_p
\end{align*}
is reached (by compactness). For $1<p<\infty$ ...
- 3,425
1
vote
1
answer
119
views
Upper bound on Lp distance of functions before and after change of variables
Setup
I am trying to upper-bound the difference between two functions: one before the change of variables and the other after.
For example, let $r \in \mathbb{N} \cup \{\infty\}, 1 \leq p < \...
- 163
1
vote
1
answer
31
views
Family of funcitons that approximates uniform density on an ellipsoid
Given an nondegerate ellipsoid $E$ in $\mathbb{R}^d$, described as $E = \{x\in\mathbb{R}^d: (x-x_0)^TQ_0(x-x_0)\leq 1\}$ and let $\chi_E$ be the characteristic function supported on $E$. I am thinking ...
- 461
2
votes
0
answers
124
views
Error bounds for spline interpolation. Hall and Meyer's conjecture
Hall & Meyer, 1976, J. Approx. Theory, show for $f \in C^4[a,b]$ and a mesh $a = x_1, \ldots x_n = b$ with $h = \max x_{j+1} - x_j$, for $\pi f$ a cubic spline interpolant over the mesh for some ...
- 151
3
votes
0
answers
216
views
The $L_\infty$ norm of the derivative of the $L_2$ spline projector
A. Shadrin (Acta Mathematica, 2001) shows that the $L_\infty$ norm of the $L_2$ projector $P_\Delta$ onto the spline space $S_k(\Delta$) is bounded independently of the knot-sequence. I.e. for a ...
- 151
1
vote
0
answers
63
views
Approximation of measured-valued function by continuous functions
For each $x\in R^d$, let $\nu(x,dz)$ be a L\'evy measure, i.e.,
$$
\int_{R^d}(|z|^2\wedge1)\nu(x,dz)<\infty.
$$
Let $\mu$ be a probability measure on $R^d$ such that
$$
\int_{R^d}\int_{R^d}(|z|^2\...
- 411
-1
votes
1
answer
122
views
Approximation of function in general measure space
Let $\mu$ be a $\sigma$-finite measure on $R^n$ ($n\geq 1$) and $(E,d)$ be a complete metric space. For any measurable function $f: R^n\to E$ with
$$
\int_{R^n}d(f(x),f(x_0))\mu(dx)<\infty,\quad \...
- 411
0
votes
0
answers
44
views
Taylor approximation of $f(q) = \left(1 + q \dfrac{w_s}{w_0}\right)^{\alpha}$
I am trying to prove equations (3) given in this paper
http://users.cecs.anu.edu.au/~thush/publications/vtc_final.pdf.
The authors use taylor series to approximate function
$f(q) = \left(1 + q \...
12
votes
2
answers
1k
views
Low-degree polynomial approximation of the piecewise-linear function $x \mapsto \max(x, 0)$ on an interval $x \in [-R,R]$
For $R > 0$, consider the piecewise-linear function $\sigma_R: [-R,R] \rightarrow \mathbb R^+$, defined by $\sigma_R(x) := \max(x,0)$.
Question
Given $\epsilon> 0$, find a "low-degree" ...
- 6,853
2
votes
0
answers
35
views
Convergence rate of cardinal series (Whittaker-Shannon interpolant)
Given $f \in C^{k}_{0}[a, b]\cap L^{2}(\mathbb{R})$, what can we say about the convergence rate of the cardinal series
$$
s(t) = \sum_{j=0}^{n-1} f(a+jh) \mathrm{sinc}\left(\pi\left(\frac{t-a}{h} -j \...
- 221
2
votes
2
answers
263
views
Multiple series calculation
Let $n$ be a positive integer.
I would like to find a numerical evaluation of the convergent (!) series
$$
S_{n,s}=\sum_{k\in \mathbb Z^{n}}\frac{1}{(1+\vert k\vert^{2})^{s/2}},\quad s> n,
$$
where ...
- 16.2k
-1
votes
1
answer
396
views
Interpolation Inequality's Proof
Let $\Omega \subseteq R^{n}$ bounded domain. I need to prove that for $u\in H^{2}(\Omega)\cap H^{1}_{0}(\Omega)$:
\begin{equation}
\|\nabla u\|_{L^{2}(\Omega)}^{2}\leq \|u\|_{L^{2}(\Omega)}\|\Delta u\...
3
votes
0
answers
243
views
Interlacing sequences by polynomials?
Given $t=2^\ell$ where $\ell\in\mathbb N_{>0}$ and $M\in\mathbb Z$ and two sets of integers $\{a_1,\dots,a_t\}$ and $\{b_1,\dots,b_t\}$ with $0<a_1\leq \dots\leq a_t<M$ and $0<b_1\leq \...
- 13.9k
2
votes
0
answers
506
views
Closed form expression for $Tr\left[ (\mathbf{DW})^k \right]$
Given the $N \times N$ diagonal matrices $\mathbf{D}$ and $\mathbf{W}$ as defined below
$
\begin{split}
\mathbf{DW} &=
\left[
\begin{array}{cccc}
\beta_{1} & 0 & \cdots & 0 \\
...
6
votes
2
answers
555
views
An expansion from Ramanujan related to birthday problem
A friend designed a drinking game with a lucky wheel of 30 distinct icons. When playing, each one takes turn to spin the wheel, and write down the items until the first one who gets the item that has ...
- 409
3
votes
0
answers
182
views
Closed subvariety that is unique in its small analytic neighborhood
Let $Y$ be some smooth projective variety over $\mathbb C$ with $\dim Y \geq 2$. For a closed sub-variety $X \hookrightarrow Y$, consider the following property:
There is some small open neighborhood ...
- 6,622
10
votes
2
answers
671
views
Reference request: Extensions of Wiener's Tauberian Theorem
Wiener's Tauberian Theorem says that linear combinations of translations of a function $f$ are dense in $L^1(\mathbb{R})$ if and only if the zero set of the Fourier transform of $f$ is empty. This is ...
- 710
2
votes
0
answers
74
views
Can we approximate this matrix field with an invertible matrix field?
Let $\mathbb{D}^2=\{ x \in \mathbb{R}^2 \, | \, |x| \le 1\}$ be the closed unit disk, and set
$$\begin{equation*}
A(x,y)=\left(
\begin{array}{cc}
x & -y \\
y & x
\end{array} \right)
\end{...
- 6,741
8
votes
0
answers
178
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}...
- 1,284
2
votes
1
answer
110
views
Proving that $\lim_{j \to i} Z_{ij} = [\ln(\frac{\Delta s_i}{2})-1]\Delta s_i$
If I have the following integral equation $$\phi(\vec{x})=\frac{1}{\pi}\int [\phi\frac{\partial (\ln r)}{\partial n} -\ln(r) \frac{\partial \phi}{\partial n}] ds$$
An approximate solution of $\phi$ ...
- 111
4
votes
0
answers
87
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$ ...
- 6,741
9
votes
1
answer
499
views
Subspaces of $L^2(0,1)$ dense on every truncation $L^2(c,1)$
It may be better to move this to a separate question.
Let me call a linear subspace $V \subset L^2(0,1)$ to be tame if, for every linear subspace $W \subset V$, either $W$ is dense in $L^2(0,1)$, or ...
- 13.8k
10
votes
1
answer
595
views
Are the polynomials in $\{1/t\}$ dense in $L^2(0,1)$?
Added. My question in the title was solved (in the negative) by Nik Weaver (in the answer below) and Mateusz Kwaśnicki (in the comments). In both solutions, the reason is that the $L^2$ density fails ...
- 13.8k
1
vote
2
answers
483
views
Trotter-Kato approximation theorem for uniformly continuous approximants
Let
$E$ be a $\mathbb R$-Banach space
$(T_n(t))_{t\ge0}$ and $(T(t))_{t\ge0}$ be strongly continuous contraction semigroups on $E$ with generators $(\mathcal D(A_n),A_n)$ and $(\mathcal D(A),A)$, ...
- 167
1
vote
0
answers
154
views
Specific L1 piece-wise linear approximation of the convex function of one variable
Consider a convex function $f(x)$ of one variable $x$ on some interval $[a,b]$.
Question:
What is known about the L1 approximation of $f(x)$ by piecewise linear functions? How to construct ...
- 24.9k
2
votes
1
answer
437
views
Best approximation of a compactly supported density by a single Gaussian
Note: This is a follow-up question inspired by a previous (more difficult) question I asked on MathOverflow.
Let $f:\mathbb{R}\to\mathbb{R}$ be a (sufficiently regular, e.g. smooth) probability ...
- 710
1
vote
1
answer
211
views
Approximation of functions by tensor products
Given a function $f(x,y)\in L^p(R^d;L^\infty(B_R))$ with $1<p<\infty$, where $B_R:=\{y\in R^d: |y|\le R\}$, can we find a sequence of functions $f_n$ of the form $f_n(x,y)=\sum_{i=1}^ng_i(x)h_i(...
- 411