Questions tagged [approximation]
A method of finding nearly-optimal solutions to a problem. Generally, this terminology is applied to algorithms and heuristics for solving NP-Hard problems in computer science.
84
questions
1
vote
0answers
63 views
Error curve does not oscillate in between reference points using Remez
Using the Remez algorithm, implemented using multi-precision library, in certain functions that I want to approximate, the error curve does not oscillate in between reference points, and so no roots ...
0
votes
1answer
36 views
Linearization of Remez algorithm rational case
In the rational case, we are interested to find polynomials $P(x)$ and $Q(x)$ s.t.
$f(x_k)-P(x_k)/Q(x_k)=(-1)^kE$ for $k=1,2,\ldots, N$ where $N=deg(P)+deg(Q)+2$
This can be rewritten as
$$
(1)~~~~~~(...
1
vote
1answer
60 views
Questions on Daubechies wavelets
Is the refinement equation for the orthonormal Daubechies scaling function
$$\phi(x) = \sqrt{2} \sum_n h_n \phi(2x-n) \;?$$
The filter coefficients for Daubechies wavelets have been given e.g. in
this ...
2
votes
0answers
76 views
Remez algorithm convergence
I have implemented the Remez algorithm in Python where all calculations were done with the Python mpmath library. I have noticed that sometimes the $|E_{max}|$ and $|E_{min}|$ do not monotonically ...
3
votes
3answers
100 views
What are some algorithms to calculate the width of an arbitrary polygon when a bounding box approximation is inaccurate
What are some alternative algorithms to creating a bounding box for finding the max width of a concave, simple winding polygon, like the one in the below image? I prefer solutions that are more ...
0
votes
1answer
77 views
what is non-asymptotic convergence?
I guess convergence in general means it is in asymptotic sense but what does non-asymptotic convergence mean?. Can someone please explain with an example?
0
votes
0answers
27 views
Computing square root of rank-1 correction
In the post Computing square root of diag(u)-uu'?, both @YaroslavBulatov and @NickAlger suggested the factor $\frac{\sqrt{u^{T}D^{-1}u+1}-1}{u^{T}D^{-1}u}$ for their approximation.
Can somebody ...
2
votes
0answers
28 views
Fast approximate evaluation of Fourier-Legendre series
Suppose I know that a function from $[0,\pi] \to \mathbb{R}$ may be written as
$$
\sum_{k=0}^\infty A_l \frac{2l+1}{4\pi} P_l(r)
$$
where $A_l$ all are known. Is there a way in which I may very ...
0
votes
2answers
96 views
How can I calculate the exponential integral?
(I originally asked this in a different exchange.)
I'm writing a program that uses the prime-counting function. Right now, I'm using x/log(x), but I want to ...
4
votes
1answer
59 views
approximate function such that the inverse of the approximation is “simple”
I have a smooth enough injective function $f:[a, b]\to \mathbb{R}$ which I want to approximate by something that can be computed quickly, e.g., a Padé approximant of low degree,
$$
\frac{\sum_{j=0}^m ...
4
votes
0answers
70 views
Fast approximate solver for vehicle routing problem
I need to solve capacitated asymmetrical vehicle routing problem with time windows on ~30k points. Time limits for calculations are 2 hours. I've tried using Clarke and Wright savings algorithm, it is ...
4
votes
0answers
138 views
MATLAB: Compute the Schwarz-Christoffel transformation symbolically
Suppose we have a conformal mapping from the unit disk in the $\omega$ plane onto the exterior of a polygon in the $z$ plane.
The Schwarz-Christoffel mapping in this case is defined as:
$$f(u) = A - ...
7
votes
1answer
235 views
Size of jump for piecewise discontinuous approximations
If one has a sufficiently smooth function $u$ that is approximated by a piecewise constant function $u_h=\Pi^0_h u$ on a mesh of cell size $h$ (where $\Pi^0_h$ is the $L_2$ projection onto the ...
0
votes
1answer
42 views
Slightly change two vectors to satisfy a constraint
$\vec{a}\cdot\vec{b} \approx c$
$\vec{\alpha} \cdot \vec{\beta} = c$
$\vec{\alpha}$ is close to $\vec{a}$ and $\vec{\beta}$ is close to $\vec{b}$
Given $\vec{a}$, $\vec{b}$ and c, how to find $\vec{\...
5
votes
0answers
200 views
What algorithm does (or did?) Excel use for Bessel functions that is discontinuous at x=8?
Writing this comment reminded me of something I noticed years ago about evaluating Bessel functions of the first kind $J_n(x)$ in Excel. (BESSELJ)
I don't use Excel now but at the time I'd checked ...
2
votes
0answers
56 views
Weighted Set Cover in practice, beyond the greedy algorithm
According to the wikipedia page for Set Cover, the greedy algorithm for weighted set cover achieves the polynomial-time approximation bound. There are other techniques for solving Set Cover, such as ...
1
vote
1answer
102 views
Approximation of a non linear problem with python
I need your help to solve a problem I'm working on for school.
My goal is to approximate the coefficients of a weight matrix so that they check particular properties.
So I have $W$ the weight matrix ...
3
votes
2answers
241 views
Image hash similarity matching possible?
I have the following question:
We have two face image files (JPEG), a Matrix of $128\times 128$ with values between 0-255.
We would like to hash both image files using a function $f(x, key)$. Where I ...
2
votes
1answer
97 views
Taylor expansion of error - Finite elements approximation
In some of my computations I calculate a scalar value $\lambda_h$ (in my case an eigenvalue) depending on a finite element discretization of the domain. Usually we can manage to find estimates of the ...
0
votes
1answer
78 views
Which are some good algorithms and heuristics to calculate the similarity between two matrices?
Say I have a matrix like this:
\begin{bmatrix}
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 1 \\
0 & 1 & 1 & 1 \\
\end{bmatrix}
And this one:
\begin{bmatrix}
...
0
votes
1answer
202 views
Linear Least-Squares Point-to-Plane ICP degenerative case
I'm trying to implement Linear Least-Squares Optimization for Point-to-Plane ICP Surface Registration
Paper describes linear approximation for point to plane distance for rigid ICP. This approach is ...
0
votes
1answer
53 views
Chebychev Polynomial derivatives at zero points and extreme points
I was looking for some help with derivatives of Chebychev polynomials at zero points. The recursive expression,
$$
T_{(j+1)}(x) = 2xT_j(x) - T_{(j-1)}(x)
$$
has the derivative
$$
T'_{j+1}(x) = 2T_j(...
0
votes
1answer
1k views
Derivatives of a Chebychev polynomial
I am using Chebychev collocation nodes for approximation, and my problem requires me to calculate derivatives of the polynomial. I have been reading from a few sources, but I am not sure I understand ...
1
vote
0answers
53 views
Computing dilogarithm
I'm measuring the integral of a quantity which, mathematically, requires the computation of a dilogarithm function.
$$\operatorname{Li}_2(be^{ax})$$
where $b$ and $a$ (are real and) can be positive ...
0
votes
1answer
203 views
B-Splines Matlab Package
I'm looking for a good Matlab package/library for B-Splines approximation. Ideally, it would take knots $t_1, \ldots , t_n$, and data points $g(t_1),\ldots , g(t_n)$, and Produce $$Vg :\,= \sum\...
4
votes
0answers
83 views
Extrapolation after successive finite element refinement
I wish to compute a certain function $\lambda$ (in my case an eigenvalue of the Laplacian) to a certain accuracy, which I wish to guarantee, if possible. I started with a finite element method. I know ...
4
votes
1answer
598 views
Chebyshev approximation by projection vs interpolation
Suppose we want to approximate a function $f: [a, b] \rightarrow \Re$ with a Chebyshev series:
$$ f(x) \approx \sum_{k=0}^n c_k \, T_k\left( \frac{2x-b-a}{b-a} \right) $$
where $T_k(x) = \cos(k\, \...
4
votes
1answer
170 views
Numerical evaluation of the Exponential Integral Ei by rational Chebyshev approximations fails
I am trying to evaluate the Exponential Integral $Ei(x)=-\int^{\infty}_{-x}\frac{e^{-t}}{t}dt$ for $x>0$ (interpreted as the Cauchy principal value) by using rational Chebyshev approximations, ...
1
vote
0answers
35 views
Find alternative path closest to original
I have a set of points in a 2D space. I want to connect the outer points so I get the convex hull. The problem here is that there is a limit to the distance between two points. Let me clarify that ...
1
vote
1answer
50 views
Finding optimal point distance to get desired number of random points in an area
I have a random point generator which takes a distance $d$ and fills an area with points such that distance between any two points is no less that $d$:
I need to control the number of points in the ...
5
votes
1answer
403 views
Polynomial order of an approximation of a section of sine and numerical accuracy
I was playing with the idea that a sine function is periodic. But even within one period there are symmetries, namely the second fourth of a period is the mirror image of the first fourth and the ...
2
votes
1answer
2k views
imaginary time propagation to find ground state wavefunction
I understand the basic idea of imaginary time propagation method:
The wavefunction $\psi(x,t)$ as a superposition of energy eigenstates $\phi_m(x)$:
$$
\psi(x,t)=\sum_m \phi_m(x)e^{-iE_mt/\hbar}
$$
...
1
vote
0answers
45 views
Alternative to two “for” loops in finding best neighborhoods for TSP?
I am trying to solve Travelling Salesman Problems using tabu search. I have been able to successfully find "near enough" optimal solutions (as well as one optimal, yay!).
For the moment I am using ...
4
votes
2answers
352 views
Interpolation with the roots of orthogonal polynomials & Spectral expansion
I'm a bit confused about the relationships between these two approximation methods mentioned in the title.
Does this kind of interpolation also belongs to the field of spectral methods?
Are the ...
3
votes
2answers
2k views
Methods for fast approximation of convolution
What are the state of the art methods for fast 2D convolution approximation?
I'm familiar with SVD based multiplication and cross approximation approaches, but would be thankful to get additional ...
5
votes
0answers
127 views
Are there any benefits of computable analysis to numerical algorithms
Computers can work only with computable numbers, while most of the algorithms are based on analysis of real numbers (real analysis).
When I heard of the existence of computable analysis I ...
6
votes
1answer
278 views
Does this Algorithm (probably Fourier like) Exist for 2D Shapes? [closed]
Update: Someone changed the title to this post to a possible answer ("Fourier decomposition of parametric shapes") but I changed it to a different title as that makes it clear what I was asking. As I ...
1
vote
1answer
71 views
Expected number of steps before a global optimum is found with Simulated Annealing
I'm reading a technical report on Simulated Annealing: On the Convergence Time of Simulated Annealing, by Sanguthevar Rajasekaran. You may find it following this link.
Given $G=(V, E)$ is the graph ...
5
votes
2answers
3k views
Solving a system of linear equations with only an approximate solution
I have a system of linear equations that is derived partially from experimental data. Theoretically, the system should have a single, exact solution; however, experimental error causes it to not have ...
3
votes
0answers
153 views
Reference Request: Variational Problem
I want to solve approximately the following variational problem:
Given a function $c:[-1,1]^2\rightarrow [0,1]$, constants $p_1...p_n\in \mathbb{R}^+$, $\alpha_1...\alpha_n\in \mathbb{R}$, and $\...
3
votes
1answer
401 views
Efficient Implementation of Taylor Series for Sine
I am trying out a few forms of polynomial expression optimization, and I'd like to improve of what I've got, if anyone has anything they know is better.
Implementation 1:
$$x-\frac{x^3}{3!}+\frac{x^...
6
votes
1answer
465 views
Fast algorithm for computing matrix square root using randomized linear algebra?
Is there a fast algorithm for computing the matrix square root of a real symmetric matrix using random matrices or randomized algorithms?
6
votes
1answer
368 views
Matching/Assignment Problem
I'm not sure how I can represent and solve the following problem.
I have a list of sales (timestamp and quantity) and a list of corresponding inventory draws (timestamp and quantity). What I ...
3
votes
1answer
420 views
Efficiency of an algorithm
I designed an algorithm to find the global minimum of a function and implemented it in MATLAB. And I also implemented the "Tunneling algorithm" for the global minimum of a function in MATLAB.
But now,...
7
votes
1answer
440 views
Problems Implementing the Remez Algorithm
So first off:
*** This code is not being used in production software.
It is a personal project of mine, trying to understand
approximation theory and advanced curve fitting.
In other words, I'm ...
1
vote
0answers
49 views
A better way to compute a double integral involving a infinite series?
Let $D_{\nu}(.)$ is the parabolic cylinder function
(http://mathworld.wolfram.com/ParabolicCylinderFunction.html)
And $\Gamma(.)$ is the Gamma function.
Define
$s_y(\mu,\nu,t,z)=2^{\nu}\...
0
votes
2answers
118 views
Looking for a particular algorithm for numerical integration
Consider the following differential equation
\begin{equation}
p(t) = \frac{\partial q(t)}{\partial t}
\end{equation}
where $t \in (0,\infty)$. I have a build a code that spits out values of the ...
-1
votes
1answer
401 views
Finite Difference for Fourth-Order PDE
How to discretize the following 4th order PDE using finite difference method?
$$\frac{\partial^{2} y}{\partial t^{2}}+\frac{\partial^{4} y}{\partial x^{4}}=0$$
thanks
2
votes
0answers
92 views
Finding most efficient route (distance/number of nodes) that uses nodes at least X amount away from another node
I'm trying to find the "looped" route with the lowest value of D/n, where D=Distance, and ...
1
vote
0answers
68 views
Piecewise linear fitting of a curve in loglog plot
Iam basically trying to fit a curve similar to that shown in fig (a) with 7 straight line segments (ie. 6 knots) as shown in fig (b) and I need to get the optimum knot positions. This is a tripartite ...
