Skip to main content
11 votes
Accepted

What does LSQR stand for

You’re right, the name is not explained anywhere, but there is some logic behind it. When Chris Paige visited Stanford in 1972, we started several methods that needed names. LSQR means that it’s for ...
Michael Saunders's user avatar
9 votes
Accepted

Solve this specific large sparse system of linear equations

The key is the fact that $C_i = - I$, i.e., the appropriately size identity matrix is trivially nonsingular and can be used to nullify the blocks above each copy. We have the following row equivalence ...
Carl Christian's user avatar
7 votes
Accepted

Sparsest similar matrix

The companion matrix to the polynomial $(x^2-1)^2=1-2x^2+x^4$ is $$\pmatrix{0&0&0&-1\cr1&0&0&0\cr0&1&0&2\cr0&0&1&0\cr}$$ which has Jordan form $$\...
Gerry Myerson's user avatar
5 votes

General formula for $f(n)$

$\newenvironment{vsmatrix}{\left|\begin{smallmatrix}}{\end{smallmatrix}\right|}\def\mycolor#1{{\color{blue}#1}}$Denote by $D_n$ the determinant of the $2n × 2n$ matrix to be solved with $2$ replaced ...
Ѕᴀᴀᴅ's user avatar
  • 34.4k
5 votes

Sparse PCA vs Orthogonal Matching Pursuit

The image of $x^T \Sigma x$ for $x\in B[0,1]$ is an ellipsoid. PCA would try to find the largest length of that ellipsoid. Sparse PCA is trying to see how close you can get to that longest length ...
NicNic8's user avatar
  • 7,032
4 votes
Accepted

What Is the Quickest Method to Solve $ A x = b $ for $ A $ Being Sparse Semi Definite Positive Matrix?

The answer depends on properties of the matrix $ A $. For large matrices sometimes iterative methods are faster than direct methods (Which is what behind \). Try ...
Royi's user avatar
  • 8,829
4 votes
Accepted

How does the Lanczos iteration find small eigenvalues?

Unsurprisingly, Golub and van Loan (3rd ed.) had an answer. In chapter 9, they present this justification: Consider an initial set of vectors $\{q_1,...,q_{k-1}\}$, and consider the optimal vector to ...
Zach Boyd's user avatar
  • 908
4 votes
Accepted

Is $det(A)=0$ a good indicator to say that a matrix is not invertible?

The determinant is takes a long time to compute for large matrices. A better way is to look for the smallest singular values of your matrix. If they are 0 or close to machine precision, then it is ...
whpowell96's user avatar
  • 6,199
4 votes
Accepted

Find a sparse surrogate matrix that performs as good as the original one

While describing an optimization algorithm for a relaxed version of this problem, I think I found a simple analytical solution for the original problem. I'll assume $x \neq 0$. Notice that none of ...
littleO's user avatar
  • 52.3k
3 votes
Accepted

"Pivot step" that Donald Knuth mentioned in TAOCP

This special "pivot" step consists of a row scaling with $a^{-1}$ and a linear update adding $-c$ times the new top row to the bottom row. This second operation would normally create a zero in the ...
Carl Christian's user avatar
3 votes
Accepted

What is a sparse vector and which role does the $l_0$ norm play?

As far as I know 0-norm, just counts the number of nonzero entries. Thus for a vector $v = (v_1,...,v_n)$ we would have that $\|v\|_0 = \sum_{v_i\neq 0}1 = \#$ of non-zero $v_i$. Note: Some authors ...
Owen Sizemore's user avatar
3 votes
Accepted

How do I invert this sparse lower triangular matrix

Let $T^{-1}=B$. Forward substitution gives $B_{i\ast}=e_i^T+B_{k(i)\ast}$. That is, the $i$-th row of $B$ is basically identical to the $k(i)$-th row, except that $b_{ii}$ is also equal to $1$. Put it ...
user1551's user avatar
  • 141k
3 votes
Accepted

Multiplying sparse matrices

