Questions tagged [sparse-matrices]
The sparse-matrices tag has no usage guidance.
64 questions
2
votes
1
answer
260
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" ...
- 879
6
votes
0
answers
111
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,319
0
votes
0
answers
36
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
6
votes
0
answers
187
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.7k
1
vote
1
answer
106
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
0
votes
1
answer
80
views
Probability of accurate sparse recovery
Suppose $\mathbf{A}_{k\times n}$ ($k<n$) is a matrix whose entries are generated i.i.d. from Gaussian distribution and $\mathbf{s}_{n\times 1}$ is a sparse vector with $m$ sparsity (i.e., $\|\...
- 287
2
votes
0
answers
27
views
Solve sparse system with nested inverse
What is the most efficient way to solve an equation
\begin{align*}
(A\,E^{-1}\,C) x = b, \qquad A\in \mathbb{R}^{m\times n}, \, E \in \mathbb{R}^{n\times n}, \, C\in \mathbb{R}^{n\times m}
\end{align*}...
- 21
0
votes
1
answer
42
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 ...
- 5,407
1
vote
1
answer
428
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 ...
- 407
1
vote
0
answers
48
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 ...
- 407
3
votes
0
answers
91
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 ...
- 547
6
votes
1
answer
762
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 ...
- 981
11
votes
2
answers
1k
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 ...
- 547
1
vote
0
answers
126
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, \...
- 519
5
votes
0
answers
155
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
2
votes
0
answers
149
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,407
1
vote
1
answer
308
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
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,524
3
votes
0
answers
111
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 ...
- 31
0
votes
0
answers
142
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
3
votes
2
answers
674
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^𝑇...
- 123
1
vote
0
answers
173
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
517
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 ...
- 2,519
3
votes
0
answers
117
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
123
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}\|...
- 111
1
vote
0
answers
391
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
2
votes
2
answers
144
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
2
votes
1
answer
120
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
0
answers
349
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
8
votes
1
answer
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
1
answer
488
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
0
answers
147
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{ ...
- 243
3
votes
1
answer
307
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)...
- 159
2
votes
1
answer
282
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 ...
- 211
5
votes
1
answer
1k
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 ...
user116085
6
votes
0
answers
289
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 &...
- 143
2
votes
0
answers
95
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 ...
- 968
3
votes
2
answers
821
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
2
votes
2
answers
335
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
4
votes
1
answer
294
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
5
votes
2
answers
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
3
votes
0
answers
105
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 ...
12
votes
2
answers
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 ...
- 723
1
vote
0
answers
165
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
8
votes
1
answer
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
7
votes
1
answer
449
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
3
votes
1
answer
269
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 ...
- 31
1
vote
1
answer
277
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 ...
- 13
6
votes
1
answer
243
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,962
1
vote
1
answer
653
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 ...
- 325