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.
69
questions
17
votes
4
answers
975
views
Finite interpolation by a nondecreasing polynomial
Let $x_1 < x_2 < \ldots < x_n$ and $y_1 < y_2 < \ldots < y_n$ be two sequences
of $n$ real numbers. It is well known that there are polynomials that "interpolate"
in that $f(x_i)...
8
votes
1
answer
2k
views
Multivariate polynomial approximation of smooth functions
Let $f$ be a function defined on $[-1,1]^d$. Assume that all partial derivatives of $f$ up to order $r$ are continuous; and the $\infty$-norm of these partial derivatives are uniformly upper bounded ...
8
votes
1
answer
596
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
$$...
5
votes
2
answers
231
views
Can we stay invertible while approximating linear maps in Sobolev spaces?
Let $\Omega \subseteq \mathbb{R}^n$ be an open bounded domain with a smooth boundary. Fix $1<p<n$.
Let $A \in W^{1,p}(\Omega;\text{End}(\mathbb{R}^n)) \cap C(\Omega;\text{End}(\mathbb{R}^n))$ ...
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_\...
28
votes
7
answers
8k
views
Solving NP problems in (usually) Polynomial time?
Just because a problem is NP-complete doesn't mean it can't be usually solved quickly.
The best example of this is probably the traveling salesman problem, for which extraordinarily large instances ...
23
votes
1
answer
1k
views
Hilbert's Theorem on $L_2$ norm of polynomials in $\mathbb{Z}[X]$ - Explicit construction and a converse?
Consider the set of polynomials with real coefficients as a vector space with the following inner-product: $\langle f, g \rangle = \int_{a}^{b} f(x)g(x) dx$.
Hilbert showed, in a paper from 1894, ...
17
votes
4
answers
3k
views
Using Quotient of Prime Numbers to Approximation Reals
We know a positive rational number can be uniquely written as $m/n$ where $m$ and $n$ are coprime positive integers. Particularly, we can pick out those numbers with $m$ and $n$ both prime.
Question ...
11
votes
1
answer
1k
views
Stone-Weierstrass analogue for $L^p$
Let $A$ be a complex algebra of bounded measurable functions on the measure space $(X,\mu)$ (case of $[0,1]$ with Lebesgue measure is enough for me) closed under conjugation. Assume that $A$ separates ...
6
votes
1
answer
172
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
votes
1
answer
697
views
Find the maximum of $|a_{p}|$, if $a_0+a_1x+\dots+a_nx^n:[-1,1]\mapsto [-1,1]$
Let $n$ be a given positive integer, and let $f(x)=\displaystyle\sum_{k=0}^{n}a_{k}x^k$, where $a_{i}\in \mathbb{R}$, $0 \le i \le n$. If
$$|f(x)|\le 1,\qquad \text{for } ~|x|\le 1,$$
what is the ...
3
votes
2
answers
2k
views
Is there an example where the error of Gauss-Laguerre quadrature does not vanish?
The $n$th Gauss-Laguerre quadrature aims to approximate integral $$\int_{\mathbb{R}_+} f(x) \exp(-x)$$ by the sum
$$\sum_{i=1}^n f(x_i) w_i$$
where $x_1,...,x_n$ are the roots of the $n$th Laguerre ...
2
votes
2
answers
2k
views
A bounded polynomial having bounded coefficients: several variables
Consider the multivariate case for the question "Approximation theory reference for a bounded polynomial having bounded coefficients" (Approximation theory reference for a bounded polynomial having ...
0
votes
1
answer
87
views
Approximating a sequence of tempered distributions "uniformly" by Schwartz functions
This question has been motivated by the post making sense of distributions on the diagonal.
Let $T$ be a tempered distribution on $\mathbb{R}^2$ and $\eta$ be a given mollifier on $\mathbb{R}$. For $f ...
13
votes
5
answers
3k
views
Application of polynomials with non-negative coefficients
Question 1: Are there any deeper applications (in any field of mathematics) of polynomials (with possibly more than one variable) over the real numbers whose coefficients are non-negative? So far I ...
22
votes
2
answers
643
views
Does every positive continuous function have a non-negative interpolating polynomial of every degree?
Let $f:[a,b] \to (0,\infty)$ be a continuous function. Then is it necessarily true that for every $n\ge 1$, we can find $n+1$ distinct points $\{x_0,x_1,...,x_n\}$ in $[a,b]$ such that the ...
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): ...
15
votes
5
answers
13k
views
A differentiable approximation to the minimum function
Suppose we have a function $f : \mathbb{R}^N \rightarrow \mathbb{R}$ which, given a vector, returns the value of its smallest element. How can I approximate $f$ with a differentiable function(s)?
12
votes
1
answer
1k
views
Accumulation of algebraic subvarieties: Near one subvariety there are many others (?), 2
This is a sequel to the question Accumulation of algebraic subvarieties: Near one subvariety there are many others (?) .
Let $Y$ be some projective variety, over $\mathbb{C}$. Let $X\subset Y$ be ...
11
votes
2
answers
992
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" ...
11
votes
1
answer
1k
views
What are some of the surprising results of finite sample statistical estimation?
I'm trying to familiarize myself with the latest results in finite sample statistics. It seems to me that these results can be classified into two categories:
Unsurprising results confirm that the ...
10
votes
2
answers
522
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 ...
10
votes
1
answer
499
views
Density of smooth function in Hilbert spaces
I am looking for a simple reference to the following fact:
If $f:\Omega\to\mathbb{R}$ is continuous, where $\Omega\subset H$ is an open subset of a separable Hilbert space $H$, then for any $\...
10
votes
1
answer
863
views
The closures in $C^0(\mathbb{R}, \mathbb{R})$ of the set of integer valued polynomials, resp, of polynomials with integer coefficients
This is a follow up of an interesting recent question on the topic. The answer given there by fedia shows that the matter is rich and complicated, and I can't resist to submit here a further question.
...
10
votes
4
answers
10k
views
Approximation with continuous functions
Is it true that for every function $\mathbb{R} \to \mathbb{R}$ there exists a sequence of continuous functions $f_n(x): \mathbb{R} \to \mathbb{R}$ such that for any $x \in \mathbb{R}$ $f_n(x)$ ...
10
votes
1
answer
537
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 ...
10
votes
1
answer
776
views
Approximation of a compactly supported function by Gaussians
Let $f:\mathbb{R}\to\mathbb{R}$ be a smooth function whose support is a closed interval, e.g. $\text{supp}(f)=[a,b]$. Then $f$ can be approximated (e.g. in $L^2$) by a linear combination of Gaussian ...
9
votes
1
answer
473
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 ...
9
votes
3
answers
649
views
Degree necessary of a polynomial?
Given $-1<a<b<0$, I want to find a polynomial $f(x)\in\Bbb R[x]$ such that $f(x)\in[a,b]$ at every $x\in[b^2,a^2]$ and $f(0)=0$. What is minimum degree that is needed and maximum degree that ...
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$...
8
votes
2
answers
430
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(\...
7
votes
3
answers
2k
views
Approximation theory reference for a bounded polynomial having bounded coefficients
Let $P(x)$ be a real polynomial of degree at most $d$. Assume $|P(x)| \leq 1$ for $|x| \leq 1$. I would like a bound saying that each coefficient of $P(x)$ is at most $C^d$ in magnitude, for some ...
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 ...
7
votes
2
answers
606
views
Given any sequence of interpolating nodes, can we find a continuous function $f$ whose interpolating polynomials doesn't converge to $f$ point-wise
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 $...
7
votes
2
answers
2k
views
Variant of Fermat's last theorem
By Fermat's last theorem, the equation $u^3+v^3=w^3$ has no solutions
in positive integers $u,v,w$. Now consider the following variant : call $\rho(x)$
the distance between $x$ and the nearest integer,...
6
votes
3
answers
2k
views
Multivariate Bernstein polynomials for approximation of derivatives.
If I have a $C^\infty$ function $f: [0,1]^n \to \mathbb{R}$ then its Bernstein polynomials
$$
B_m(x) = \sum_{k_1,\dots,k_n=0}^m f\left(\frac{k_1}{m}, \dots, \frac{k_m}{m}\right)
\prod_{i=1}^n \binom{m}...
6
votes
1
answer
274
views
Time of peak of an SIR epidemic
I've learned some classical results on the peak and the attack rate of an idealized epidemic which evolves according to a SIR model
$\dot{s} = -\beta\cdot i \cdot s$
$\dot{i} = +\beta\cdot i \cdot s -...
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,...
6
votes
2
answers
2k
views
Polynomial approximation in L^p norms
Hello,
I am very new to the field of approximation theory, and since
an extended search on the Internet did not provide answers for
two rather basic questions, I decided to ask them here.
1) From ...
6
votes
1
answer
296
views
Regularization by mean curvature flow
I have a $C^{1,\alpha}$ surface defined as the graph of some function $\varphi : B \to \Bbb{R}_+$ ($B$ is a ball). This surface has positive and bounded mean curvature in the weak sense (since the ...
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
1
answer
374
views
Asymptotics of Fresnel integrals
It is known that
\begin{equation*}
I(p) = \sqrt { \frac {4 \mathrm{i} p} {\pi}}\int \limits _{-\infty} ^{\infty} \mathrm{e}^{- \mathrm{i} p x^2} \varphi (x) \mathrm{d}x
\end{equation*}
is a bounded ...
5
votes
1
answer
2k
views
Are piecewise linear functions dense in $W^{1,\infty}$?
Are piecewise linear functions dense in $W^{1,\infty}$ ?
5
votes
2
answers
3k
views
approximating the $|x|$ function
I'm familiar with Newman's rational approximation of the absolute value function via rational functions. Are there other explicit functions that approximate $|x|$ with exponential error? I was under ...
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
1
answer
773
views
Is there a continuous function $f$ satisfying the following Zygmund condition but not differentiable.
Suppose that a continuous function $f$ on the line and satisfies
$$
|f(x+2h)−2f(x+h)+f(x)|\leq const \frac{|h|}{(\log\frac{1}{|h|})^{\beta}}\,\,\,\,\,\,\text{where}\,\,\,\, \beta \in(0, 1]
$$
...
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
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
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
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 ...