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.
583
questions
1
vote
1
answer
216
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 ...
- 75
2
votes
1
answer
246
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
124
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
694
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
95
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,525
1
vote
1
answer
148
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
287
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)}.
$...
- 458
3
votes
0
answers
163
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 ...
- 4,969
1
vote
0
answers
118
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
102
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 ...
- 631
10
votes
1
answer
269
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
68
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
154
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)...
- 225
4
votes
1
answer
403
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 ...
- 4,969
3
votes
0
answers
146
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
75
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}...
- 95
0
votes
0
answers
47
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
546
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 ...
- 637
0
votes
0
answers
99
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$...
- 4,969
1
vote
0
answers
56
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
356
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 ...
- 637
5
votes
0
answers
105
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 ...
- 103k
0
votes
0
answers
45
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
171
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,\...
- 4,969
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?
&...
- 3,929
2
votes
0
answers
89
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
1k
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): ...
- 637
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
223
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
218
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,726
6
votes
1
answer
307
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}^...
- 4,969
2
votes
1
answer
108
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, ...
2
votes
0
answers
39
views
Find weak approximation by smooth unit vector fields for Sobolev fields on manifold
I am considering the Sobolev space of unit tangent vector fields on a compact manifold:
$Γ_{W^{1,2}}(M, UTM)$.
I would like to approximate those weakly with smooth vector fields ($Γ_{C^∞}(M, UTM)$).
...
- 121
4
votes
1
answer
432
views
Series expansion for gaussian-like function
I need a series expansion to describe a general gaussian-like (bell shaped) function. I couldn't find a rigorous definition of "bell shaped" online but in essence the function should have ...
- 43
1
vote
1
answer
125
views
Distribution of quadratic polynomials mod $n$ and $n^2$
Suppose $n$ is odd, then both equations $x^2 = D \; mod \;n$ and $x^2 = D \; mod \;n^2$ have the same number of solutions for fixed $D$ coprime to $n$. What can be said about the relationship between ...
- 577
0
votes
1
answer
627
views
Fast decaying Fourier coefficients for indicator function
Let $0 \leq a < b \leq 1$. I wanted to compute the Fourier series expansion of the indicator function $f = \chi_{[a, b]}$ of the interval $[a, b]$, as
$$
f(x) = \sum_{k\geq 0}a_k e(kx).
$$ My ...
- 577
0
votes
2
answers
692
views
Approximating exp(x) with a piecewise-linear function accurately
I am looking for the best way to approximate $\exp(x)$ on a finite domain $[0,M]$ with a piecewise-linear function. My initial approach is to take $K$ evenly-spaced segments from $0$ to $M$. For each ...
- 13
7
votes
3
answers
908
views
How to numerically compute $x \ln x$ and related functions near $0$?
I was recently trying to find a numerical solution to a thermodynamics problem and the expression $x\ln x$ appeared in one of the computations. I did not have to find its value very near $0$, so the ...
- 3,680
0
votes
0
answers
103
views
Computing $\int^{4b}_0 {e^{-tx}\biggl(\frac{\sqrt{4bx-x^2}}{(2b-2c)^2+4cx}\biggr) dx}$
I am a PhD student working on complex analysis. After integrating over a keyhole contour to obtain the inverse of a particular Laplace transform, I ended up with the following integral:
$$\frac{1}{\pi}...
- 9
2
votes
0
answers
117
views
Almost periodic functions in weak mixing extension
In Theorem 3.4.6 of the 'Lecture notes on ergodic theory' by Jesse Peterson, it is shown that in a weak mixing extension, every almost periodic function is trivial. I have a doubt in the proof of this ...
- 45
2
votes
0
answers
192
views
Almost periodicity and approximation in tracial von Neumann algebra
Let $N$ be a von Neumann algebra with a faithful normal tracial state $\tau$. For a countable group $G$, let $\sigma: G\rightarrow \text{Aut}(N)$ be a $G$- action on $N$ which preserves the tracial ...
- 73
3
votes
1
answer
565
views
Functions dense in $L^1[0,1]$ but not in $L^2[0,1]$
Is there a family of continuous functions $(f_n)_{n \in \mathbb{N}}$ on $[0,1]$ whose span is dense in $L^1[0,1]$ for the $L^1$-norm, but not dense in $L^2[0,1]$ for the $L^2$-norm?
Some preliminary ...
- 188
2
votes
0
answers
165
views
Density of $\mathrm{span} \{ f(\cdot - n) : n \in \Bbb Z \}$ in $C(\mathbb R)$
I recently came across a survey paper by Allan Pinkus. This paper contains the following result:
Suppose that $g \in L^1(\mathbb R)$ has support in an interval of length at most $2\pi$. If $f=\hat g$ ...
- 367
5
votes
1
answer
194
views
Smooth, non-analytic functions of non-normal matrices
My apologies if this isn't a well-enough-posed question, I think I'm partly unsure of what exact question to even ask.
There are many different ways in which we can take a function of a matrix.
We ...
- 844
3
votes
1
answer
276
views
Polynomial and rational approximation of continuous functions in $\mathbb{C}$
I am wondering what the state of the art is for polynomial and rational approximations to continuous/holomorphic functions in $\mathbb{C}$. The particular domains of interest are the closed unit ball $...
- 465
4
votes
1
answer
65
views
Distance to finite degree polynomials for BV functions
A result of Jackson establishes for lipschitz functions $f\in\text{W}^{1,\infty}(0,1)$ the bound $$\inf_{p\in\mathbf{R}_n[x]} \|f-p\|_\infty\lesssim \frac{1}{n}\|f'\|_\infty,$$
where $\mathbf{R}_n[x]$ ...
- 2,710
3
votes
1
answer
82
views
Weierstrass-type approximation of a system of the form $\{ x \mapsto f(x)^{p_n} : n \in \mathbb N\}$
Let $(p_n)_{n \in \mathbb N} \subset (0,\infty)$ be a sequence of distinct positive numbers such that their series of reciprocals diverges. By the theorem of Müntz-Szasz the closure of the span of the ...
- 163
1
vote
0
answers
71
views
Error estimates for orthogonal polynomial approximation
tl;dr: Are there explicit bounds for the approximation error by orthogonal polynomials?
There are various ways to formulate this question more precisely, so want I emphasize up front that this is a ...
- 19