All Questions
1,732 questions
0
votes
0
answers
45
views
Newton method for polynomials with random starting points
I know that this question exists, but unfortunately it doesn't cover my issue sufficiently.
Assume that we have a polynomial $p(x)$ of degree $n$ with real coefficients, we can assume that all its ...
- 1,171
3
votes
1
answer
132
views
How to maximize the variance of a subset of integers?
$\DeclareMathOperator{\Var}{Var}$Given the set of numbers $\Omega := \{1, \ldots, n\}, n \in \mathbb{Z}^+$, how can I choose a subset, $A$ of $\Omega$ , such that $\min(\Var(A), \Var(\Omega \setminus ...
- 41
2
votes
0
answers
46
views
Convergence of finite-difference method for Cauchy-Riemann equations
Let $I\subseteq \mathbb{R}$ an open interval. Let $f:I\rightarrow \mathbb{C}$ real analytic. Suppose we want to numerically compute an analytic extension of $f$.
We will assume the following: we are ...
- 312
1
vote
0
answers
29
views
Integral hull of a polyhedron Q is polyhedron
Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
- 21
-1
votes
0
answers
41
views
Is it possible to backtrack an optimization solver? [closed]
I have an optimization problem and was using a linear programming optimizer to find solutions. However, I find that past a certain size, the problem becomes "infeasible" and has no solutions....
0
votes
0
answers
57
views
Complexity of evaluation of analytic functions
Given an analytic function $f(x)$ (say as combination of elementary functions and operators), is it possible to compute $n$ first bits of the value of the function on the whole interval $[a, b]$ ...
- 67
0
votes
0
answers
21
views
Easy instance of set cover
I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
- 4,049
7
votes
2
answers
242
views
Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$
Let $x_1, \dotsc, x_n \in \mathbb{R}^d$ and $\theta_1, \dotsc, \theta_n \in \mathbb{R}^d$ be vectors such that for every $k \in [n]$, the following inequality holds:
$$
\langle x_k, \theta_k \rangle &...
1
vote
0
answers
58
views
Method of characteristics, the characteristic lines follow gradient, is this significant?
The PDE I am working on comes from geology, which I do not have much background on.
Said equation aims to describe describes the erosion by describing it as an advection phenomena: the advection ...
- 11
1
vote
1
answer
141
views
Understanding quadrature rule of a function multiplied by another $C^{\infty}$ function
Define a function $f \in C^m[-1,1],m \in \mathbb{N}$ and $g\in C^{\infty}[-1,1]$. Also define a quadrature rule $Q$ for approximating the integral $\int_{-1}^1 h(x)dx$ for some function integrable ...
- 69
0
votes
2
answers
97
views
Optimization algorithms for Kronecker approximation of high-dimensional covariance matrices
I'm working with a high-dimensional covariance matrix and exploring Kronecker product approximations to make it computationally manageable.
Here's the setup:
I have a graph $G$ represented by a $D\...
- 1
5
votes
0
answers
75
views
What is the maximal advantage of randomized over deterministic algorithms for approximation in the worst-case?
Let $X\subset Y$ be Banach spaces and $B_X:=\{x\in X: \|x\|_X\le1\}$ be the unit ball of $X$.
The goal is to find an approximation of every element from $B_X$ with error measured in $Y$ by using at ...
2
votes
4
answers
212
views
Efficient algorithm for graph problem
Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and ...
- 157
1
vote
1
answer
152
views
Linear interpolation vs L2-projection
I'm reading the book "The Finite Element Method: Theory, Implementation, and Applications" by Larson and Bengzon. In the first chapters there are presented two methods for approximating ...
- 19
1
vote
1
answer
106
views
Iterated optimal transport
Suppose we are interested in two consecutive transport plans (in the Kantorovich formulation). That is, we are given finite sets $X$, $Y$ and $Z$, endowed with probability measures $\mu_X$, $\mu_Y$ ...
- 13
4
votes
1
answer
253
views
Reference to formal approach to homotopy analysis method
I'm currently reading a book about the Homotopy Analysis Method (HAM), but it isn't very rigorous (it explains most things with a single example), which is bothering me.
I'm searching for papers where ...
- 151
3
votes
1
answer
138
views
Handling absolute value and other discontinuities in numerical optimization methods that use gradients
Suppose we have difficult peak fitting problems where the the users wish to fit asymmetric peaks to their experimental data by the least squares method. One such function is illustrated below:
Here
$...
- 879
4
votes
0
answers
198
views
Pricing zero coupon bonds through PDE
I'm currently studying Paul Wilmott on quantitative finance and saw an interesting idea for an interest rate model that went unexplored in the book.
The idea is to model the market price of risk as a ...
- 51
0
votes
2
answers
178
views
Inversion formula for discrete sine and cosine transforms
$\newcommand{\wh}[1]{{\widehat{#1}}}
\newcommand{\R}{{\mathbb{R}}}
$I am looking for a proof of the inversion formulas for the discrete sine and cosine transforms, i.e. a proof of the fact that these ...
- 113
4
votes
1
answer
88
views
Simulation of SDEs using Karhunen Loeve expansion
A very common and easy way to simulate the solution of a SDE is to use the Euler-Maruyama method. At each time step the only random part comes from the realization of the increment of the Brownian.
It ...
3
votes
1
answer
79
views
How to deal with singularities in thin plate splines?
Follow up from this question Thin-Plate-Spline understanding and solution.
In the general case of $\mathbb{R}^N$ the following problem (interpolant which minimizes the Thin Plate Energy, specifically ...
- 115
1
vote
0
answers
69
views
Newton-Kantorovich: theorem geometric
This post is cross-posted from Math StackExchange where I did not receive any response after 5 days. I guess this question might be targeted more towards research level mathematics, so I decided that ...
- 11
0
votes
0
answers
25
views
Numerical computation of spectral abscissa of operator
I would like to numerically compute the spectral abscissa of an unbounded linear operator $A$ on a Hilbert space. To give you an idea my operator has the form:
$$Af(x,y) = a(y) \partial_x f(x,y) - b(x)...
- 143
0
votes
0
answers
48
views
A question on a quantitative form of Farkas' lemma
Suppose A is an $m \times n$ matrix whose entries are non-negative integers and $\mathbf{b}$ is a vector with rational entries. A version of Farkas lemma implies that if the equation $$A\mathbf{x}=\...
- 6,214
1
vote
1
answer
133
views
Chebyshev approximation via iterated weighted least squares fits
I have the task of finding a Chebyshev approximation for a time-series; I want to check different types of functions, e.g. polynomials, rational functions, harmonics, etc.
I know that the Remez ...
- 13.2k
0
votes
0
answers
54
views
How to deal with minimizing a flat objective function
Problematic (Debiased Sinkhorn barycenter, proposed by H.Janti et al.): Let $\alpha_1, \ldots, \alpha_K \in \Delta_n$ and $\mathbf{K}=e^{-\frac{\mathrm{C}}{\varepsilon}}$. Let $\pi$ denote a sequence ...
- 121
1
vote
0
answers
59
views
Approximating a symmetric function in S(R) by Gaussians
The comments on this question point to a paper which demonstrates that the Gaussians $$E_b(x)=e^{-bx^2}$$ are dense in the even functions in $\mathcal{S}(\mathbb{R})$. I'm wondering if there's a nice ...
- 111
0
votes
0
answers
83
views
Interpolating points and orthogonal polynomials on varying intervals
In general, a Lebesgue-Stieltjes integral, $\int (\cdot) \, d \alpha(x)$, that defines an inner product on the space of polynomials establishes a notion of orthogonality.
Suppose we have a sequence of ...
- 13
1
vote
2
answers
156
views
Numerical evaluation of monomial divided differences
Suppose $f(x)=x^{n+1}$ for some $n\in\mathbb{N}$, and define the divided difference $$f[a,b]=\frac{a^{n+1}-b^{n+1}}{a-b}.$$
I am wondering about the best way to numerically evaluate $f[a,b]$ to high ...
- 45
1
vote
0
answers
99
views
Minimum of the maximum element frequency given the family size and the universe size
[Crossposted at math.stackexchange].
Consider families of sets $\mathcal{F}$ with size $n = |\mathcal{F}|$ and universe $U(\mathcal{F})$ with size $q = |U(\mathcal{F})|$.
I have written and solved ...
- 990
1
vote
1
answer
60
views
Does Monotone (linear) convergence of iterates imply monotone (linear) convergence of function values?
I am considering a proof that would require a certain connection between convergence of iterates and corresponding function values: Consider an algorithm with iterates $\left\{{\mathbf{x}}^k\right\}_{...
- 13
0
votes
0
answers
32
views
Finding measure representation for rank 2 moment matrices
Assuming the following equation has a solution, I'm interested in finding any concrete values of $x_{1},\dots x_{n},y_{1},\dots y_{n},c_{1},c_{2},R$ that fulfills it.
$$
\begin{bmatrix}
1 & 1 \\
...
- 275
3
votes
1
answer
122
views
Upper bound of $-r’’_\nu(x)/r’_\nu(x)$ where $r_\nu(x)=I_{\nu+1}(x)/I_\nu(x)$
Please see the bottom of the post for an updated version of the question.
Original Question. I’m looking for an analytical proof of an upper bound for $-r’’_\nu(x)/r’_\nu(x)$ for $\nu \ge 0$ and $x \...
- 31
0
votes
0
answers
101
views
Simulation of Markov processes with exponential timestepping
Let $(Y_t)_{t\ge0}$ be a time-homogeneous Markov process with transition semigroup $(\kappa_t)_{t\ge0}$. Numerical simulation of $(Y_t)_{t\ge0}$ can be done in the following way:
Choose an initial ...
- 167
0
votes
0
answers
115
views
Software for computing polytopes
As can be inferred from the title, I want to do some computation on the facets representation of the polytopes given the vertices. My advisor recommended me Polymake, which is indeed useful even with ...
- 1
0
votes
0
answers
72
views
Probability of being inside a convex n-dimensional polytop
I am currently conducting some post-grad research about wireless transmissions with uncertain transmission delays.
As part of the research, each individual transmission is modelled using a probability ...
6
votes
1
answer
234
views
Stopping criteria for damped Newton iterations with backtracking line search
Are there better criteria than the Armijo criterion for damped Newton iteration with backtracking line search, when the objective is standard self-concordant? (See Boyd and Vandenberghe.)
Let $F(x)$ ...
- 981
5
votes
1
answer
176
views
Efficient counting of integer solutions to linear system
In my research, I have a particular 18x18 matrix $\mathbf{A}$ which defines the linear system $\mathbf{A}\cdot \mathbf{x} \leq \mathbf{-1}$ over the nonnegative integers. And I'm interested in ...
- 151
0
votes
0
answers
30
views
Peak search for NLS equation solutions
By solving the initial value problem of the NLS equation, I can get a matrix of numerical solutions. I hope to perform a peak search on the matrix of this numerical solution, that is, there are ...
- 33
4
votes
1
answer
341
views
rank of an integer valued matrix
I make some numerical experiments, involving rank of integer valued matrices of the size about $14\times 24$. As the matrix is integer valued, theoretically there should be no room for errors. However ...
- 728
3
votes
1
answer
118
views
Restate equality between random variables in a numerical stable way
Let $X$ and $Y$ be two random variables drawn from two distinct normal distributions, $\mathcal{N} (\mu_X, \sigma_X^2)$ and $\mathcal{N} (\mu_Y, \sigma_Y^2)$, that correspond to the measurements of an ...
1
vote
0
answers
124
views
Can numerical differentiation be applied to tensor derivatives?
I know that for a 1D function, I can calculate the numerical derivative at every point, $\DeclareMathOperator{\d}{d\!} (x_1,y_1)$, with $\d y/\d x$ where $\d y = y_2 - y_0$ and $\d x = x_2 - x_0$. If ...
- 19
0
votes
0
answers
72
views
Initial guess in shifted QR algorithm
I'm comparing timings of two implementations of algorithms for the computation of Gauss-Legendre nodes.
1 - The first is a Newton algorithm to find the roots of the Gauss-Legendre polynomials. Quite ...
- 297
2
votes
0
answers
58
views
Is there any way to approximate a function based on a series of logarithm [closed]
Is there a way to expand a function in terms of logarithmic series? Like when we expand a function in terms of Taylor or Fourier series?
I tried to answer this question this way: Let's assume it can ...
- 21
0
votes
0
answers
49
views
Galerkin scheme in $H^s_0(G)\subset L^2(G)\subset H^{-s}(G)$ ($s>0$)
What basis functions are usually choosen if one attempts to conduct a Galerkin finite element method given an evolution triplet $H^s_0(G)\subset L^2(G)\subset H^{-s}(G)$. Where $G$ is a sufficiently ...
- 163
1
vote
0
answers
65
views
Discretization of oscillating integral
Suppose I am interested in computing
$$
I \equiv \int_0^B dx \, g(x) f(x)
$$
where $B$ is a known upper bound for the integral,
$g(x)$ is a known oscillating function and
$f(x)$ is a smooth function ...
- 33
0
votes
0
answers
136
views
Antiderivatives via Taylor series and the FT of Calculus
If $f$ is a real function on an interval $[a,b]$ such that
$f$ is computationally tractable on $[a,b]$: you can calculate $f(x)$ to $n$ bits of precision using an algorithm which is polynomial in $n$ ...
- 827
1
vote
0
answers
95
views
Vandermonde-type factorization of moment matrix?
Consider $n,d \in \mathbb{N}_{>0}$, there are many functions $y:\mathbb{N}^{n} \to \mathbb{R}$. Now for simplicity, we denote $y(\alpha)$ to be $y_{\alpha}$. Let $|\alpha| = \sum_{i=1}^{n}\alpha_{i}...
- 275
1
vote
0
answers
38
views
Formulation of multipoint constraints using Lagrange multipliers for a time dependent problem (with the Finite Element Method)
Intro
Suppose we have the following static linear equations (e.g. of an elastostatic problem):
$$\mathbf{K}\boldsymbol{u}=\boldsymbol{f}$$
We want a multipoint constraint of the type
$$\boldsymbol{\...
- 111
3
votes
1
answer
204
views
Converting an algebraic equation into a ODE
I'm working on a method to solve algebraic equations by converting them into ordinary differential equations (ODEs) and then integrating these ODEs over time.
Given an algebraic equation $f(x(t), t) = ...
- 31