Questions tagged [sparse-matrices]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
13 views

Positive semi-definite block diagonal covariance matrix with exponential decay

I am implementing Kalman filtering in R. Part of the problem involves generating a really huge error covariance block-diagonal matrix (dim: 18000 rows x 18000 columns = 324,000,000 entries). We denote ...
2
votes
0answers
16 views

Calculating diagonal of inverse of sparse band-like matrix

I'm trying find an optimization for an equation related to theorem 3.5.7 from "Finite Markov Chains" by Kemeny and Snell (1976). The theorem is: $$H=(N-I)N_{dg}^{-1}$$ Where $N_{dg}$ is a diagonal ...
0
votes
0answers
52 views

How to quickly solve a linear equation for 7000 times?

I need to solve a linear equation Ax=b for 7000 times (A is sparse and complex square matrix), and at each time only 4 elements (A(i,k), A(i,m), A(j,k) and A(j,m)) are changed while all other elements ...
1
vote
0answers
35 views

Why is sparsity useful in dictionary learning?

What is the particular reason for which we use sparse matrix X in dictionary learning equation Y=DX where Y is the signal matrix, D is dictionary and X is the coefficient matrix?
1
vote
0answers
35 views

Computing (near) optimal displacement tables

Suppose we have a two-dimensional table $T$ with $r$ rows and $c$ columns that is sparse. Let $T[i][j]$ be the element at the $i$th row and $j$th column of $T$, with zero-based indexing. We can ...
1
vote
1answer
17 views

Smallest Circuit for Square of Sparse Symmetric Matrix

I have an n by n symmetric matrix, and I would like to compute its square in as small a circuit complexity as possible. It's sparse: there are sqrt(n) nonzero entries in each row/column, so the input ...
1
vote
1answer
56 views

Optimize sorting matrix entries by row and column

I am writing a routine to store an $M$-by-$N$ sparse matrix in a balanced binary tree. The insertion routine calls a comparison function to determine where a new matrix entry $(i,j)$ should be ...
0
votes
0answers
4 views

Looking for a specific type of ADMM iterates

For a $k-$dimensional optimization variable $b \in \mathbb{R}^k$ say the objective is given as, $$f(b) = \langle b, v \rangle + \langle b , Ab \rangle + \lambda \Vert b \Vert_1$$ for some parameter ...
1
vote
0answers
52 views

Sparse Matrix inversion without actual inversion

I want to know what are the efficient way to invert a Sparse Matrix? Are there any algorithm,linear algebra or expansions that make this task easier with out actually inverting the matrix? Thank you ...
6
votes
1answer
157 views

Chernoff-Hoeffding bounds for the number of nonzeros in a submatrix

Consider a $n \times n$ matrix $A$ with $k$ nonzero entries. Assume every row and every column of $A$ has at most $\sqrt{k}$ nonzeros. Permute uniformly at random the rows and the columns of $A$. ...
2
votes
1answer
33 views

GraphSlam Doubt

I am trying to implement Graph slam. I have some doubts regrading implementation. I attached a picture to clarify my doubt. [ I have a doubt in line number 2. It show omega have a scalar value 0. ...
3
votes
1answer
199 views

Need clarification about the use of Big-O to describe matrix sparsity

In one of my courses, Big-O notation was used for defining what a sparse matrix is, under the context of qualifying for suitability for a particular set of linear algebra algorithms. I looked around ...
3
votes
1answer
553 views

Finding the bandwidth of a band matrix

I am designing an algorithm that solves a linear system using the QR factorization, and the matrices I am dealing with are sparse and very large ($6000 \times 6000$). In order to improve the ...
1
vote
1answer
188 views

What is the literature on a sparse matrix encoding of rose trees?

I have 'discovered' a way to encode rose trees (see e.g. What are the applications of Rose trees? ) as a sparse matrix: if you have a node n with ID i and parent ID p, then you place n in the matrix ...
0
votes
1answer
585 views

Running time of sparse matrix multiplication

Given a sparse matrix $M \in \mathbb{R}^{n \times m}$ with $n \ll m$ and $\mathsf{nnz}$ being the number of non-zero-components. What is the running time of computing $M M^T$?
2
votes
1answer
227 views

Permutation on matrix to fill main diagonal with non-zero values

I am currently working on some sparse non-singular matrices. One of the algorithms I use requires divisions by the elements on the main diagonal so I have to ensure that my main diagonal is filled ...
0
votes
0answers
43 views

Is there a non-linear version of ICA?

"Independent Component Analysis" is this : someone is sampling a random vector $s \in \mathbb{R}^d$ such that all its components $s_i$ are mutually independent and $\mathbb{E}[s_i^4] < 3$ and the ...
1
vote
0answers
55 views

Compressed row storage: What happens if last row is all zeros? [closed]

I am studying compressed row storage (CRS format) for storing an sparse matrix. I can't tell how this works if the matrix has a row with all entries zero, and in particular, what happens with the ...
8
votes
1answer
834 views

Inverting a band matrix

I have a band matrix -- a sparse, square, symmetric $N \times N$ matrix whose structure looks like the following: Here, the area under the blue stripes is the non-zero elements; everything else is ...
3
votes
1answer
2k views

SimRank on a weighted directed graph (how to calculate node similarity)

I have a weighted directed graph (it's sparse, 35,000 nodes and 19 million edges) and would like to calculate similarity scores for pairs of nodes. SimRank would be ideal for this purpose, except that ...
5
votes
2answers
344 views

Data structure for sparse matrices for an online problem

I need to compute a large linear optimization problem very often after recieving updates to my optimization problem. That is I have a linear problem to find an x such that $x_1 * c_1 + ... + x_n * ...