It cannot be k+j as it can be seen in the next counterexample: We define k = 3 and j = 2 and create the next two matrices, with dimension that agree for the multiplication as you stated: $A=\left( \...
Josu Etxezarreta Martinez's user avatar
3 votes
Accepted

Generating a random sparse hermitian matrix in Python

This generates a random mask with of a given size n and density dens, you just need to apply it to a dense matrix of your choice ...
caverac's user avatar
  • 19.4k
3 votes

Solve this specific large sparse system of linear equations

You could try formulating it as a feasibility optimization problem such as $$\begin{equation} \begin{array}{rrclcl} \displaystyle \min_{x} &0 \\ \textrm{s.t.} & A x & = & b \\ \end{...
YukiJ's user avatar
  • 2,549
3 votes
Accepted

Diagonalization of very large (but very simple) sparse matrix

As $A$ is symmetric, we have $\max|\lambda_i|=\|A\|_2$ and $\|A\|_1 = \|A\|_{\infty}.$ Furthermore $\|A\|_2 \leq \sqrt{\|A\|_1\|A\|_{\infty}}$, see here. If we put all this together, we get an easy-to-...
Reinhard Meier's user avatar
3 votes

Diagonalization of very large (but very simple) sparse matrix

You can use Gershgorin Circle Theorem to get a lower bound $\lambda_{GCT}$ for $\lambda_{min}$ and then use that as a starting point for inverse iteration (https://en.wikipedia.org/wiki/...
JCK's user avatar
  • 104
3 votes
Accepted

Relationship between matrices whose singular values are the same

So, if they are just close but not exactly the same, I am not so sure there is much that we can say. However, for the purpose of exploration suppose that the singular values of both matrices are the ...
Ariel's user avatar
  • 370
3 votes

Eigenvalues of a sparse 8x8 matrix

Since $P^3=\frac18ee^T$, $1$ is a simple eigenvalue of $P$ and $0$ is an eigenvalue of algebraic multiplicity $7$.
user1551's user avatar
  • 141k
3 votes

Sparse Cholesky decomposition of factorized matrix

You'll find the LSQR as an option for solving large sparse linear systems that max be over or under determined. This is included in scipy.sparse.linalg.lsqr. ...
Mikael Öhman's user avatar
2 votes
Accepted

Choosing $\lambda$ to yield sparse solution

It's not hard to show (Hint: show that the dual problem is a projection of $\frac{1}{\lambda}(Ax_0 + z)$ onto the polyhedron $\mathcal P := \{\theta \text{ s.t }\|A^T\theta\|_\infty \le 1\}$, and then ...
dohmatob's user avatar
  • 9,565
2 votes
Accepted

What techniques are useful for solving this sparse symmetric matrix?

You want the Tridiagonal matrix algorithm, also known as the Thomas algorithm.
Robert Israel's user avatar
2 votes
Accepted

Diagonal approximation of the inverse of a sparse matrix

If $\Omega\Sigma = I + E$, with $\|E\|$ small, then $\Sigma^{-1}\Omega^{-1} \approx I - E$, and $\Sigma-\Omega^{-1} \approx \Sigma E$, thus $\|\Sigma-\Omega^{-1}\| \approx \|\Sigma\| \|E\|$. Since $\...
Pawel Kowal's user avatar
  • 2,252
2 votes
Accepted

Can someone explain the role of sparsity in optimization?

In many problems there are a large number of variables and constraints, but each constraint will only involve a small number of variables. Therefore nearly all of the entries of the coefficient ...
Robert Israel's user avatar
2 votes
Accepted

How to Mathematically Recover Sparse Signal (Least Squares with $ {L}_{1} $ Regularization - LASSO)?

The simplest way to solve this is using Sub Gradient Method (Generalizes the Gradient Method). A valid Sub Graidnet of the $ {L}_{1} $ Norm is given by the $ \operatorname{sign} \left( \cdot \right) $...
Royi's user avatar
  • 8,829
2 votes

What is a sparse vector and which role does the $l_0$ norm play?

A sparse vector is a vector of big dimension (e.g., $x\in\mathbb{R}^n$ for large $n$), but with only very few non-zero coordinates. ("Morally $n$, actually $k$ coordinates.") That's what the $\ell_0$ ...
Clement C.'s user avatar
  • 67.5k
2 votes

compressive sensing

The compressive sensing theory basically says, a signal can be (even fully perhaps) recovered even when it is extremely under-sampled. Normally, it is an inverse problem, meaning that if you have a ...
Nick X Tsui's user avatar
2 votes
Accepted

Making a matrix as sparse as possible

You can pose the following optimization problem: $$min_{C,B} \quad \|C\|_1 \qquad \text{s.t. } \quad C = BA.$$ An easy way to solve this problem is the ADMM approach. In summary, you add the augmented ...
abolfazl's user avatar
  • 575

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