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

109 questions
Filter by
Sorted by
Tagged with
211 views

• 485
1 vote
126 views

### in Finite Element, which approximation requires less number of unknowns: B-splines vs Shape functions vs Spectral Elements

In Finite Element Analysis, one requires to approximate the solution in terms of basis functions. My questions is, which method in general is better? by 'better', I mean which involves less number of ...
218 views

### How to optimize an approximated matrix multiplication?

[UPDATING] The old one is a simplified version of the current one. Here is a solution based on the answer proposed by professor Bangerth down below. To describe what I am trying to do, first rewrite ...
1k views

### Faster Logistic Function

I've noticed that a fairly significant number of cycles in one of my programs are being consumed by the logistic function: $$f(x)=\frac{1}{1+e^{-x}}$$ Is there a good approximation I can use to reduce ...
• 4,021
1 vote
733 views

### Kolmogorov n-width

Could someone please point me to an understandable definition of the Kolmogorov n-width? I'm having a hard time figuring out what is the output of the definition - is it an integer? Edit: I realize ...
• 832
1 vote
808 views

### Finding the parameters of a function via curve fit

I'm trying to estimate the parameters (v, n, k) defined in fit_func. I tried the default least squares fit but I couldn't find the parameters successfully. ...
• 433
659 views

### Curve fitting using a piecewise polynomial

I am trying to fit a piecewise polynomial function Code: ...
• 433
1 vote
42 views

### Integral from function approximations

I have some data which I cannot manage to model and fit with a known function, so let’s say that they are a sample from the unknow function $f(x)$, which look a sort of skewed bell-shaped distribution....
56 views

### Estimating $n$ column norms of $A$ by using less than $n$ calls to $Ax$?

Suppose I have an $m \times n$ matrix $A$ that is only accessible through matrix-vector products $Ax$. These are expensive, is there a way to approximate vector $x$ of $n$ column norms of $A$ by using ...
• 2,735
87 views

• 2,735
244 views

• 181
1 vote
79 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 ...
• 331
229 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 ...
• 181
704 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 ...
• 131
2k 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?
39 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 ...
• 21
348 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 ...
• 109
101 views

• 73
337 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 ...
• 56.2k
47 views

• 1,077
100 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} ...
• 109
300 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 ...
• 225