# Questions tagged [sparse-matrices]

The tag has no usage guidance.

52 questions
Filter by
Sorted by
Tagged with
19 views

### Most efficient way to solve against large sparse matrix with a few dense rows and columns?

I have a constrained optimization problem of the form: $$\min_{Bx=g} \frac{1}{2} x^T A x - x^T f$$ $A \in \mathbb{R}^{n\times n}$ is positive semi-definite (with a tiny null space of dimension &...
44 views

### Recovering sparsity from $\ell^1$ relaxation

I've read that $\ell^1$ norm on $\mathbb{R}^n$ is the convex relaxation of the $\ell^0$ "norm": $$\|x\|_0 \triangleq \sum_{i=1}^n I_{x_i \neq 0}.$$ In the regression setting, under what ...
45 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 ...
69 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$ ...
84 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 ...
96 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 ...
69 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 ...
63 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? ...
149 views

176 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 ...
109 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 ...
70 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 ...
183 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 ...
404 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 ...
148 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 ...
84 views

84 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 ...
450 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 ...
127 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 ...
243 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 ...
999 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.
83 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 ...
2k 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 ...
128 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 ...
673 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-...
368 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-...
211 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 ...
198 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 ...
174 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-...
395 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 ...
110 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 ...
371 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 ...
1k views

255 views

### L1-regularized Least Squares on a matrix with Toeplitz Blocks (not block-Toeplitz)

I am trying to speed up a sparse signal recovery algorithms. My sensing matrix is a set of Toeplitz Blocks, M = [T1,T2,T3,...,Tk] The objective is min ||Mx - b||_2^2 + ||x||1 What I'm actually ...
1k views

### Computer algebra system for calculation of characteristic polynomial of sparse matrix

I have a $n \times n$ matrix, for which i need to calculate the characteristic polynomial. The matrix is over $GF(2)$, and $n \approx 10^4$. However the matrix is very sparse, with around $n$ non ...
268 views

### Sparse Eigenvectors for the Discrete Fourier Transform matrix

There are many ways to choose eigenbasis for the Discrete Fourier Transform matrix since it has only $4$ distinct eigenvalues taken from $\{\pm 1,\pm i\}$. Has there been any refereed work that ...
I am trying to compute the asymptotic growth-rate in a specific combinatorial problem depending on a parameter $w$, using the Transfer-Matrix method. This amounts to computing the largest eigenvalue ...