The sparse-matrices tag has no wiki summary.

**6**

votes

**1**answer

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

**1**

vote

**1**answer

109 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

102 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

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

**1**

vote

**1**answer

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

votes

**1**answer

133 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

**0**answers

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

**8**

votes

**4**answers

2k views

### Eigenvectors and eigenvalues of Tridiagonal matrix

Hi, is it possible to analytically evaluate the eigenvectors and the eigenvalues of a tridiagonal matrix of the form :
$$
\mathcal{T}^{a}_n(p,q) = \begin{pmatrix}
0 & q & 0 & 0 ...

**2**

votes

**1**answer

370 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

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

**5**

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

229 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

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

**5**

votes

**1**answer

497 views

### Are there interesting problems involving arbitrarily long time series of small matrices?

Are there well-known or interesting applied problems (especially of the real-time signal processing sort) where arbitrarily long time series of small (say $d \equiv \dim \le 30$ for a nominal bound, ...