# Questions tagged [sparse-matrices]

The sparse-matrices tag has no usage guidance.

52
questions

**0**

votes

**0**answers

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

**0**

votes

**0**answers

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

**2**

votes

**0**answers

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

**3**

votes

**0**answers

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

**1**

vote

**1**answer

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

**6**

votes

**0**answers

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

**3**

votes

**0**answers

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

**0**

votes

**0**answers

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

**2**

votes

**2**answers

149 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

93 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

162 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

99 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

84 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

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

**2**

votes

**2**answers

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

**2**

votes

**1**answer

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

**1**

vote

**0**answers

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

**7**

votes

**1**answer

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

**1**

vote

**1**answer

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

**1**

vote

**0**answers

84 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

157 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

146 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

812 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

254 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

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

**2**

votes

**2**answers

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

**2**

votes

**2**answers

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

**4**

votes

**1**answer

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

**4**

votes

**2**answers

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.

**3**

votes

**0**answers

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

**8**

votes

**2**answers

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

**1**

vote

**0**answers

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

**8**

votes

**1**answer

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

**7**

votes

**1**answer

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

**3**

votes

**1**answer

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

**1**

vote

**1**answer

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

**6**

votes

**1**answer

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

**1**

vote

**1**answer

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

**1**

vote

**1**answer

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

**2**

votes

**0**answers

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

**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

429 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

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

**3**

votes

**2**answers

691 views

### Spectra of VERY sparse random matrices

Consider an $n\times n$ random binary matrix $M$ with i.i.d. entries $m_{ij} \sim {\rm Bernoulli}(p)$, where $p = n^{-\beta}$ with $\beta \in (1,2)$. I am interested in the behavior of the singular ...

**2**

votes

**1**answer

556 views

### minimizing functions over simple matrix inequalities

I'm wondering if anything is known about minimizing convex, not necessarily linear functions subject to "simple" matrix equalities. To be precise, consider the following example:
$min \Sigma x_i ln ...

**0**

votes

**0**answers

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

**6**

votes

**5**answers

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

**2**

votes

**0**answers

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

**0**

votes

**2**answers

2k views

### How to accelerate/avoid multiplication for large matrices in Matlab? [closed]

The setting is here.
X: 6000x8000 non-sparse matrix
B: 8000x1 sparse vector with only tens of non-zeros
d: positive number
M: is sparsified X'X, i.e. thresholding the elements smaller than d ...

**4**

votes

**2**answers

5k views

### Computing the largest eigenvalue of a very large sparse matrix

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