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.
580
questions
5
votes
2
answers
952
views
L1 distance from a trigonometric susbspace
How to check, whether the $L^{1}$ distance between a finite exponential sum $S_{F}(x)=\sum\limits_{n\in F} \exp(inx)$ and the $L^{1}$-closure of subspace $\mathrm{span}\left(\exp(inx): n\in \mathbb{Z}\...
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 \...
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 ...
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 ...
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 ...
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 $...
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 ...
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$ ...
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 ...
4
votes
3
answers
737
views
Does NP = "epsilon-P" (PTAS / BPP)?
Some NP-complete optimization problems, like the knapsack problem, have a solution reachable in polynomial time that is guaranteed to be within arbitrary ε of the optimum answer. (aka PTAS - ...
4
votes
2
answers
301
views
Can SO_n(R) be approximated arbitrarily well using a discrete subgroup?
Let $G := SO_n(R)$ be equipped with the Euclidean metric on vectors of length $n^2$. Is it true that for any $\epsilon >0$, there is a finite subgroup of $G$ which intersects every metric ball of ...
4
votes
4
answers
2k
views
When we use Bernstein polynomials in application
When it is preferable to use Bernstein polynomials to approximate a continuous function instead of using the only following preliminary Numerical Analysis methods: "Lagrange Polynomials", &...
4
votes
5
answers
2k
views
Relative error approximation by polynomials
For given continuous real functions $f$ and $g$ defined on $[-1,1]$, let's define
$$
D(f,g) = \sup_{x \in [-1,1]} \left|{\frac{f(x)-g(x)}{f(x)}}\right|
$$
(in this context, let's take $0/0$ to be $0$ ...
4
votes
2
answers
2k
views
Estimate on sum of squares of multinomial coefficients
I am interested in approximating the sum of the squares of the multinomial coefficients, i.e.
$a_\ell^p := \sum_{k_0+\ldots+k_p = \ell} (\frac{\ell!}{k_0! \ldots k_p!})^2$
or more general,
$a_\...
4
votes
2
answers
274
views
Approximating a fraction with a given denominator
Let $M$, $N$ be large natural numbers (say ~200 bits). Let $L$ be a smaller number, (say ~100 bits).
I want to approximate the fraction:
$$\frac{M}{N} \sim \frac{k}{L+r}$$
where $r$ is at most $L$. In ...
4
votes
1
answer
365
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 ...
4
votes
1
answer
168
views
automorphisms of a measurable space can be approximated by continuous measure preserving maps?
Suppose first that $D=[0,1]$ is equipped with the usual Lebesgue measure, and that $\varphi$ is a measure-preserving transformation $\varphi:D\to D$ that is bijective and whose inverse is also measure ...
4
votes
1
answer
401
views
Approximation of a $C^{\infty}_c$ function by tensor products
Suppose that $f \in C^{\infty}_c ( \mathbb{R}^2 )$, i.e. $f$ is a $C^{\infty}$ function with compact support defined on $\mathbb{R}^2$. The following link
Approximation of smooth compactly supported ...
4
votes
2
answers
135
views
Markov-type functions
I'd like to have some informations about Markov-type functions (or Cauchy-type):
\[ f(z)=\int_{\Gamma} \frac{\mathrm{d}\gamma(\xi)}{\xi-z}.\]
$\gamma$ is a positive measure with compact support $\...
4
votes
1
answer
193
views
Rate of convergence of Padé approximants
Let $f$ be an entire function of order $1$. Two questions:
1) Can one assert that the diagonal Padé approximants converge to $f$ (pointwise or uniformly over compacts of $\mathbb C$)?
2) if yes, can ...
4
votes
1
answer
160
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 ...
4
votes
1
answer
285
views
Literature request: Functional capacities
Are the results of the following book (in French) covered in English in a book or in an article, and if so, could you please provide a reference?
C. Dellacherie, Ensembles analytiques, Capacités, ...
4
votes
1
answer
1k
views
Variational proof for minimum curvature of cubic splines
Background: Given an increasing set of points $(x_i)_{i=0}^n \subset \mathbb [a,b]$, a cubic spline $S(x)\in C^2([a,b])$ is a piecewise cubic polynomial on each subinterval $(x_i, x_{i+1})$.
Given a ...
4
votes
1
answer
790
views
Reference for the exponential decay of Legendre coefficients
In Short: I look for a reference to the proof that the spectral coefficients in the Legendre (or Jacobi) expansion are of exponential decay rate.
Longer: If $p_n$ is the $n$-th Legendre polynomial, ...
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]$ ...
4
votes
1
answer
306
views
Schrodinger's equation over a randomized grid
I am interested in solutions to
$$
\frac{d}{dt} \Psi = -iH \Psi
$$
for $H$ hermitian and time independent. This boils down to evaluating
$$
\Psi(t) = e^{-iHt}\Psi_0
$$
at points of interest $t_n$. I ...
4
votes
1
answer
931
views
Interpolation by a function whose second derivative is bounded
I don't know if this is an easy question for specialists in the field. Consider
the following interpolation problem : let $\varepsilon >0$, $X$ be a finite
set of real numbers and $g$ be a real-...
4
votes
1
answer
575
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-...
4
votes
1
answer
390
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
votes
1
answer
407
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 ...
4
votes
2
answers
260
views
Approximated solutions of SEIR models
Numerical solutions of the SEIR equations (describing the spreading of an epidemic disease) – or variations thereof –
$\dot{S} = - N$
$\dot{E} = + N - E/\lambda$
$\dot{I} = + E/\lambda - I/\delta$
...
4
votes
1
answer
130
views
Construct a dense family in $W^{2,2}(\Omega)\cap W^{1,2}_0(\Omega)$ based on distance functions
Let $\Omega$ be a sufficiently regular domain, for example $\Omega=B(0,r)$, $r>0$, and $m(x)=\textrm{dist}(x,\partial \Omega)$ be the distance to boundary function.
Suppose $\mathcal{F}$ is a ...
4
votes
1
answer
674
views
Marsden's Identity and B-splines
Marsden's Identity states that for every $\tau$ in $\mathbb{R }$:
$$(\cdot -\tau)^{k-1}=\sum_j\Psi_{j,k}(\tau)B_{j,k,t} \, ,$$
with $\Psi_{j,k}=(t_j-\tau)\times...\times(t_{j+k-1}-\tau)$.
Following ...
4
votes
1
answer
148
views
Find $p$ s.t. there is a sequence of nodes in $[0,1]$ s.t. sequence of interpolating polynomials of every continuous function converges in $p$-norm
Let $[a,b]$ be an interval in real line . Given any function $f:[a,b]\to \mathbb R$ and set $A \subseteq [a,b]$ of size $n+1$, there exists a unique polynomial $p_{f,A,n}(x)$ of degree $n$ such that $...
4
votes
1
answer
461
views
Is the kernel of a Fredholm operator stable under perturbation?
This is a follow-up of this question.
In a nutshell: Does the kernel of a bounded operator change "nicely" with the operator?
Let $(X,\| \cdot \|)$ be an infinite-dimensional normed vector space.
...
4
votes
1
answer
274
views
Constructive approximation of Hölder functions using kernel functions
Suppose I have a function $f \in \mathcal C^{\alpha, L}([0,1])$, where
$\mathcal C^{\alpha, L}([0,1])$ is the space of $\alpha$-smooth Hölder
functions with norm $L$. I am interested in efficiently ...
4
votes
1
answer
455
views
Polynomial interpolants in quadrature points and L2 convergence spectral rate
We recall that the Lagrange Interpolation Polynomial $p_n(x)$ of a function $f\in C^n(\Omega )$ for some $\Omega \subseteq \mathbb{R}$ and $n\in \mathbb{N}$, has a pointwise error term of the form $$|...
4
votes
1
answer
259
views
Approximation of $e^x$ by rational functions
Define a sequence of polynomials: $p_0(x)=1$, $p_1(x)=2+x$, and, for $n\ge 1$, $p_{n+1}=(4n+2)p_n(x)+x^2p_{n-1}(x)$ so that the first few are $1, x+2, x^2+6x+12, x^2+12x^2+60x+120$.
Is there an ...
4
votes
1
answer
903
views
Lebesgue constant as condition number of polynomial interpolation
Let $T = \{ x_0,\ldots,x_n \}$ be a set of $n+1$ different points in the real interval $[a,b]$. Let $X_T$ be the associated interpolation operator on $C[a,b]$: it takes a function $f \in C[a,b]$ into ...
4
votes
1
answer
260
views
Minimizing the L1 norm of odd-term trigonometric polynomial
I want to minimize the $L_1$ norm of a finite odd-term trigonometric polynomial:
$$\min_{a_k} \int_{0}^{1} |\sin(2\pi t)+\sum_{k \in \{3,5,7,...,2K-1\}}a_k\sin(2\pi kt)| \, \mathrm d t$$
Obviously, ...
4
votes
1
answer
228
views
Expectation over Pareto Sums
Given $K$ iid random variables $x_i$ with uniform distribution on $(0,1]$
and a constant $\alpha > 0$, the random variable $x_i^{-\alpha/2}$ is Pareto-distributed with scale parameter $1$ and ...
4
votes
1
answer
203
views
Simultaneous approximation of arbitrary functions in Hölder space and in $L^2(\mu)$ by a smooth function and its derivative
Let $\mu$ be a probability measure on the circle $S^1=\mathbb{R}/\mathbb{Z}$ which is singular with respect to the Lebesgue measure $\lambda$. Consider the functions spaces $L^2(\mu)$ on the one hand, ...
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)}^...
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 ...
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 ...
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{...
4
votes
0
answers
153
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}{ \...
4
votes
0
answers
477
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 $\...
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$ ...
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 ...