# Tag Info

4

If you have a good LP solver, then the linear programming approach often works well. You don’t want to implement your own simplex or interior point code for LP though. A specialized variant of the simplex method due to Barrodale and Roberts is a popular approach to this problem, but it takes some effort to implement this efficiently and you might be better ...

3

That might also have been a trick question. Let's say you want to solve the normal equations for $Ax=b$, i.e., $(A^T A) x = A^T b$. Let's assume for a moment that the questioner meant that $A$ is actually already stored in memory, so we know that that much memory is already available. Let's also assume that $A$ is tall and narrow (more specifically, has ...

2

The problem ended up being elsewhere in the code with complete working solution posted here: ## Python adaptation of optimization routine as conceptualized by Markus Piro circa 2014. import matplotlib.pyplot as plt import pandas as pd import numpy as np np.random.seed(42) ## function to test against beta_true = np.array([5, 33, -1e4]) def test(x, beta): ...

2

TL;DR For an image of size $m\times n$ you can solve this problem in $O(nm(\log(n) + \log(m)))$. In fact, there is nothing to "solve", the solution can be written down analytically. The differencing operator is linear space invariant, i.e. a convolution, and you are asking how to do a "de-convolution". This can be done efficiently in the ...

2

Thanks to Wolfgang Bangerth for pointing out that this can be rewritten as a linear problem. My reformulation would be: $$\min_{x\in\mathbb{R}^N}\|Ax-b\|_1 \implies$$ $$\min_{(x,y)\in\mathbb{R}^{N+M}}\sum_{i=1}^N y_i,$$ $$Ax - y \leq b$$ $$-(Ax+y) \leq -b$$ $$y\geq0$$

2

Ok, now it's too long for a comment, so I can try to answer your question right away. Let's write your matrix $DF$ as $D+F$ where $D$ is a matrix with only the last row filled with unknowns and $F$ has as only non-zero entries ones on the first subdiagonal. Then your equation becomes $$z^{k+1} = (D + F) z^{k}\\ \rightarrow z^{k+1} - F z^{k} = D z^{k}$$ ...

1

Among approximate techniques: Gradient descent should do a decent job, given the limitations. Randomized SVD is an effective technique. It is quick to implement, and there are ready-to-use error bounds (see e.g. https://doi.org/10.1137/090771806 for a review of that area). Among techniques that produce an exact solution: There is research on out-of-core ...

1

So called “matrix free” methods, relying primarily on the ability to perform multiplication of the matrix by a vector, lend themselves nicely to iterative techniques such as GMRES. The matrix itself might be on disk, but portions retrieved selectively to compute the necessary matrix-vector products.

Only top voted, non community-wiki answers of a minimum length are eligible