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
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 ...
- 21.3k
27
votes
2
answers
3k
views
Accumulation of algebraic subvarieties: Near one subvariety there are many others (?)
Let's work over the field $\mathbb{C}$ of complex numbers, and let $X\subset \mathbb{P}^n$ be a projective variety. Let $\tilde{X}\subset \mathbb{P}^n$ be any small open neighborhood of $X$, in the ...
- 21.3k
5
votes
0
answers
412
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 ...
- 1,171
1
vote
3
answers
3k
views
Approximation in $L^2$ by piecewise constant functions
Dear all,
in order to prove the validity of my Galerkin approach of a certain variational problem, I need to check the so-called approximability property. In my case, it boils down to showing that for ...
- 23
1
vote
1
answer
502
views
nonnegative series expansion of nonnegative functions
The title says it all! When using orthogonal series expansions like the Gram-Charlier expansion to approximate probability density function, a big problem (making this approach less usefull and less ...
- 2,600
2
votes
1
answer
466
views
Regularization of Zygmund functions
Dear community.
I would like to derive a "good" estimate on $\frac{d}{dt}f_\epsilon(t)$, where $f_\epsilon$ is a regularization of a Zygmund-continuous function $f$, i.e.
$|f(x-\tau)+f(x+\tau)-2f(x)|...
- 742
8
votes
3
answers
2k
views
Kronecker Approximation theorem and Fibonacci numbers
There is a famous old theorem by Kronecker that for every positive real $\alpha$ and $\epsilon>0$ there exists a positive integer n such that $\alpha n$ is within $\epsilon$ of an integer.
...
- 606
5
votes
5
answers
3k
views
best approximation to the LambertW(x) or exp(LambertW(x))
what is the best available approximation ( say up to 10 digits ) for LambertW(x) or exp(LambertW(x)) for x > 2000
- 153
2
votes
1
answer
336
views
Cubic spline smoothing question
I came across this link when searching for an algorithm for spline smoothing. Though I understand basically what I have to do, I need further clarifications on the formula chosen for curvature ...
- 351
6
votes
3
answers
502
views
Approximating derivatives between gridpoints
Suppose we have a grid (possibly irregular) of $N$ function/value pairs, $(x_i, f_i)$, $i=1...N$. The function is differentiable everywhere at least twice (perhaps more).
What would be a good way to ...
- 177
5
votes
2
answers
958
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}\...
- 696
2
votes
3
answers
5k
views
Smooth approximation of the hinge loss function
I came across a paper but the smooth approximation for the hinge loss function is wrong. Can someone guide me to the proper smooth approximation (using polynomials) of the function $$h(x)=\max(0,1-x)$$...
- 111
3
votes
0
answers
239
views
Density of C^\infty in the domain of the exterior derivative on a noncompact, complete manifold?
Let $(M,g)$ be a geodesically complete Riemannian manifold that is not necessarily compact. Futhermore, assume that $M$ has at most exponential volume growth (ie., locally doubling property). Let $\mu$...
- 51
3
votes
1
answer
3k
views
Simple algorithm to generate a Mondrian "Random Grid"
I was wondering if there is a simple way or algorithm that can generate 2-d grids resembling Mondrian paintings like the boogie woogie grid ( https://nuit-blanche.blogspot.com/2010/12/cs-boogie-woogie-...
- 65
10
votes
1
answer
873
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.
...
- 60.6k
0
votes
0
answers
724
views
What is the function $\sin(n \omega) / (n \sin \omega)$?
During my work, I encounter the function like $\frac{\sin(n \omega)}{n \sin \omega}$. I'm puzzled and knew nothing about this function before.
Given integer $n>1$, my question is how to find a ...
- 173
10
votes
3
answers
1k
views
Non-linear "Fourier analysis"
Call a function of the following form a beep: $e^{-(\frac{x-\alpha}{\beta})^2}\sin(\rho x+\theta)$. Given a real-valued function $f\in L^2(R)$ and a number $n$, I'm interested in the approximating $f$...
- 17.6k
11
votes
4
answers
2k
views
A senseful meaning of 'approximation of manifolds'?
Any continuous function can be uniformly approximated by smooth functions.
I would like to have something similar - in what-ever sense - for continuous manifolds.
For example, by Whitney's theorem, ...
- 5,327
6
votes
0
answers
273
views
Polynomial upper approximation with respect to the Gaussian measure
Let $f = 1_{[a,+\infty)}$ be the indicator function of a half-line. Does there exist a sequence $(P_n)$ of polynomials such that $f(x) \leq P_n(x)$ for every real $x$ and
$$ \lim_{n\to \infty} \int_{\...
- 4,653
4
votes
1
answer
309
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 ...
- 817
2
votes
0
answers
104
views
Noisy bases for linear functions
For any $x \in \mathbb{R}^n$, the following statement is trivially true:
There exists a set $I \subset \mathbb{R}^n$ with $|I| \leq n$ such that for any $x' \in \mathbb{R}^n$, if $x \cdot y = x' \...
- 794
3
votes
1
answer
499
views
methods for interpolating a function, holomorphic in the upper halfplane
Let $n,k\colon\mathbb{R}\to\mathbb{R}$ be real functions such that function $N$ given by $N(x)=n(x)-ik(x)$ is a holomorphic function in the upper half-plane. Also I know some additional properties of ...
- 1,284
3
votes
1
answer
795
views
Where does the Chebyshev polynomial notation come from?
The $k$th Chebyshev polynomial is denoted by $T_k$ where
$T_k(x) = \cos(k\cos^{-1}(x))$
I was wondering where this notation came from. It has been suggested that it comes from Tschebyscheff (the ...
- 3,217
5
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$ ...
- 403
2
votes
1
answer
1k
views
Padé approximation - usability in iterative algorithms
Firstly, I have to say that I don't understand Padé approximation well.
But I discovered that, it is more precise than Taylor series.
I have to create approximation for these functions: Log(x) and ...
- 23
3
votes
2
answers
2k
views
Interpolation splines of bounded curvature
Given $n$ points $p_i=(x_i,y_i)$ on the [Euclidean] plane, and a positive real number $\rho$. Can we have a polynomial spline (e.g., natural cubic spline) passing through all these points, such that: (...
- 627
3
votes
1
answer
507
views
Approximating an integral representation of the Number Partition Problem
One can write out an integral whose solution gives the number of solutions to the NP-Complete Number Partition Problem and I'm wondering if anyone has an suggestions or ideas on who to solve or ...
- 513
0
votes
1
answer
637
views
Rational solutions of homogeneous equations
Can every solution of a homogeneous linear system be approximated by a solution in rational numbers?
In mathematical terms: Let $$Ax=0$$ be a homogeneous linear system in $n$ determinates for an $m\...
- 10.4k
15
votes
5
answers
14k
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)?
- 453
4
votes
2
answers
302
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 ...
- 313
11
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)$ ...
- 2,821
4
votes
3
answers
769
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 - ...
- 179
6
votes
2
answers
2k
views
Efficient approximation of a matrix and its inverse
Assume that $ A $ is a real $ n\times n $ matrix whose rows constitute an orthonormal basis of $ \mathbb R^n $.
Informal statement of question: Assume we want to approximate $ A $ by a rational ...
- 201
8
votes
4
answers
4k
views
Approximation by exponential polynomials
Let $u(t) = \Sigma_{k=1}^n c_k e^{\lambda_k t} (c_k \in \mathbb C, \lambda_k \in \mathbb C) $ be an exponential polynomial of order $n$.
Define $E_n$ to be the collection of all exponential ...
- 1,795
2
votes
1
answer
1k
views
Probability of system failure in a distributed network
I am trying to build a mathematical model of the availability of a file in a distributed file-system. The system works like this: a node $x$ stores a file $f$ (encoed using erasure codes) at $rb$ ...
- 121
13
votes
5
answers
1k
views
Does this sequence span $L^2$?
Consider the following sequence of functions in $L^2[0,\infty)$:
$$f_n(x)=e^{-x/n}x^n,\;\;n\geq 1$$
Does this sequence span $L^2[0,\infty)$ (that is, is the set of finite linear combinations
of these ...
- 520
1
vote
1
answer
813
views
Fast gradient approximations
I am trying to use the one-sided Simultaneous Perturbation (SP) method to get a gradient approximation for multi-variable function.
The equations are very simple: $g_{i}=\frac{f(x+c\delta)-f(x)}{c{\...
- 121
1
vote
1
answer
793
views
References regarding unisolvent sets
Let $X = {x_1, ..., x_N}$ be a finite subset of $R^n$ and let $p$ and $q$ be any polynomials of degree $k$ or less. X is called $\underline{P_k-unisolvent}$ if $p(x_j) = q(x_j)$ ($j = 1, ..., N$) ...
10
votes
2
answers
5k
views
Approximate a probability distribution by moment matching
Suppose we want to approximate a real-valued random variable $X$ by a discrete random variable $Z$ with finitely many atoms. Suppose all moments of $X$ is finite. We want to match the moments of $X$ ...
- 1,839
3
votes
1
answer
1k
views
Matrix approximation
Let A be an $m\times n$ matrix and $k$ be an integer. Assume that $A$ is non-negative. We want to find a scalar $\epsilon$ and an $n\times n$ matrix $B$ such that $A\leq A(\epsilon I + B)$ (where $\...
- 145
10
votes
3
answers
22k
views
Approximation of a normal distribution function
I am reviewing and documenting a software application (part of a supply chain system) which implements an approximation of a normal distribution function; the original documentation mentions the same/...
- 211
17
votes
4
answers
993
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)...
- 3,595
8
votes
0
answers
605
views
convergence rate in Wiener's approximation theorem
Wiener has the following fantastic results about approximations using translation families:
Given a function $h: \mathbb{R} \to \mathbb{R}$, the set $\{\sum a_i h(\cdot - x_i): a_i, x_i \in \mathbb{...
- 1,839
6
votes
1
answer
347
views
Sparse approximate representation of a collection of vectors
Suppose I have a collection of $n$ vectors $C \subset \mathbb{F}_2^n$. They are of course spanned by the canonical set of $n$ basis vectors.
What I would like to find is a much smaller (~ $\log n$) ...
- 583
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,...
- 3,595
29
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 ...
- 2,383
4
votes
1
answer
945
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-...
- 3,595
9
votes
3
answers
763
views
Approximating with translated Gaussians and low-frequency trig functions
Defining the translated Gaussians by $f_t(x)=\exp(-(x-t)^2)$ for $t,x\in\Bbb{R}$, we showed that the linear span of $\{f_t \mid 0 \le t < \epsilon\}$ is dense in $L^2(\Bbb{R})$, for any $\epsilon&...
- 524
9
votes
6
answers
8k
views
How to approximate a solution to a matrix equation? [closed]
Suppose a matrix equation $Ax = b$ has no solution ($b$ is not in the column space of $A$)
How can I find a vector $x^\prime$ so that $Ax^\prime$ is the closest possible vector to $b$?
- 461