# Questions tagged [sparse-matrices]

The tag has no usage guidance.

64 questions
Filter by
Sorted by
Tagged with
245 views

### Usage and origin of the terms dictionary and atom in compressed sensing

In compressed sensing two terms or perhaps fancy word are frequently encountered. One is the dictionary and the other is atom. The dictionary is the matrix and its columns are called "atoms" ...
• 831
101 views

### Factorization to sparse matrices

$\newcommand{\lrank}{\operatorname{lrank}}$ $\newcommand{\rank}{\operatorname{rank}}$ Given a matrix $A$, we can define its Hamming weight, $w(A)$, as the number of non-zero elements in it. Now, given ...
• 3,029
32 views

### Conjugate gradient-like algorithm with multiple search directions

I am solving an $n*n$ system $Ax=b$ in CUDA where $A$ is a sparse matrix. Currently I am solving it using the conjugate gradient algorithm. I have noticed that $Ax$ where $x$ is $n*1$ has roughly the ...
• 71
168 views

### Expressing an invertible sparse matrix as a product of few elementary matrices

Let $M$ be an $n \times n$ matrix with integer entries. Suppose that $M$ is invertible (over the integers) and that $M$ has at most $An$ nonzero entries, each of which is less than $B$ in absolute ...
• 18.5k
1 vote
105 views

### How to numerically solve differential equations involving sines, cosines and inverses of the unknown function? [closed]

Crossposted at SciComp SE I'm very new to finite difference method and I am just introduced to methods of solving differential equation using finite difference method via sparse matrix method. I find ...
• 31
75 views

• 519
139 views

### "sparsifying" a binary (over the field F2) matrix

Assume I have a matrix $A \in GF(2)$, i.e., $A_{i,j} \in \{0, 1\}$ and the sum is modulo 2. Is there any known algorithms/methods to sparsify (reduce the number of non-zero entries) $A$ while keeping ...
• 183
143 views

### Random sparse and invertible matrices

Let $n\leq m$ and $0\leq k\leq (n\times m - \min\{n,m\})$ be in $\mathbb{N}$. Let $\mu$ be a probability measure dominated by the Lebesgue measure on $\mathbb{R}$ and generate a random $n\times m$ ...
• 5,079
1 vote
280 views

### Relation between the algebraic multiplicity of an eigenvalue and the subdiagonal elements of a symmetric tridiagonal matrix [closed]

Show that if $T$ is a symmetric tridiagonal matrix and an eigenvalue $\lambda$ has multiplicity $k$, then at least $k−1$ subdiagonal elements of $T$ are zero. If we consider a submatrix $B$ that has ...
141 views

### Algorithm to check a conjectural value for the rank of a large matrix

Feel free to suggest a different title, I'm not sure how to phrase this. I'm in the following somewhat specific situation: I'm checking a conjecture which at the end of the day boils down to the ...
• 8,454
107 views

### Approximate inverse of large sparse matrix

Given a large sparse matrix $M$, how to determine the existence of a good preconditioner? In other words, does there exist a sparse matrix $X$ such that $X M$ is close to the identity with respect to ...
135 views

### Jordan Decomposition of Sparse matrix

Suppose we are given $n \times n$ rational matrix, $A$ with at most $k$ nonzero elements in each row and each column with $k \ll n$. What is the best algorithm to compute its Jordan decomposition? ...
• 1,503
631 views

• 111
1 vote
381 views

### Decomposition of a Matrix by Sparse Matrices

Let $\mathbb{F}$ is a field. Consider an $n \times n$ matrix $\bf A$ over $\mathbb{F}$. $\bf A$ is called sparse matrix over $\mathbb{F}$ iff the number of non-zero entities of $\bf A$ be at most ...
• 211
141 views

### Spectrum of finite-band random matrices?

Let $X_n=(X_{ij})_{1 \leq i,j \leq n}$ such that : $$\begin{cases} &X_{ij} = 0 \quad \text{if}\quad \vert i - j \vert > k\\ & X_{ij} \sim P_X \quad \text{otherwise} \end{cases}$$ And ...
• 245
116 views

### Maximise singular value decay by sparse matrix approximation

I have a large matrix $A \in \mathbb{R}^{n \times m}$ and would like to subtract a sparse matrix $B \in \mathbb{R}^{n \times m}$ with less than $c (n+m)$ non-zero entries, where $c > 0$ is a ...
• 435
1 vote
345 views

### Matrix Sparsity Pattern

Suppose I have a matrix $H^{+} = (H^T H)^{-1} H^T$ where $H$ is a sparse matrix. Consider the case where only the sparsity pattern i.e. the zero elements of $H^{+}$ matrix is known, then would it be ...
• 11
1k views

