Questions tagged [sparse-matrices]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 $...
user avatar
  • 131
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 12.8k
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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, \...
user avatar
  • 519
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 ...
user avatar
  • 153
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$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 7,422
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 ...
user avatar
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? ...
user avatar
  • 1,265
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^𝑇...
user avatar
  • 113
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 ...
user avatar
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 ...
user avatar
  • 2,287
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 ...
user avatar
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}\|...
user avatar
  • 111
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 ...
user avatar
  • 211
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 ...
user avatar
  • 185
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 ...
user avatar
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 ...
user avatar
  • 11
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 ...
user avatar
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 ...
user avatar
  • 121
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{ ...
user avatar
  • 243
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)...
user avatar
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 ...
user avatar
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 ...
user avatar
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 &...
user avatar
  • 143
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 123
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 ...
user avatar
  • 91
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.
user avatar
  • 419
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 281
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-...
user avatar
  • 500
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-...
user avatar
  • 103
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 ...
user avatar
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 ...
user avatar
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-...
user avatar
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 ...
user avatar
  • 213
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 ...
user avatar
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 ...
user avatar
  • 137
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,...
user avatar
  • 165
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} )
user avatar
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 ...
user avatar
  • 11