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
2
votes
0
answers
148
views
"Almost rational" irrational
This is a follow-up to an older question.
Let $r\in \mathbb{R}\setminus\mathbb{Q}$, let $\mathbb{N}$ denote the set of non-negative integers and let $\mathbb{N}_+=\mathbb{N}\setminus\{0\}$. For $n\in\...
- 48.9k
8
votes
1
answer
273
views
Smooth approximation of Hölder functions "from below"
We assume that we have a $\alpha$-Hölder continuous function $f$ on an interval $[0,1].$
I am wondering if there exists an explicit construction of a sequence $f_{n} \in C_c^{\infty}(\mathbb R)$ such ...
8
votes
3
answers
545
views
Approximation of pseudogeometric progression
Let $f_n(x)=1+x+x^{\sqrt{2}}+x^{\sqrt{3}}+x^{\sqrt{4}}+\cdots+x^{\sqrt{n}}$ be a sequence of functions on the interval $[0, 1]$. Is there a good closed form approximation for such a function ( ...
- 728
5
votes
2
answers
708
views
Approximation of Hölder continuous functions "from below"
We assume that we have a $\alpha$-Hölder continuous function $f$ on an interval $[0,1]$ with $f(0)=0$.
I am wondering if there exists an explicit construction of a sequence $f_{n} \in C_c^{\infty}(\...
0
votes
1
answer
205
views
How to prove approximation for fresnel integral converges
I was looking at the fresnel integral $S(x)=\int^x_0\sin(s^2)ds$. From reading I learned that this integral approaches $\frac{1}{2} \sqrt{\frac{\pi}{2}}$ as $x \rightarrow \infty$. Through messing ...
1
vote
0
answers
75
views
Carleman approximation for functions from $\mathbb R$ to (closed convex subset of) a Lie algebra
I am looking for an approximation result dealing with continuous functions of a real parameter with values in (some subset of) the unitary algebra. However, I wouldn't be surprised if the following ...
4
votes
1
answer
643
views
Explicit and fast error bounds for approximating continuous functions
Main Question
This question is about finding explicit, calculable, and fast error bounds (no hidden constants) when approximating continuous functions with polynomials or simpler functions to a user-...
- 697
2
votes
1
answer
76
views
Zeros in $[0,1]$ of functions $f \in \mathrm{span} \{ p(x - \lambda_k)e^{\lambda_k x} : k=1,\dots, n \}$
Let $n \in \mathbb N$, let $p:\mathbb R \to \mathbb R$ be a real polynomial, and let $\lambda_1< \lambda_2 <\dots < \lambda_n$. Now let
$$
f \in \mathrm{span} \left \{ p(x - \lambda_k)e^{\...
- 190
2
votes
1
answer
216
views
Measuring how "close" $\alpha\in[0,1]\setminus\mathbb{Q}$ is to being rational
Let $\mathbb{N}_+$ denote the set of positive integers and let $\mathbb{N}_0 = \mathbb{N}_+\cup\{0\}$. Fix $\alpha\in[0,1]\setminus \mathbb{Q}$. For $n\in\mathbb{N}_+$ we let the approximation radius ...
- 48.9k
1
vote
2
answers
107
views
Measurability of Brjuno numbers
A positive irrational number $\alpha\in{\mathbb R}\setminus {\mathbb Q}$ is said to be a Brjuno number if $$\sum_{i=1}^\infty\frac{\log q_{i+1}}{q_i} < \infty$$ where $q_i>0$ is the denominator ...
- 48.9k
6
votes
2
answers
541
views
Optimal polynomial approximation of rational function $\frac{1}{1-x}$
I've been working on the following polynomial approximation problem. I want to find the optimal Chebyshev approximation of the rational function $\frac{1}{1-x}$ on the real interval $x\in[-\rho, \rho]$...
- 63
8
votes
1
answer
722
views
A robust version of "a holomorphic function is determined by its modulus"
It is well known that if $f(z)$ and $g(z)$ are both holomorphic on a (path-)connected open set $C$ and $\lvert f(z)\rvert=\lvert g(z)\rvert$ on $C$ then $f(z)=cg(z)$ on $C$ for some constant $c$. Do ...
- 1,551
1
vote
0
answers
216
views
Is there an approximate formula for this summation function?
Consider the function $$\sum_{n=1}^\infty \frac{\cos(nx)}{n^r},$$ where $r\in\mathbb{N}$. Is there any approximate formula (closed form possibly avoiding this type of summation) for this function? I ...
- 59
5
votes
3
answers
666
views
The relative error of approximating a binomial
Are there any good approximations for a binomial CDF that work well in terms of the relative error, as opposed to absolute? For the usual normal approximation, the absolute error is very well-studied ...
- 4,049
4
votes
0
answers
99
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)}^...
- 380
1
vote
0
answers
56
views
Error bounds for Sobolev space norm approximation on a finite grid
Suppose that $f : [0, 1] \to \mathbb{R}$ is an element of the order-$k$ Sobolev space,
\begin{multline}
f^{(k - 1)}~\text{is absolutely continuous},\quad \|f\|_{W^k}^2 := \int_0^1 f^{(k)}(x)^2 \, dx &...
- 380
1
vote
1
answer
260
views
Finding the set of best approximation
Given $X$=$l^1$ and its dual space $X^*=l^\infty$. Now take $f=(1, 1/2, 2/3, 3/4,...) \in X^*$. Then clearly $\|f\|_\infty = 1$. I have found that $H=\ker f$ is a proximinal hyperplane in $X$.
Note: A ...
- 85
2
votes
1
answer
276
views
Construction of the Lipschitz function with a given Lipschitz constant, given two values and with small Lipschitz norm
Let the function $f\colon [a,b] \to\mathbb{C}$ be Lipschitz and let $|f(a)| \geq c,$ $|f(b)| = c$ and $\varepsilon > 0.$
It is easy to see that if $\|f\|_{\infty}< \frac{\varepsilon}{2} =: \...
- 97
1
vote
1
answer
136
views
Construction of the Lipschitz function with a given Lipschitz constant and given two values
Let the function $f\colon [a,b] \to\mathbb{C}$ be Lipschitz and let $|f(a)| \geq c$ and $|f(b)| = c$. Is there a Lipschitz function $g$ such that $|g| \geq c,$ $g(a)=f(a),$ $ g(b)=f(b)$ and Lipschitz ...
- 97
8
votes
1
answer
723
views
Bounding the discrete $l^p$ norm by the continuous $L^p$ norm for trigonometric polynomials
Let $ X_N = \text{span} \{\cos(2\pi lx): l=0, \cdots, N-1 \} $ with $ x \in [0, 1] $ and $ Y_N = \{v =(v_0, \cdots, v_{N-1}): v_j \in \mathbb{C}\} = \mathbb{C}^N $. Then $ X_N $ is the space of ...
- 105
2
votes
0
answers
111
views
Generalization of the min-entropy that looks at the top $n$ probabilities
The min-entropy of a random variable $X$ can often be much easier to compute than the Shannon entropy. This is because the min-entropy is simply a function of the most probable value, and sometimes, ...
- 4,907
1
vote
1
answer
185
views
Approximating a strictly increasing non-negative function on a non-negative domain by polynomials with non-negative coefficients
Let $f:[0,2]\rightarrow [0,\infty)$ be a strictly increasing smooth function. The Weierstrass approximation theorem says that we can uniformly approximate $f$ by polynomials. But my concern is
...
- 11
1
vote
1
answer
54
views
Can the second-order difference control the first-order difference for nowhere differentiable functions?
Suppose that $f$ is a continuous, nonconstant function on $[0,1]$. Fix some $0<a<1$. Is it possible to establish the following inequality
$$ |f(x+h)-f(x)| \leq C \left[ |h|^a + |2f(x)-f(x+h)-f(x-...
- 419
9
votes
2
answers
313
views
Average as a constant approximation in $L^p$
Let $I=[0,1]$. For $p\in[1,\infty]$ define $C_p$ as the best constant such that for all $f\in L^p(I)$
$$
\left\|f-\int_If\,\right\|_{L^p(I)}\leq C_p\inf_{c\in\mathbb{R}}\left\|f-c\,\right\|_{L^p(I)}.
$...
- 493
3
votes
0
answers
183
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 ...
- 5,405
1
vote
0
answers
195
views
Uniform norm bounds for linear approximation of 1-Lipschitz functions
This problem seems like it should be quite easy/standard, but I've not found a solution written down anywhere.
Consider the set of 1-Lipschitz functions on the $[0,d]$ interval. Define the linear ...
- 181
0
votes
1
answer
104
views
Show that $\frac{1}{n} \sum_{i=1}^n a_i \operatorname{erf} \left( \frac{b_i-x}{\sqrt{2}} \right) \to x$ for some sequence $\{a_n\}$ and $\{b_n\}$
Consider the following function
\begin{align}
f_n(x)=\frac{1}{n} \sum_{i=1}^n a_i \operatorname{erf} \left( \frac{b_i-x}{\sqrt{2}} \right)
\end{align}
where $\operatorname{erf} $ is the error ...
- 671
10
votes
1
answer
283
views
A function is of bounded variation if and only if the errors of its best approximation by trigonometric polynomials satisfy $\sum\frac{e_n}n<\infty$?
Let $\mathcal P_n$ be the set of trigonometric polynomials of degree less than or equal to $n$ and let $\lVert\cdot\rVert_\infty$ be the supremum norm. The error of the best approximation of $f$ of ...
- 288
2
votes
0
answers
72
views
Under what conditions is the least-squares approximation bounded with the same Lipschitz gradient constants?
Let $f(x):\mathbb{R}^K\Longrightarrow \mathbb{R}^L$ denote a multivariate continuously differentiable function. All the partial derivatives of $f$ (all its Jacobian elements) are bounded from above ...
- 21
3
votes
1
answer
162
views
Approximation in Bochner spaces
Is there any result like the Bramble-Hilbert lemma for Bochner spaces?
More specifically: let $H$ be a (e.g.) Hilbert space, $I\subset \mathbb R$ a bounded interval, and $L \in \mathcal L(H^k(I;H), Y)...
- 235
4
votes
1
answer
500
views
Smooth approximation of the $\max\{0,x\}$ function with controlled derivatives
Motivation/Hand-Wavy Question:
In this post, it was asked what the best local approximation of $f(x):=\max\{0,x\}$ is by a polynomial of a given degree; with the answer provided by Chebyshev's ...
- 5,405
3
votes
0
answers
147
views
Chebyshev-like polynomials [closed]
In some approximation problems I'm working on, the errors turned out to be polynomials of various degrees whose graphs on the interval $[-1,1]$ look like this:
As you can see, these things look a bit ...
- 649
1
vote
0
answers
78
views
Does a matrix product have an upper bound on the largest coefficient?
Let $A$ and $B$ be two $n\times n$ random matrices. Matrix $A$ has coefficients taken from a normal distribution $ \mathcal{N}(\mu_A,\sigma_A)$, and matrix $B$ has coefficients taken from $ \mathcal{N}...
- 105
0
votes
0
answers
54
views
Numerically expanding a function in a rational-power "basis"
I have some scientific code which interfaces with a library which accepts real functions specified as any number of additive terms with exponential powers. For instance, it is capable of accepting ...
- 173
4
votes
0
answers
582
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 ...
- 697
0
votes
0
answers
105
views
Wavelet decomposition of $C^{k}$-functions on smooth manifolds
Background (compactly supported wavelet decomposition of $\mathbb{R}^n$):
Fix compactly supported “mother and father wavelets” $\phi,\psi^{\epsilon}:\mathbb{R}^n\rightarrow \mathbb{R}$ where $\epsilon$...
- 5,405
1
vote
0
answers
59
views
Functional approximation with derivatives
I am trying to solve a functional approximation problem.
Consider a set of measurements of a d-dimensional state $\mathrm x \in \mathbb{R}^d$, together with velocities $\dot{\mathrm x}$ and ...
3
votes
0
answers
368
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 ...
- 697
5
votes
0
answers
109
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 ...
- 109k
0
votes
0
answers
50
views
Can we talk about approximation when the decision problem for solution existence is NP-Hard
I am wishing to design an approximation algorithm for an optimization problem where the existence of solution for corresponding decision problem is not guaranteed. Is it wise to find an approximation ...
1
vote
1
answer
201
views
Approximating a smooth function under some restrictions
Let $C^{m,\alpha}_M([0,1])$ be a Holder ball consisting of real-valued functions $g$ on $[0,1]$ such that
$$ \|g\|_{C^{m,\alpha}} := \max_{0\leq j \leq m } \sup_{x\in [0,1]} |g^{(j)}(x)| + \sup_{x,y\...
- 93
1
vote
0
answers
48
views
Optimal regularity of polynomial interpolators
Definitions
We define the "complexity" of any polynomial function $p:\mathbb{R}^n\rightarrow \mathbb{R}^m$ as $m\binom{n+\deg(p)}{n}$ (i.e the dimension of $\oplus_{i=1}^m\,\mathbb{R}[X_1,\...
- 5,405
2
votes
0
answers
93
views
Approximating a probability density with a point set
Let $f$ be a "nice" probability density on $\mathbb{R}^2$, let $p=1/k$ for some fixed positive integer $k$, and let $\epsilon>0$. Are there any known statements of the following form?
&...
- 4,049
2
votes
0
answers
92
views
Is there a continuous function with finitely many local extrema which is arbitrarily hard to approximate by (trigonometric) polynomials?
("Hard" in the same way that $\varphi=\frac{1+\sqrt 5}2$ is "hard to approximate by rationals".)
I'll state the problem here and give the motivation below. Is there a continuous ...
- 288
17
votes
2
answers
2k
views
Explicit and fast error bounds for polynomial approximation
Main Question
This question is about finding explicit, calculable, and fast error bounds when approximating continuous functions with polynomials to a user-specified error tolerance.
EDIT (Apr. 23): ...
- 697
1
vote
1
answer
61
views
Weak lower semicontinuity of a sequence of Riemann sums
Let us have a sequence of functions $\{f^K\}_{K \in \mathbb{N}} \in C([0,1],\mathbb{R})$ which is uniformly bounded in $L^2((0,1))$. We observe a sequence of Riemann sums
$$R^K=\frac{1}{K} \sum_{k=0}^{...
- 319
2
votes
1
answer
259
views
Are Chebyshev polynomials a Schauder basis of $\mathrm{Lip}[-1,1]$?
It is known that every Lipschitz function $f \colon [-1,1] \to \mathbb R$ can be expressed as a series in the Chebyshev polynomials $$f = \sum_{n = 0}^\infty a_n T_n $$ which is absolutely convergent ...
- 319
1
vote
1
answer
223
views
Bound error in approximating $E_x [H(f(x))]$ with random $(1/n) \sum_{i=1}^n \Phi(f(x_i)/h)$ where $H$ is Heaviside function and $\Phi$ is normal CDF
Let $f:\mathbb R^d \to \mathbb R$ be a "sufficiently smooth" function. For simplicity, we may consider $f$ to be an affine function, i.e $f(x) \equiv b-x^\top w$, for some $(w,b) \in \mathbb ...
- 6,853
6
votes
1
answer
346
views
Best approximation of L1 function by Lipschitz function
Fix constant $L,C>0$ and $k\geq 1$ and let $f\in W^{1,k}(\mathbb{R}^d,\mathbb{R}^n)$ with $\|f\|_{W^{1,k}}\leq C$.
Is there a known estimate on the distance
$$
\|f - \operatorname{Lip}_L(\mathbb{R}^...
- 5,405
3
votes
1
answer
125
views
Relation between the local maxima and the local minima for approximating the generalized Laguerre polynomial
I have already asked my question in the link below:
Minima approximation for Laguerre polynomials
I have suggested to anyone to give me the approximations of the minima for the Laguerre polynomial, ...
