6 votes
Accepted

How can one construct a sparse null space basis using recursive LU decomposition?

On the LUQ decomposition The algorithm implemented in luq (see reference given below) computes bases for the left/right null spaces of a sparse matrix $A$. ...
Nawaf Bou-Rabee's user avatar
5 votes
Accepted

In a large sparse matrix, how many eigenvalues/eigenvectors are “spurious”?

Antisymmetric matrices are normal, hence they can be diagonalized with an orthogonal matrix. So $\|A\|_F^2=\sum |\lambda_i|^2$. If you keep only the $k$ largest eigenvalues (ordered in modulus: $|\...
Federico Poloni's user avatar
4 votes
Accepted

Square root of a large sparse symmetric positive definite matrix

I completely agree with fedja: there is a nice method here (which, unfortunately, does not always work well). If you know bounds for the spectrum of $A$, say $0<a<\lambda<b$, then you (...
Alex Gavrilov's user avatar
4 votes
Accepted

Solving linear system when one eigenvalue is known

Yes and no. If you modify slightly the implementation of a Krylov subspace method such as GMRES, you can construct a method with a projection subspace that contains the known eigenvector. This ...
Federico Poloni's user avatar
4 votes

How can one construct a sparse null space basis using recursive LU decomposition?

Not the same algorithm, but here is an alternative that I have used in a recent paper; you can put it together quickly with standard Matlab functions if $A$ is a $m\times n$ matrix with $m\ll n$ (like ...
Federico Poloni's user avatar
3 votes

Decomposing a matrix into a product of sparse matrices

The question of deciding if a specific matrix is a product of "a few" "sparse" matrices seems very interesting to me and perhaps rather hard. Likewise the question of how bad things could be if the ...
Aaron Meyerowitz's user avatar
3 votes

Expected spectral radius for a sparse Erdős-Rényi binary matrix with a certain density

If you mean that $A$ is the adjacency matrix of an Erdos-Renyi random graph, then the question has been studied, and your conjecture is false (but just barely). See Krivelevich, Michael; Sudakov, ...
Igor Rivin's user avatar
  • 95.6k
3 votes

Decomposition of rectangular matrices into a product of a sparse and a small matrices

I do not know yet how to solve your question, but there is a similar question with the same difficulty that allows a nice solution. Note that you are basically asking whether we can efficiently find a ...
fedja's user avatar
  • 59.5k
3 votes
Accepted

Parametrising a sparse orthogonal matrix

The smallest number of nonzero entries in an $n\times n$ fully indecomposable$^*$ orthogonal matrix is $4n−4$. A method to construct such a matrix is described in Sparse orthogonal matrices (2003). $^...
Carlo Beenakker's user avatar
3 votes

Parametrising a sparse orthogonal matrix

The four-argument version of Matlab's sprand can generate a sparse orthogonal matrix, with suitable arguments. According to the documentation, [the matrix] is ...
Federico Poloni's user avatar
2 votes

LASSO problem but with a maximization instead of minimization

That problem does not have a maximum. Unless $A$ or $k$ are zero, you can take $\alpha = Me_j$, where $e_j$ is a vector of the canonical basis, and then the objective function diverges when $M \to \...
Federico Poloni's user avatar
2 votes

Existence of sparse LU decomposition of sparse matrix

It seems that the answer is that with high probability, a random sparse matrix (for an appropriate choice of probability distribution over matrices) does not have a sparse decomposition in this sense. ...
Matt Hastings's user avatar
1 vote

Relation between the algebraic multiplicity of an eigenvalue and the subdiagonal elements of a symmetric tridiagonal matrix

The most natural explanation for this (in my view) lies in the fact that the eigenvectors of such a matrix solve a difference equation. More precisely, if we write $T_{nn}=b_n$, $T_{n,n+1}=T_{n+1,n}=...
Christian Remling's user avatar
1 vote
Accepted

Probability of accurate sparse recovery

A good starting point is "Mathematics of sparsity (and a few other things)" by E. Candes, or a book on compressed sensing such as "A Mathematical Introduction to Compressive Sensing&...
jlewk's user avatar
  • 1,344
1 vote
Accepted

How sparse can a matrix mapping between sparse vectors be?

$||v||_0$, so $\leq d-s$: The matrix $A$ needs to have at least one entry for every entry of $v$ (otherwise it can't obtain that entry). It is also sufficient to have so many entries, as if we ...
Bastian Seifert's user avatar
1 vote

Covering number in the space of symmetric matrices

One answer for the second case. We can see that we have to look at (for $k \in \mathbb{N}$): \begin{equation} \mathcal{M}=\{\Theta \in S_n^{++}(\mathbb{R})| \ \|\Theta\|_0 \leq n +2k, \|\Theta\|_F \...
Titouan Vayer's user avatar
1 vote
Accepted

What is the big-O complexity of solving the sparse Laplace equation in the plane?

I'm not sure if this is the final answer, but this paper claims that $O(n^{1.5})$ FLOPS with $O(n\log n)$ storage, is best possible across all possible reorderings of the rows and columns of $A$. This ...
Sébastien Loisel's user avatar
1 vote

Sparse, left-looking LU factorization

I was confused -- the algorithm does not produce sorted columns, only topologically sorted ones. To obtain a bona fide matrix, one must use e.g. the trick of transposing it twice.
grok's user avatar
  • 2,489
1 vote

Spectrum of finite-band random matrices?

Yes, convergence to a limiting empirical measure $\mu_\infty$ is well known . Let $L\in \mathbb{N}$, (we will chose $1\ll L \ll n$) and define $Y$ $$Y_{i,j}=\begin{cases}X_{i,j} \text{ if } \exists k\...
RaphaelB4's user avatar
  • 4,296
1 vote

Sparse matrix approximation using only a few dense columns (or rows)

Since this is getting bumped to the home page, I'll turn my comment into an answer. We have $$\|A-A_I\|^2_F = \sum_{i \not \in I} \|a_i\|^2,$$ where $a_i$ are the rows of $A$, so it is clear that ...
Federico Poloni's user avatar
1 vote

Exponential of large matrices

I've done 11kx11k matrices in Python with scipy's sparse matrix exponential function in tens of seconds: https://docs.scipy.org/...
Stanley Bak's user avatar

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