Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [sparse-matrices]

Use this tag for questions regarding sparse matrices, that is matrices with relatively few entries compared to their size. Related: [numerical-methods] and [numerical-linear-algebra].

6
votes
1answer
69 views

Fast way to Invert ADA' when D is a diagonal matrix that changes each iteration?

So I have a statistical learning algorithm in which D is a diagonal matrix that changes each iteration while A stays the same. I'm looking for a fast way to invert ADA' each iteration which ends up ...
1
vote
1answer
33 views

How to optimize a non-linear least squares energy with respect to the non-zeros of a sparse matrix?

I have an energy I'd like to minimize of the form: $E(G) = \|\underbrace{X - Y G^T L G B}_{f(G)}\|_F^2$ where $X,Y,B$ are dense matrices and $G,L$ are sparse matrices ($G^TLG$ is also sparse), $\|M\...
0
votes
0answers
21 views

Requiring number of data samples in order to learn a dictionary

I have a sparse representation problem where I have the linear model $ \mathbf{x} \approx DA $, where $D$ $\in$ $\mathbb{R}^{N \times K}$ is the dictionary I want to learn and $A=[\alpha_{1}, ..., \...
1
vote
1answer
29 views

How to compute amount of floating point operations for LU-decomposition of banded matrix?

I want to compute the amount of floating point operations, flops, needed for the LU-decomposition/factorization of a banded matrix A consisting of 5 nonzero diagonals. Matrix $A\in\mathbb{R}^{n \...
1
vote
3answers
66 views

Is $det(A)=0$ a good indicator to say that a matrix is not invertible?

In finite elements, for example, appears huge sparce (CRS) matrices (matrices with a lot of zeros). It is possible that matlab (or some other program) calculates $det(A)=0$ even though the matrix is ...
1
vote
0answers
12 views

An alternate for Householder QR linear equation solving for fixed-layout sparse matrix

This concerns sparse matrices where the sparsity pattern is known beforehand, and where the size is between 5 and up to 50, as the linear solver for a Newton Raphson non linear solver. For smaller ...
1
vote
2answers
40 views

Generating a random sparse hermitian matrix in Python

I'd like to find a way to generate random sparse hermitian matrices in Python, but don't really know how to do so efficiently. How would I go about doing this? Obviously, there are slow, ugly ways to ...
3
votes
0answers
35 views

Where can I find 'Emily', the matrix visualization tool?

While searching for a tool to visualize sparse matrices I discovered this paper about 'emily', a piece of software which has everything I need. However, I cannot find a place to download or purchase ...
0
votes
1answer
53 views

Sparse recovery with L1 shrinkage iteration for higher denominational image classification

For 2 months I have been studying sparse recovery and its applications for image classification and I have found that it's a broad area in mathematics which gives rise to a wide variety of ...
1
vote
1answer
17 views

time complexity for sparse matrix multiplication $XX^T$

I have an matrix $X\in R^{m\times n}$ and the matrix is very sparse. Assume the $nnz(X) = D$, which means the number of non-zero elements is $D$, then what is the time complexity to compute $$A = ...
0
votes
1answer
19 views

What is the meaning of “linear projections onto rows of some matrix”?

I was reading through a research paper on compressive particle filtering for target tracking, and I came across the following: Let $z \in d_{z}$ denote a vectorized image with $d_{z}$ pixels. Assume ...
4
votes
1answer
123 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 ...
0
votes
0answers
11 views

Performance of conventional estimation approaches for sparse recovery

If we use conventional estimation methods (like Least squares or MMSE) to recover a sparse vector for which we have random measurements, is the result accurate? Why?
1
vote
1answer
69 views

Moore-Penrose psuedoinverse of Laplacian

I am trying to attain the Moore-Penrose psuedoinverse of a a very large, sparse, rank degenerate, singular, and square matrix. (75000x75000, near rank) I realize the inverse will be very dense. I have ...
0
votes
1answer
43 views

Doing Sparse Recovery in Python

From what I understand, sparse recovery is about: Ax = y I know A, I know y, I want to find a representation of x that is a possible solution. If x >> y, ...
0
votes
2answers
99 views

How to apply conjugate gradient to invert a sparse matrix

I have to clarify a mathematical concept for my research work. The concept is coming from The GraphSLAM Algorithm . There is no need to read the whole paper. I can explain the paper in short here. ...
3
votes
2answers
92 views

Large invertible submatrix in random sparse matrices

The Problem Informal statement of the problem: consider a natural distribution $D_n$ of very sparse $n\times n$ matrices over the binary field $\mathbb{F}_2$ - that is, a matrix sampled from $D_n$ ...
2
votes
1answer
93 views

Making a matrix as sparse as possible

Consider a matrix $A \in \mathbb{R}^{m \times n}$ where $n >> m$. In other words, $A$ has much more columns than rows. Also, consider we are given a fixed number (integer) $m \leq r < n$. I'm ...
0
votes
0answers
26 views

Permutation selection for $P A P^T = L D L^T$ using local minimum fill-in where A is symmetric indefinite

I'm going to find the best permutation matrix to minimize the non-zero elements in the matrix $L$, I have found a strategy called local minimum fill-in, but I couldn't find out how to obtain the best ...
0
votes
0answers
17 views

decompose sparse matrix

I have a sparse matrix $ A (m \times n) $ and I know that each column has at most $p$ non zero elements. I think it should be decomposable into $$ B (p \times n) = P (dim?) \cdot A (m \times n) $$ ...
0
votes
1answer
31 views

Sparse Matrix inversion some time singular some time get a big value

I want to invert a matrix which is a "band" diagonal matrix. The structure of the matrix is The blue strip represents the elements that are non zero.All other element in white area are of zero value. ...
1
vote
0answers
11 views

Regularity of zeros in a sparse matrix

I have a large matrix which is around 70% zeros. How can I test whether there is some statistical regularity to those zeros, as opposed to being randomly distributed?
2
votes
1answer
43 views

Sparse matrix computational difficulties

I am a computer science student. But I start writing here because my problem is not code related. It is purely computational related. I am trying to calculated inverse of a large (e.g., $2000 \times ...
1
vote
0answers
121 views

Solving saddle-point matrix with projection when Schur's complement doesn't exist

I work in the field and FEM and CFD and usually come across such a sparse saddle-point system when dealing with Dirichlet boundary conditions. $\begin{bmatrix} K & S \\ S^T & 0 \end{...
2
votes
1answer
67 views

Constant weight vectors and their linear independence

I'm struggling with a problem for quite some time and unfortunately I haven't found the solution yet.. I would appreciate any insights.. Consider the finite set of all vectors of dimension $n$ with ...
1
vote
0answers
48 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 ...
1
vote
1answer
166 views

What is the most efficient method to compute recuversively (sparse) matrix power?

I have a sparse matrix $P$ and I want to take its $n$-th power. more precisely my problem is "is it better to make for k=1:n result(k)=result(k-1)+P^k; end ...
3
votes
0answers
62 views

Blackbox Methods for Rank Deficient Least Squares

I'm interested in computing the minimal 2-norm least squares solution for a possibly rank deficient (or numerically rank deficient) large sparse matrix A that's hidden behind some black box routine $F$...
1
vote
0answers
28 views

Definition of sparsity

Considering the definition of sparsity in algebra, is it still correct to consider that a matrix / vector is sparse if the position of non-zero elements is known? Can a time-gating operation then be ...
0
votes
0answers
12 views

Finding the smallest 200 eigenvalues of huge (3M x 3M) symmetric positive semi-definite matrix of which the first three eigenvalues are known.

I'm having trouble finding out details about which sparse partial diagonalisation routines are available and what their advantages and disadvantages are, and I am having a hard time penetrating the ...
0
votes
1answer
81 views

How can I approximately solve a 2-player zero-sum game by subselecting its rows/columns?

This is rather an open-ended question, but I'm posting here since I was not able to find a good resource elsewhere. Say there's a two player zero sum game with payoff matrix $A$ that's $N \times H$. ...
0
votes
0answers
376 views

How do you do sparse matrix multiplication using CSR (Compressed Sparse Row) format?

https://en.wikipedia.org/wiki/Sparse_matrix describes the CSR format, but I'm not seeing how you'd multiply two sparse matrices using it. Say I've correctly filled in $A, IA, JA$, and $B, IB, JB$, ...
0
votes
0answers
202 views

What is the best sparse matrix data structure for speeding up multiplication of a $1000 \times 1000$ matrix?

https://en.wikipedia.org/wiki/Sparse_matrix My matrix sparsity is exhibited in this screen capture (250 x 250 matrix): where the non-even rows is because it's a text file output of my matrix. Any ...
0
votes
0answers
37 views

Show that dense matrix is structurally sparse

I'm currently practicing for an upcoming exam but I can't solve the question "a) Show that this dense matrix is structurally sparse". I know that it has rank 4. It is possible to represent a 1-rank ...
3
votes
0answers
68 views

How does minimizing the rank of a matrix help us impute missing values in it?

I am not really a math guru myself, but I know that many estimation or approximation problems can be reformulated as minimizing the rank of a matrix. Although that is really hard, we can try to ...
1
vote
0answers
28 views

Simplification of multiplication of sparse matrices $B(A A^T)A$

I have large very sparse $m \times n$ matrix $\mathbf{A}$, (roughly $10^5 \times 10^3$ with ~99% sparsity). I need to compute $\mathbf{B (A A^\text{T})^{-1}A}$, where $\mathbf{B}$ is a $p \times m$ ...
1
vote
0answers
46 views

Least-squares: sparse normal matrix but full design matrix

In the literature, "sparse least-squares" refer to the problem of minimising $\|Ax-b\|_2^2$ when the design matrix $A$ is sparse. But are there efficient and robust methods for the case when $A$ is ...
3
votes
1answer
91 views

“Pivot step” that Donald Knuth mentioned in TAOCP

I stumbled upon the following operation on matrices in section 2.2.6 Arrays and Orthogonal Lists in the first volume of The Art of Computer Programming, in an example of working with sparse matrices: $...
1
vote
2answers
294 views

Huge matrix multiplication

I have a sparse A matrix stored in column major order (it is intrisically column major) of ~80GB and another sparse matrix B relatively small (1GB) which can be loaded in row or column major with no ...
1
vote
0answers
107 views

In a large sparse matrix, how many eigenvlaues/eigenvectors are “spurious”?

In a large (possibly above 5000x5000) matrix, the problem of finding all the eigenvalues and eigenvectors can be solved using iterative methods (Arnoldi, Lanczos etc.). However, there seems to be a ...
1
vote
0answers
98 views

Is the product of a sparse and a dense matrix also sparse in general?

My goal is to efficiently compute a particular matrix-vector product, say, $\bf{Ax}$, where $\bf{A}$ is a matrix and $\bf{x}$ is a vector. I don't know whether or not $\bf{A}$ is sparse, but I want to ...
0
votes
0answers
149 views

How to densify a sparse adjacency matrix?

I have a sparse symmetric adjacency matrix $\mathbf{A} \in \{0,1\}^{n \times n}$ that denotes an undirected graph. How can I densify the matrix? I mean, how can I find a non-sparse matrix? Is it OK ...
1
vote
0answers
30 views

Complex matrix factorization into three

If you have complex matrix M, how can you decompose M into three matrices, A, B, C? They are all complex and n by n matrices. Additional information of matrices A, B, C is as follows. A and C are ...
0
votes
1answer
40 views

Evaluate a “matrix of bilinear-forms”

I have $n\times m$ sparse matrices $U$ and $V$ ($n \gg m)$, $$ U = \left[ \begin{array}{1} \mathbf{u}_1 \\ \vdots \\ \mathbf{u}_n \end{array} \right],\quad V = \left[ \begin{array}{1} \mathbf{...
2
votes
0answers
17 views

Joint optimization of precision matrices for common sparsity pattern

This question is motivated from paper by Cai, 2016 on joint estimation of multiple (K) precision matrices from K datasets. Let $X^{(k)} \sim N(\mu^{(k)}, \Sigma^{(k)})$ be a p-dimensional random ...
3
votes
0answers
80 views

Factorize product of matrices without actually computing the product of matrices

I have a a system of equations $$ (B^TB + C)x = B^Tb $$ Here, $B$ is a very large, dense matrix and $C$ is a very sparse symmetric matrix. Computing $B^TB$ is infeasible (although computing $BB^T$ ...
2
votes
1answer
22 views

maximal width of nne of matrix-rows

The smallest $b\in\mathbb{Z}_0$ such that $M_{ij} = 0$ for $|i-j| > b$ is the bandwidth of a matrix $M$. Is there also a standard name for the smallest $w\in\mathbb{Z}_{\geq 0}$ such that $M_{ki}\...
1
vote
1answer
34 views

Relation of SVDs between two particular matrices

Let $A = B - C$ be a very large matrix, where $C$ is a matrix with constant value $C$. Note that in my case $A$ represents an undirected graph adjacency matrix. I need to find the max singular value ...
2
votes
1answer
85 views

How to Mathematically Recover Sparse Signal (Least Squares with $ {L}_{1} $ Regularization - LASSO)?

I got this equation for signal recovery by using LASSO: $$\alpha_y =\mathrm{argmin} \left(\| Y - D\alpha \|_2^2 + \lambda^* \|\alpha\|_1\right) $$ Here $D$ is a Dictionary, $Y$ is noisy data signal ...
1
vote
1answer
196 views

What Is the Quickest Method to Solve $ A x = b $ for $ A $ Being Sparse Semi Definite Positive Matrix?

A is a huge scale of sparse symmetric semi-positive matrix. In MATLAB, the solution can be solved by b=A\b; But it is ...