### Square root of a large sparse symmetric positive definite matrix

I am trying to calculate $$Y = A^{\frac 12} X$$ where $A$ is a very large and sparse positive definite matrix, say, $10^4 \times 10^4$. Matrix $X$ is known and, say, $10^4 \times 100$. Is there any ...
• 83
1 vote
447 views

### Upper bound on the number of non-zero entries of the product of sparse matrices

I have two sparse matrices: $A$ of dimension $m \times k$ and $B$ of dimension $k \times n$. Is there a way to know how many non-zero entries there are in $C = A B$ without computing $A B$? I can ...
• 121
1 vote
144 views

• 143
93 views

### Maximal "all zeros" submatrix of a sparse binary matrix

Let $A\in\left\{ 0,1\right\} ^{M\times N}$, where each row of $A$ has at most $d$ components equal to $1$, and $d\leq M\ll N\ll Md$. Question: $\forall n\leq N$, what is $m\left(n\right)$, the ...
790 views

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

Given a dense matrix $A \in \mathbb{R}^{n \times m}$, with $n < m$, I am interested in finding a good approximation by choosing $s$ rows and zeroing the rest. This leads me to the following ...
• 194
320 views

### Solving linear system when one eigenvalue is known

I have a huge sparse linear system $Ax = b$ where I know that an eigenvalue/eigenvector pair is $1$ and a vector of all $1$'s. Can this knowledge help me in solving the linear system at all? It seems ...
• 123
292 views

### Finding high-dimensional correlation matrices that are both sparse and low-rank

Let $\boldsymbol{R}$ be the correlation matrix of $X_i,i=1,\dots,p$ with a large $p\gg q=\text{rank}(\boldsymbol{R})$. Is that reasonable to assume that $\boldsymbol{R}$ is both (approximately) sparse ...
• 193
2k views

### Decomposing a matrix into a product of sparse matrices

How to study the decomposition of a square matrix into a product of sparse matrices? There are no restrictions on the number of matrices in the product, but the fewer the better.
• 451
104 views

### Finding large bicliques in random bipartite graph

I want to find a $k$ by $r$ biclique hidden in an $M$ by $N$ random bipartite graph where edges are present with probability $p \in [0,1]$. I am specifically interested in $p \ll 1$, and large values ...
4k views

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

Given an $m$ by $n$ matrix $A$ I'm familiar with the standard method to compute a basis for the null space of $A$ by computing a QR factorization of $A^T$. If $A$ is large and sparse, we can use ...
1 vote
163 views

### Spectrum of a binary markov transition matrix

I would like to know if there are any special analytic expressions or fast numerical methods to get the spectrum for the transition matrix corresponding to a Markovian binary process (Bernoulli ...
• 291
1k views

### Efficiently compute the trace of a sparse matrix times the inverse of a sparse matrix?

How can I efficiently compute $\mathrm{trace}(A(B^{-1}))$ where $A$ and $B$ are both sparse symmetric PSD $n \times n$ matrices, both with $O(n)$ non-zero entries? If it helps, the pattern of non-...
• 500
437 views

### Can I find the gap between the two least eigenvalues of this special matrix A(t)?‎

I am interested in finding the gap between the two least eigenvalues of $A(t)$, a Hermitian $N\times N$ sparse ‎matrix whose diagonal elements are $a_it+b_i\,(1\leq i\leq N)$, and all off-diagonal non-...
• 103
259 views

### Decomposing large symmetric banded sparse matrices

I'm investigating 3D image deblurring and one of the approaches I'm interested in is applying spatial regularisation. To do this I have generated a matrix $A$ which encodes the 6-connectivity of each ...
1 vote
265 views

### Asymptotic eigenvalue analysis for a sparse random matrix

We have an asymptotic analysis problem for the eigenvalue performance of the following random matrix: $H=\{h_{ij}\}_{N_r\times N_t}$, where each entry $h_{ij}$ is with a probability $p$ to obey the ...
231 views

### Hamiltonicity criteria for sparse graphs

Given a sparse graph, how can one go about proving that it is Hamiltonian? (Assuming it actually is, of course). There are three main classes of criteria for Hamiltonicity that I am aware of: Dirac-...
• 6,922
1 vote
637 views

### Estimate the determinant of sparse 0-1 matrix

There is a matrix A where each entry is either 0 or 1. Each column has exactly a 1's and each row has at most b 1's. What's the upper bound of abs(|A|)? The condition is stronger than the Hadamard's ...
• 245