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
1
vote
1
answer
179
views
Approximating rational generating functions
Suppose we have a initial segment $x_1,\ldots,x_N$ (for reasonably large $N$) of a sequence of natural numbers $(x_i)$. We have reason to believe the generating function $\sum_{i=0}^\infty x_iX^i$ is ...
- 13
1
vote
0
answers
129
views
Jackson inequality for a nonpolynomial basis
Hi everybody, this is my first question.$L^2$,$H^p$ are the standard Lebesgue,Sobolev spaces here, and I am deliberately omitting the domains because I'll accept an answer if it's on an interval or a ...
- 191
1
vote
0
answers
226
views
Spectral norm for a truncated Hilbert matrix
Let $T_{N}$ be the (Hilbert) matrix defined by $T_{N}(m,n)=\frac{1}{m-n}$ if $1\leq m,n \leq N$ and $m\neq n$ , and $ T_{N}(n,n)=0$ if $1\leq n \leq N$ .
It's well known that $\Vert T_{N}\Vert < \...
3
votes
1
answer
244
views
Is the Binomial Expectation of a Multivariate Convex Function Convex in the Vector p?
Let $\mathbf{p}=(p_1,\dots,p_m)$ be a vector in $[0,1]^m$ and let $\mathbf{X}=(X_1,\dots,X_m)$ be a vector of independently-distributed binomial random variables such that $X_i\sim \text{Binom}(n,p_i)$...
- 103
0
votes
0
answers
160
views
Two Different Representations of Multivariate Bernstein Polynomials
In the literature the multivariate Bernstein polynomial of a function $f:[0,1]^m\rightarrow\mathbb{R}$ is often defined as the following:
$$B_{f,n}(x_1,\dots,x_m)=\sum_{\mathbf{k}\in \{0,\dots,n\}^m}...
- 103
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$ ...
- 111
64
votes
5
answers
18k
views
The unreasonable effectiveness of Padé approximation
I am trying to get an intuitive feel for why Padé approximation works so well. Given a truncated Taylor/Maclaurin series it "extrapolates" it beyond the radius of convergence.
But what I can'...
- 6,962
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, ...
- 14.7k
3
votes
1
answer
312
views
Approximation theory under $L_1$-error
Is there a reference for results in approximation theory of bounded functions of one (and multiple) variables under $L_1$-error?
Formal definitions for functions of one variable are below.
Let $C$ ...
4
votes
1
answer
942
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 ...
- 43
-1
votes
2
answers
605
views
Approximating a subspace by sampling a base without replacement
Let $X$ be a $p \times n$ matrix, with $p > n$. Now, suppose I sample $m < n$ columns from $X$ at random, without replacement. I would like to characterize the distance between the subspace ...
- 461
6
votes
2
answers
3k
views
Approximating erf by tanh
It appears to be well-known that $\tanh(x)\le \mathrm{erf}(x)$ on $[0,\infty)$. It's off-handedly mentioned here, for example. Where can I find a formal proof? On the one hand, it's hard to imagine ...
- 6,541
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 ...
- 273
2
votes
2
answers
1k
views
Convex upper bound on a linear-fractional function
I have a function of the form $f(x,y) = \frac{x}{c+y}$ where $c$ is a positive constant, $c \ge x \ge 0$, and $y \ge 0$. I would like to find a convex upper-bound for this function. Is there a ...
- 362
4
votes
4
answers
3k
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", &...
6
votes
1
answer
459
views
Approximation power of wavelets
The Wikipedia article on Wavelet Transform states that:
Wavelet compression is not good for all kinds of data: transient signal characteristics mean good wavelet compression, while smooth, periodic ...
- 959
0
votes
0
answers
105
views
approximation in Lie algebras
Let $x_{1}$, $x_{2}$, $x_{3}$ three disctinct closed points of a curve $X$ over an algebraically closed field k.
Let G a connected reductive group and $\mathfrak{g}$ his Lie algebra.
I fix a Borel $...
- 3,472
3
votes
0
answers
440
views
Decay rate of the singular values of functions
Suppose a function $f:[-1,1]^2\rightarrow \mathbb{C}$ has a singular value decomposition:
$$ f(x,y) = \sum_{k=1}^\infty \sigma_k u_k(y) v_k(x), \qquad \sum_{k=1}^\infty \sigma_k^2 <\infty, $$
...
- 3,217
3
votes
0
answers
180
views
A.G. Vitushkin's "Easily representable families of functions" - can it be generalized?
Background
In his monograph "Estimation of the complexity of the tabulation problem" (translated into English as "Theory of the Transmission and Processing of Information") Vitushkin studies ...
- 959
2
votes
0
answers
243
views
Worst-case error and Cramer-Rao Lower Bound - is there any mathematical relation between them?
I would like to understand the relation (if any) between the Cramer-Rao Lower Bound of estimation theory and the following simple definition of "reconstruction accuracy" which doesn't use any ...
- 959
3
votes
2
answers
2k
views
Sampling without replacement until hitting a subset
I randomly sample uniformly from $ \{1,..,N \}$ without replacement until drawing a number $ \leq k$. Denote the expected number of draws by $R(N,k)$. I want a good approximation for $\sum_{k=1}^N R(...
- 63
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}...
- 413
16
votes
2
answers
3k
views
Approximating a convex function by a piecewise linear function
Suppose I have a Lipschitz-continuous convex function $f:\mathbb{R}^n\rightarrow \mathbb{R}$. I wish to approximate it on the unit ball by a piecewise-linear function $g:\mathbb{R}^n\rightarrow \...
- 161
2
votes
1
answer
341
views
Bound on trigonometric sum
I want to show that there is some $\gamma(n)=o(n^{-1})$ and some $C(n) \to -\infty$ such that for $\gamma \leq \theta \leq \pi$ we have
$\sum_{k=1}^n -1+\cos(k\theta) \leq C(n)$.
If we rewrite this ...
- 315
1
vote
2
answers
754
views
Approximation by polynom 1) with respect to supremum-norm 2) I need F_{approx} > F_{exact}
Given a function F, how to find polynom which is best/good approximate with respect supreremum-norm, i.e. minimize over P_{approx} sup|F-P_{approx}| ?
I am intersted in polynoms in two variables of ...
- 24.9k
1
vote
1
answer
185
views
Approximating $\prod_{i=1}^{n-1} (1-ai)$ for large $n$
I have a function of the form:
$f(n) = \prod_{i=1}^{n-1} (1-ai)$
Here, $a \geq 0$ and $(a*i) < 1$. For $n > 10^5$ or $10^6$, what is the best possible analytic approximation for $f(n)$ that ...
- 67
3
votes
3
answers
343
views
Algebraic curve approximation
I am wondering wether it exists a theorem that any continuous path on the plane one can
approximate with algebraic curve $P(x,y)=0$ ($P$- is a polynom)?
- 83
1
vote
1
answer
133
views
are p-limits scales dense in the infinite musical scale of all rational frequencies?
In the wiki section on prime limit tuning, one reads:
...
- 7,853
7
votes
1
answer
249
views
$W^{1,1}$ simplicial approximation
Let $f$ be a continuous real-valued function defined on an $n$ dimesional simplex $\Sigma\subset \mathbb{R}^n $. The classical simplicial approximation scheme provides a sequence $f_k$ of piecewise ...
- 60.6k
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 ...
- 6,694
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 ...
- 109k
6
votes
0
answers
191
views
what books to read to quickly understand adiabatic approximation
Hi group, I'm a theoretical ecologist with fairly adequate training in applied math (ODE, linear algebra, applied probability, some PDEs). In my current work, I've encountered the use of adiabatic ...
- 61
6
votes
1
answer
1k
views
A question about the Beurling-Selberg majorant
Beurling's majorant is defined as the unique entire function $B(z)$ such that the Fourier transform of $B(x)$ is compactly supported in the interval $[-1;1]$, $B(x) \geq \text{sgn}(x)$ and $B(x)$ ...
- 63
2
votes
2
answers
171
views
approximation of holomorphic functions on a halfplane.
Let $\mathbb {C} _ + $ denote the right halfplane and $A$ the algebra
$$
A = \{ f \in H^\infty({\mathbb C} _ +) \cap C(\overline{{\mathbb C} _ +}): \;
|f(z)| \le M (1+|z|)^{-\epsilon} \text{ ...
- 21
13
votes
5
answers
4k
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 ...
5
votes
1
answer
664
views
Are piecewise linear curves dense among Hölder curves?
Consider for some $0 < \alpha \leq 1$ the space functions $x:[0,1] \to \mathbb{R}^n$ such that $x(0) = 0$ and
$\sup_{s,t} \frac{\|f(t)-f(s)\|}{|t-s|^{\alpha}}$
is finite.
There are at least two ...
- 4,304
8
votes
2
answers
1k
views
Approximation by polynomials
Let $f:[a,b] \rightarrow \mathbb{R}$ be of class $C^n$. Let $ x_0, ..., x_m$ be different numbers from $[a,b]$.
Does for each $\varepsilon >0$ there exist a polynom $P$ such that $P^{(k)}(x_i)=f^{...
- 277
9
votes
2
answers
1k
views
polynomials with minimal $L_\infty$ norm on multiple disjoint intervals
It is well-known that Chebyshev polynomials are the polynomials of minimal $L_\infty$ norm on [-1,1] with leading coefficient 1. But what if you want the minimal $L_\infty$ polynomial on two disjoint ...
- 223
9
votes
0
answers
561
views
Padé approximations of $e$
The following question came up in the analysis of some algorithm.
Let $R_{s,t}(z)$ be the Padé approximants of $e^z$, and define $r_{s,t} = R_{s,t}(1)$. Using the explicit expression for the error ...
- 1,906
5
votes
2
answers
1k
views
Stone-Weierstrass for monotone functions
Let $\; f : [0,1] \to \mathbb{R} \;$ be continuous and non-decreasing. $\;\;$ Let $\epsilon$ be a real number such that $\; 0 < \epsilon \;$.
Does it follow that that there exists a real ...
user5810
2
votes
0
answers
195
views
Markov-type inequalities with arbitrary exponents
By a Markov-type inequality I mean an inequality of the form
$$
\| p^{(k)} \| \leq \lambda_{k,n} \| p \|,\quad \forall p \in U_n,
$$
for some $\lambda_{k,n} > 0$, where $U_n \subset L^\infty[-1,1]$ ...
- 191
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 ...
- 69
6
votes
1
answer
1k
views
Low degree polynomial approximation for the entropy function
Let $X$ be a discrete random variable with possible values
$\{x_1,\ldots,x_n\}$, and let $p$ denote the probability mass function of
$X$. In addition, denote $p_i=p(x_i)$.
The entropy of $X$ is ...
user17253
19
votes
1
answer
2k
views
Accumulation of algebraic subvarieties: Near one subvariety there are many others (?), 3
Part 3 of this series of questions. In the meantime, I realized that there is some very simple question that was left open in Accumulation of algebraic subvarieties: Near one subvariety there are many ...
- 21.3k
0
votes
1
answer
369
views
Low degree approximation of the polynomial extension of the logical-or function
Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$).
Consider ...
user17253
2
votes
1
answer
367
views
Trigonometrical approximation for the characteristic function of an interval
Hello,
Denoting $e(x)$ for $e^{2i\pi x}$, set
$$E(R):=\left\{f\ \left|\ f(x)=\sum_{r=0}^{R-1}a_re(rx)\mbox{ where }a_r\in\mathbb{C}\ \forall r\mbox{ and }\sum_r|a_r|^2=1\right\}\right.$$
$h(a,R):=\...
15
votes
0
answers
517
views
Functions approximated by rolling epicycle curves
Imagine a decreasing sequence of (positive) radii $r_1 > r_2 > r_3 > \cdots$
and a series of nested circles $C_1 \supset C_2 \supset C_3 \supset \cdots$
with these radii,
initially each ...
- 151k
6
votes
5
answers
3k
views
Approximation to the ratio of a Gaussian CDF to PDF
Johnstone and Silverman (2005) claimed that for large x
$\frac{1-\Phi(x)}{\phi(x)} \approx \frac{1}{x}$
where $\Phi(x)$ and $\phi(x)$ are the CDF and PDF for a normal random variable.
I was able ...
- 203
7
votes
3
answers
3k
views
Uniform approximation of $x^n$ by a degree $d$ polynomial: estimating the error
The answer to this question should be well known, but it's a hard question to search for online.
Suppose we want to approximate the function $x^n$ by a polynomial of degree $d$ in the $L_\infty$ norm ...
- 6,694
3
votes
1
answer
955
views
Least-squares regression and differential geometry
For $k, n \in \mathbb{N}$, let $\mathcal{C}_n \mathbb{R}^k$ denote the configuration space of $n$ distinct points in $\mathbb{R}^k$.
(1) Is there a description of the tangent space $T_C \mathcal{C}...
- 952