Questions tagged [na.numerical-analysis]

19 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10 votes
0 answers
101 views

Complexity of checking $a > br^m + cr^n$, with $r$ rational

I'm wondering if the following problem is decidable in P-time (or even NP): Given $a, b, c \in \mathbb{Z}$ and $m, n, p, q \in \mathbb{N}$ all in binary, decide if $a > br^m + cr^n$, where $r = {p ...
Michaël Cadilhac's user avatar
8 votes
0 answers
367 views

Efficiently approximating derivative of a well-behaved function

I need an algorithm for adaptive sampling a well-behaved function and computing its derivative in the sampling range with prescribed accuracy. The function has no more than one minimum in the sampling ...
Alexey Popkov's user avatar
7 votes
0 answers
129 views

What's the state of the art for matrix nuclear/trace norm optimization

I am interested in simple matrix optimizations with nuclear/trace norm: $\min_X \left(f(X) + \|X\|_*\right)$ where $\|X\|_*$ stands for the trace norm of the matrix $X$, and $f$ is a convex smooth ...
Jonathan's user avatar
7 votes
0 answers
140 views

What's new in sparse eigensystems solution

As a part of other work I need to solve relatively large (~1E5x1E5) and sparse (~100 non-zero elements in each raw in few blocks) hermitian eigensystems. Usually only few eigenvalues+vectors are ...
Misha's user avatar
  • 171
4 votes
0 answers
51 views

Error analysis of Estrin's method

Estrin's Method is an alternative to Horner's method for evaluating polynomials. To evaluate a polynomial $P(x)=\sum_{i=0}^7 a_i x^i$ at a point $x\in\mathbb R$, it first computes the powers $x^2$ and ...
Thomas Ahle's user avatar
3 votes
0 answers
77 views

Monotonic and bounded sequences throughout computer science

When I refer to the Monotone Convergence Theorem below, I refer to the very simple claim that if a non-decreasing sequence has an upper bound then it converges. I don't refer to the claim from Measure ...
wlad's user avatar
  • 303
3 votes
0 answers
874 views

Is there any algorithm to find just the largest eigenvalue with subquadratic time complexity?

SVD or PCA can be used find the largest eigenvalue, but at a cost of $O(n^3)$ complexity. Lanczos algorithm runs much faster on a sparse matrix with complexity $O(dn^2)$ where $d$ is the average ...
River's user avatar
  • 131
3 votes
0 answers
80 views

Efficiently Detecting "edges" in the time frequency plane

Given a signal $y(t)\in\mathbb{R}$ I wish to detect edge patterns. $s(f,t)$ is a time-frequency decomposition of $y(t)$ in some window $(t-n,t+n)$ so that $f$ loosely corresponds to a local frequency....
Mark S's user avatar
  • 131
2 votes
0 answers
101 views

Inverting a sum of easy to invert linear terms?

Below are some examples of linear equations with $d\times d$ matrices $Y,A,B,C,D$ which can be solved for unknown $d\times d$ matrix $X$ in $O(d^3)$ time. Repeated indices in each term are summed over:...
Yaroslav Bulatov's user avatar
2 votes
0 answers
704 views

the confusion about 'with high probability (w.h.p.)'

w.h.p. can often be seen in the analysis of randomized algorithms. It's definition can be seen here https://en.wikipedia.org/wiki/With_high_probability. However my confusion is that: Assuming we ...
olivia's user avatar
  • 179
1 vote
0 answers
36 views

What is the complexity of the "characteristic bisection" method?

The characteristic bisection method is an algorithm for finding approximate zeros of multi-dimensional functions. It is a generalization of the bisection method; it is described briefly here. ...
Erel Segal-Halevi's user avatar
1 vote
0 answers
34 views

Interval arithmetic adapted to backwards stable problems

In numerical analysis, there are algorithms which are either forwards stable or backwards stable. Forwards stability is strictly stronger, and is more desirable. Unfortunately, it is in many instances ...
wlad's user avatar
  • 303
1 vote
0 answers
70 views

Smallest nonzero eigenvalue of a sum of +1/-1 rank-one matrices?

Suppose we have a $k\times k$ matrix $A = \sum_{i=1}^{n} a_i a_i^T$ where $n \leq \mathrm{poly}(k)$ and each $a_i\in\{-1,1\}^{k}$. It is easy to prove that the largest eigenvalue of $A$ is at most $\...
Octopus's user avatar
  • 31
1 vote
0 answers
1k views

How can I understand the Coppersmith–Winograd algorithm?

I want to do research on matrix multiplication algorithms. I glanced at the Coppersmith-Winograd algorithm paper, but I didn't understand anything. How can I complete the background to read this paper?...
Huseyin Okan Demir's user avatar
1 vote
0 answers
95 views

Complexity of low-rank matrix factorizations with rows in a simplex and outliers

Our goal is to obtain a matrix factorization in form of $M = U V'$, where $U\in\mathbb{R}^{d\times r}, V \in\mathbb{R}^{N\times r}$ and each row of $V$ satisfies $$ \sum_{j}(V)_{ij}=1, (V)_{ij}\ge 0 $$...
Yufeng Zhang's user avatar
1 vote
0 answers
118 views

Computing log of sum of positive integers

As input, we are give $k$-bit approximation (after the decimal point) of $\log(a)$ and $\log(b)$ for positive integers $a$ and $b$, i.e, we are given $\alpha$ and $\beta$ (as binary strings) as input ...
Gorav Jindal's user avatar
1 vote
0 answers
60 views

Computational complexity of Initial Value Problems of ODEs

Are there known results on computational complexity of initial value problems of ODEs? As my question may be somewhat vague, I want to mention that I'm mainly interested for results on the ...
Kapoios's user avatar
  • 161
1 vote
0 answers
129 views

High Dimensional Volume (HDV) estimator for Entropy estimation

I am writing a program using high-dimensional volume (HDV) estimator to estimate entropy and mutual information for variable selection. Let $ D = (x^i_1, x^i_2, ..., x^i_M)$, N is the number of data ...
JYJ's user avatar
  • 11
0 votes
0 answers
113 views

Complexity of, given any elementary function $f$ and a natural $n$, compute $n$ digits of $f(x)$

We define problem $A$ as follows. Each instance of the problem consists of: (a) some succinct codification of an elementary function, that is, a function constructed by composing arithmetic operators, ...
EXPTIME-complete's user avatar