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.

Filter by
Sorted by
Tagged with
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)...
Ewan Delanoy's user avatar
  • 3,565
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 ...
Liwei Wang's user avatar
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 $$...
Asaf Shachar's user avatar
  • 6,611
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))$ ...
Asaf Shachar's user avatar
  • 6,611
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_\...
Liss's user avatar
  • 145
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 ...
DoubleJay's user avatar
  • 2,353
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, ...
Ofir Gorodetsky's user avatar
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 ...
Ash GX's user avatar
  • 273
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 ...
Fedor Petrov's user avatar
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 ...
Asaf Shachar's user avatar
  • 6,611
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 ...
math110's user avatar
  • 4,230
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 ...
gondolier's user avatar
  • 1,829
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 ...
Felix Y.'s user avatar
  • 123
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 ...
Isaac's user avatar
  • 2,727
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 ...
Miroslav Korbelar's user avatar
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 ...
user521337's user avatar
  • 1,189
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): ...
Peter O.'s user avatar
  • 637
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)?
eakbas's user avatar
  • 453
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 ...
Peter Scholze's user avatar
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" ...
dohmatob's user avatar
  • 6,716
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 ...
Mike Izbicki's user avatar
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 ...
JohnA's user avatar
  • 680
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 $\...
Piotr Hajlasz's user avatar
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. ...
Pietro Majer's user avatar
  • 56.5k
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)$ ...
falagar's user avatar
  • 2,761
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 ...
Vesselin Dimitrov's user avatar
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 ...
JohnA's user avatar
  • 680
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 ...
Vesselin Dimitrov's user avatar
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 ...
Turbo's user avatar
  • 13.7k
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$...
Joonas Ilmavirta's user avatar
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(\...
Pietro Majer's user avatar
  • 56.5k
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 ...
Ryan O'Donnell's user avatar
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 ...
Taras Banakh's user avatar
  • 40.8k
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 $...
user521337's user avatar
  • 1,189
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,...
Ewan Delanoy's user avatar
  • 3,565
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}...
Joe Neeman's user avatar
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 -...
Hans-Peter Stricker's user avatar
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,...
Peter O.'s user avatar
  • 637
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 ...
nothappy's user avatar
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 ...
Beni Bogosel's user avatar
  • 2,102
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 ...
Rajesh D's user avatar
  • 704
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 ...
Alex M.'s user avatar
  • 5,207
5 votes
1 answer
2k views

Are piecewise linear functions dense in $W^{1,\infty}$?

Are piecewise linear functions dense in $W^{1,\infty}$ ?
Buyang LI's user avatar
  • 393
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 ...
mathstudent42's user avatar
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 $...
Vesselin Dimitrov's user avatar
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] $$ ...
Ravi's user avatar
  • 101
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 ...
Melika's user avatar
  • 189
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 ...
Peter O.'s user avatar
  • 637
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 ...
Richard's user avatar
  • 357
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 ...
Amir Sagiv's user avatar
  • 3,544