All Questions
Tagged with sparse-matrix optimization
12 questions
0
votes
0
answers
25
views
Formulating an MRF as a graph weights matrix
I have a binary Markov random field (MRF) of an image:
$$E \left( B \right) = \sum_{i, j} L_{i, j}^{0} + \sum_{i, j} L_{i, j}^{1} + \sum_{i, j} \sum_{m, n \in \mathcal{N} ( i, j )} C (B_{i, j} , B_{m, ...
- 101
1
vote
2
answers
252
views
Are there good block sparse matrix solver libraries?
There are some great libraries with linear solvers for sparse matrices - SuiteSparse is the obvious one. The methods work on sparse matrices with scalar entries.
However, often in optimization ...
- 111
2
votes
0
answers
106
views
Parameter choice rules for L1 regularization?
I am solving an L1 regularized least squares of the form like:
$$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \lambda {\left\| \boldsymbol{x} \...
- 121
3
votes
1
answer
401
views
Nonlinear root solving libraries which accept a Jacobian in band-storage
I'm in search for a library for solving large systems of non-linear equations, similar to MINPACK, but unlike MINPACK, can accept a Jacobian in band-storage.
My Jacobian is sometimes not invertible, ...
- 317
2
votes
2
answers
223
views
L1 least squares minimization with a sparse matrix
I have the following problem:
$$\min_{x\in \mathbb{R}^n}\|Ax-b\|_1$$
where the matrix $A$ is large and sparse. I am looking for methods/code that can minimize this efficiently. References are very ...
- 2,872
0
votes
0
answers
86
views
Derivative-free ill-conditioned non-linear least squares
I am looking for a package which can solve (non-linear) least squares problems without the use of derivatives (because of an expensive model), but which also deals with ill-conditioning well (such as ...
- 131
4
votes
1
answer
914
views
Minimize a function with sparse Hessian
The problem I am trying to solve involves minimising a function with respect to a large number (probably 10,000+) of parameters. I can cheaply compute both its Jacobian and its Hessian. The Hessian is ...
- 161
3
votes
2
answers
457
views
Knapsack problem with fixed number of elements?
I am looking at an optimization problem that looks like this:
$$
\text{minimize}\;\; \mathbf{x}^TQ\mathbf x \;\;, \; \mathbf x \in \mathbb R^n, x_i \in \lbrace 0, 1 \rbrace\\
\text{subject to}\;\; ||...
- 189
1
vote
1
answer
355
views
Compressed sensing: $\ell_0$ "norm" vs $\ell_1$ norm
Suppose we have a very efficient way to perform $\ell_0$ "norm" compressed vs $\ell_1$ norm compressed sensing. Specifically, $\ell_0$ "norm" compressed sensing is
$$\eqalign{
& \min \quad {x^T}...
- 243
5
votes
0
answers
550
views
Optimisation of matrix exponential
I have a 7000x7000 sparse matrix (scipy), which I want to exponentiate. I've tried using scipy.sparse.linalg.expm, which works quite well for smaller matrices (takes a few seconds for a 1000x1000 ...
- 51
3
votes
1
answer
536
views
indirect method for least-squares with inequality constraints
I aim to find $x \in \mathbb{R}^n$ that
$\min_x |D \cdot F \cdot x|^2$
subject to $x_i = X_i$ and $x_j \geq X_j$ ,
$i \in I, j \in J$ and I and J partition ${1\cdots N}$ into two sets.
it is ...
- 251
0
votes
1
answer
314
views
Issues with solving large sparse linear equations
I have some issues solving sparse linear equations Ax = b
My matrix A is sparse with dimension of 5 million by 5 million. Actually, it is a combination of two matrices. One is tridiagonal and the ...
- 483