# Questions tagged [sparse-matrices]

The sparse-matrices tag has no usage guidance.

59
questions

0
votes

1
answer

37
views

### How sparse can a matrix mapping between sparse vectors be?

Let $s$ and $d$ be non-negative integers with $0\leq s<d$ and let $v,u\in \mathbb{R}^d$ be vectors satisfying the sparsity estimate
$$
\max\{\|u\|_0,\|v\|_0\}\leq d-s,
$$
where, as usual, for any ...

0
votes

0
answers

17
views

### iterative linear solver with multiple starting vectors

Suppose I want to solve a (huge, sparse, self-adjoint) linear problem $Ax=b$ in a "matrix-free" form (i.e. without making components of $A$ explicit, just providing a function that computes $...

1
vote

1
answer

136
views

### Covering number in the space of symmetric matrices

Let $S_n(\mathbb{R})$ be the set of symmetric matrices of size $n \times n$. Note $\|\Theta\|_{0}$ the number of nonzero elements of a matrix $\Theta$ and $\|\cdot\|_F$ the Froebenius norm. Consider ...

1
vote

0
answers

40
views

### Size of PD matrices with sparse inverse

Let $S_{n}^{++}(\mathbb{R})$ be the set of strictly positive definite (PD) matrices on $\mathbb{R}$. We say that a matrix is $k$ sparse if it has at most $k$ nonzero elements.
Can we somehow ...

0
votes

0
answers

57
views

### Number of edges in bipartite graphs

Let $G$ be a bipartite graph on $n$ vertices of either color.
Suppose $G$ contains no perfect matching the number of edges can be $\Omega(n^2)$ (just do not place an edge between a particular pair of ...

2
votes

0
answers

66
views

### Volume and basis for integer lattice subject to sparse constraint

Let $k<n$ be integers. Let $A\in \mathbb{Z}^{k \times n}$ be a sparse matrix, meaning that the number of nonzero entries in every row and every column is at most $O(1)$. Further, assume that ...

6
votes

1
answer

144
views

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

In MATLAB, you can get a 2d Laplacian via A = delsq(numgrid('S',N)); yielding a matrix $A$ that is $n \times n$ with $n = O(N^2)$, for a square domain discretized ...

10
votes

2
answers

381
views

### Existence of sparse LU decomposition of sparse matrix

Let $A$ be a sparse matrix over some field. I would like to know about the existence of LU decompositions so that $L,U$ are both sparse.
More precisely, let $A$ be an $N$-by-$N$ matrix. Suppose each ...

1
vote

0
answers

49
views

### A packing ball problem: verify lower bound on Gaussian width of sparse ball

Note: This should be a geometry problem about packing balls. All the necessary probability pre-requisite is given below.
Consider a set of sparse vectors: $T_{n,s}:=\{x\in \mathbb{R}^n:\|x\|_0 \le s, \...

2
votes

0
answers

79
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 ...

2
votes

0
answers

107
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$ ...

1
vote

1
answer

141
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 ...

6
votes

0
answers

130
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 ...

3
votes

0
answers

84
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 ...

0
votes

0
answers

101
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? ...

2
votes

2
answers

368
views

### Parametrising a sparse orthogonal matrix

I need to find a way to parametrise a matrix that is both sparse (to some degree) and orthogonal, i.e., I am looking for a parametrisation that describes $A \in \mathbb{R}^{n\times m}$ such that $AA^𝑇...

1
vote

0
answers

120
views

### Algorithm to find "islands" in sparse matrices

I am playing with a weird dataset of ternary images (+1,0,-1 values only) which happen to be very sparse (avg. > 90%). I would like to determine the most relevant "islands" (or should I call them ...

1
vote

1
answer

307
views

### Sparse, left-looking LU factorization

I'm trying to understand the left-looking LU factorization algorithm for sparse matrices, by reading T.A. Davis' book, and have trouble in one step (sorry for the specific question) about returning ...

3
votes

0
answers

109
views

### Sparsest similar matrix

Given a square matrix A (say with complex entries), which is the sparsest matrix which is similar to A?
I guess it has to be its Jordan normal form but I am not sure.
Remarks:
A matrix is sparser ...

1
vote

1
answer

98
views

### LASSO problem but with a maximization instead of minimization

I have the following optimization problem (like the LASSO problem but with maximization instead of minimization):
$\mathbf{maximize}_{\boldsymbol{\alpha}} \|\mathbf{x} -\mathbf{A}\boldsymbol{\alpha}\|...

1
vote

0
answers

323
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 ...

2
votes

2
answers

118
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 ...

2
votes

1
answer

95
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 ...

1
vote

0
answers

287
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 ...

7
votes

1
answer

733
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 ...

1
vote

1
answer

315
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 ...

1
vote

0
answers

111
views

### Properties of graphs with Hankel-like adjacency matrix

I am having undirected graphs with adjacency matrices which have a regular Hankel-like form, e.g.,
$$A=\begin{pmatrix}0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & (6\times 0 \text{ ...

3
votes

1
answer

219
views

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

Let $A$ be an $n \times n$ sparse matrix generated via the Erdős-Rényi method. Here, "sparse" means that $\|A\|_F = O(n)$. I am interested in the relationship between the expectation $\mathbb E(\rho(A)...

2
votes

1
answer

210
views

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

I would like to construct a rectangular matrix which doesn't have a decomposition into a product of a sparse and a small matrices. It is easy to see that a random matrix doesn't have such a ...

5
votes

1
answer

985
views

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

In a large (possibly above $5000\times 5000$) matrix, the problem of finding all the eigenvalues and eigenvectors can be solved using iterative methods (Arnoldi, Lanczos etc.). However, there seems to ...

6
votes

0
answers

263
views

### Upper bound for $\|\textbf{D}^{-1}\|$, where $\textbf{D}$ is a matrix with specific sparse pattern

Consider the block matrix given by
$$\textbf{D} = \left[
\begin{array}{ccc}
\left[
\begin{array}{ccc}
D & \ldots & D\\
\vdots & \ddots & \vdots\\
D &...

2
votes

0
answers

89
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 ...

3
votes

2
answers

599
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 ...

2
votes

2
answers

194
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 ...

4
votes

1
answer

264
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 ...

5
votes

2
answers

1k
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.

3
votes

0
answers

88
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 ...

8
votes

2
answers

3k
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

0
answers

151
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 ...

8
votes

1
answer

877
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-...

7
votes

1
answer

396
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-...

3
votes

1
answer

224
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

1
answer

232
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 ...

6
votes

1
answer

192
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-...

1
vote

1
answer

491
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 ...

1
vote

1
answer

113
views

### Transform $a\mathbf x+\mathbf b$, then make it $k$-sparse, resulting least modification?

Consider vector $\mathbf x = (x_1,x_2,\cdots,x_n)$, $a$ a scalar, $\mathbf b = (b_0,\cdots,b_0)$ and $k < n$.
I want to transform $\mathbf x$ ($\mathbf y = a\mathbf x+\mathbf b$) such that if I ...

2
votes

0
answers

529
views

### Inverse of sparse matrix is not generally sparse [closed]

I have a question regarding inverse of square sparse matrices(or can be restricted to real symmetric positive definite matrices).
I encountered several times the web pages which states that the ...

4
votes

2
answers

1k
views

### probability of having linearly independent sparse vectors over finite fields

Suppose that there are $i< N$ linearly independent $N$-dimensional vectors $\mathbf{v}_1,\mathbf{v}_2,\ldots,\mathbf{v}_i$ over a finite field $\mathbb{F}_q$, whose elements are denoted as $\{0,1,2,...

1
vote

1
answer

527
views

### sparse binary vector

I want to know if the following problem has been solved
max_w w'Rw
where the entries of the vector w are binary (w_i= {0,1} )

0
votes

1
answer

487
views

### $\ell_o$ Minimization (Minimizing the support of a vector)

I have been looking into the problem
$\min: \|x \|_0$ subject to$: Ax=b$. $\|x \|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current form. Most of my time ...