Skip to main content

Questions tagged [sparse-matrices]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
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" ...
ACR's user avatar
  • 831
6 votes
0 answers
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 ...
Daniel Weber's user avatar
  • 3,029
0 votes
0 answers
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 ...
SRB121's user avatar
  • 71
6 votes
0 answers
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 ...
John Pardon's user avatar
  • 18.5k
1 vote
1 answer
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 ...
Hari Sam's user avatar
0 votes
1 answer
75 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., $\|\...
Math_Y's user avatar
  • 311
2 votes
0 answers
26 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*}...
Bjornson's user avatar
0 votes
1 answer
41 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 ...
ABIM's user avatar
  • 5,079
1 vote
1 answer
384 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 ...
Titouan Vayer's user avatar
1 vote
0 answers
47 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 ...
Titouan Vayer's user avatar
3 votes
0 answers
88 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 ...
Matt Hastings's user avatar
6 votes
1 answer
630 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 ...
Sébastien Loisel's user avatar
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 ...
Matt Hastings's user avatar
1 vote
0 answers
122 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, \...
Daniel Li's user avatar
  • 519
5 votes
0 answers
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 ...
MRm's user avatar
  • 183
2 votes
0 answers
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$ ...
ABIM's user avatar
  • 5,079
1 vote
1 answer
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 ...
Prashant Govindarajan's user avatar
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 ...
Adrien's user avatar
  • 8,454
3 votes
0 answers
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 ...
Jianqiang Li's user avatar
0 votes
0 answers
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? ...
gondolf's user avatar
  • 1,503
3 votes
2 answers
631 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^𝑇...
HesterJ's user avatar
  • 123
1 vote
0 answers
163 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 ...
charlie_bronx_'s user avatar
1 vote
1 answer
496 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 ...
grok's user avatar
  • 2,489
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 ...
Nacho Garcia Marco's user avatar
1 vote
1 answer
122 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}\|...
Christina's user avatar
  • 111
1 vote
0 answers
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 ...
user0410's user avatar
  • 211
2 votes
2 answers
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 ...
Gericault's user avatar
  • 245
2 votes
1 answer
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 ...
user3095304's user avatar
1 vote
0 answers
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 ...
Srinath's user avatar
  • 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 ...
messcode's user avatar
1 vote
1 answer
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 ...
Morpheus's user avatar
  • 121
1 vote
0 answers
144 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{ ...
pisoir's user avatar
  • 243
3 votes
1 answer
294 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)...
SC_thesard's user avatar
2 votes
1 answer
277 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 ...
Alex Golovnev's user avatar
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 ...
user avatar
6 votes
0 answers
281 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 &...
Integral's user avatar
  • 143
2 votes
0 answers
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 ...
Daniel Soudry's user avatar
3 votes
2 answers
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 ...
Paul Irofti's user avatar
2 votes
2 answers
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 ...
kip622's user avatar
  • 123
4 votes
1 answer
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 ...
John's user avatar
  • 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.
unknown's user avatar
  • 451
3 votes
0 answers
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 ...
HoseinMohimani's user avatar
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 ...
Alec Jacobson's user avatar
1 vote
0 answers
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 ...
Memming's user avatar
  • 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-...
Jeff's user avatar
  • 500
7 votes
1 answer
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-...
Toughee's user avatar
  • 103
3 votes
1 answer
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 ...
user69820's user avatar
1 vote
1 answer
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 ...
Wenlong Cai's user avatar
6 votes
1 answer
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-...
Felix Goldberg's user avatar
1 vote
1 answer
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 ...
MMM's user avatar
  • 245