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$. ...
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: $|\...
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 (...
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 ...
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 ...
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 ...
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, ...
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 ...
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).
$^...
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 ...
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 \...
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. ...
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}=...
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&...
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 ...
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 \...
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 ...
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.
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\...
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 ...
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/...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
sparse-matrices × 61linear-algebra × 25
matrices × 23
numerical-linear-algebra × 12
pr.probability × 7
random-matrices × 7
eigenvalues × 7
co.combinatorics × 5
matrix-theory × 5
na.numerical-analysis × 4
oc.optimization-and-control × 4
matrix-analysis × 4
graph-theory × 3
algorithms × 3
finite-fields × 3
reference-request × 2
convex-optimization × 2
linear-programming × 2
eigenvector × 2
hamiltonian-graphs × 2
numerical-analysis-of-pde × 2
compressed-sensing × 2
mg.metric-geometry × 1
ra.rings-and-algebras × 1
mp.mathematical-physics × 1