The approximation-theory tag has no wiki summary.

**5**

votes

**0**answers

217 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} ...

**4**

votes

**1**answer

286 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 ...

**2**

votes

**0**answers

103 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' ...

**3**

votes

**1**answer

421 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 ...

**3**

votes

**1**answer

640 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 ...

**2**

votes

**5**answers

1k 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$ ...

**1**

vote

**1**answer

689 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 ...

**2**

votes

**2**answers

872 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: ...

**3**

votes

**1**answer

478 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 ...

**0**

votes

**1**answer

462 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 ...

**1**

vote

**4**answers

2k views

### A differentiable approximation to the minimum function

Suppose we have a function $f : \Re^N \rightarrow \Re$ which, given a vector, returns the value of its smallest element. How can I approximate $f$ with a differentiable function(s)?

**4**

votes

**2**answers

275 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 ...

**7**

votes

**4**answers

4k 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)$ ...

**4**

votes

**3**answers

526 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 - ...

**6**

votes

**2**answers

1k 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 ...

**5**

votes

**4**answers

2k 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 $\underline{order}$ $n$.
Define $E_n$ to be the collection of all ...

**2**

votes

**1**answer

775 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$ ...

**12**

votes

**5**answers

897 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 ...

**1**

vote

**1**answer

749 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: ...

**1**

vote

**1**answer

323 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$) ...

**7**

votes

**2**answers

3k 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$ ...

**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 ...

**2**

votes

**2**answers

755 views

### Aproximation 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 ...

**11**

votes

**4**answers

570 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 ...

**6**

votes

**0**answers

426 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 ...

**5**

votes

**1**answer

296 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$) ...

**3**

votes

**2**answers

919 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 ...

**13**

votes

**6**answers

3k 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 ...

**4**

votes

**1**answer

447 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 ...

**8**

votes

**3**answers

641 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 ...