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

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

Sample problem to test sdp optimization

I am trying to write code for an algorithm to solve sparse SDP problems using distributed computing. The form of the problem I am trying to solve is as follows: \begin{equation} \begin{aligned} \min_{...
user avatar
3 votes
2 answers
98 views

Eigenvalues of a sparse 8x8 matrix

I have the following $ 8 \times 8 $ sparse matrix $ P=\begin{bmatrix} 0.5 & 0.5 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.5 & 0.5 & 0.0 & 0....
user avatar
  • 331
0 votes
0 answers
32 views

Can one solve more sparse system(s) in Levenberg–Marquardt?

In the least squares solving algorithm, levenberg-marquardt, one iteratively solves a system of the form $ (J^T \cdot J + \lambda I) h_{lm} = -J^Tf $. The concept being that the dampening parameter, $\...
user avatar
  • 335
0 votes
0 answers
12 views

Matrix linear transformation to wipe out a sparse matrix

Is there any linear transformation that can wipe out the following matrix? $$\mathbf{A} = \begin{pmatrix} a_{11}&0&0&a_{14}&0&0 \\ a_{21}&0&0&a_{24}&0&0\\ a_{...
user avatar
0 votes
0 answers
23 views

Matlab sparse matrix memory storage

I have been asked to compare the memory usage for a full matrix vs a sparse matrix. Matlab says that a full matrix stores every element, while a sparse matrix only needs to store the non-zero elements ...
user avatar
  • 11
0 votes
0 answers
16 views

Row-Wise Group Sparsity in (Covariance) Matrix

Given $N$ groups $G=1,..,N$ with different number of samples, we assume that each sample in a group is generated from a group-specific Multivariate Normal distributions (e.g., here 3 groups): $$ s_{1,...
user avatar
  • 101
2 votes
1 answer
94 views

Inverse of matrix with hadamard product

Let $A$ and $B$, $X$ be matrices with $\mathbb{R}^{n \times n}$ where $A$, $B$ are a dense and sparse matrix, i.e., the almost elements of $B$ are zeros, respectively. I'm looking for a way to solve ...
user avatar
  • 21
1 vote
2 answers
60 views

Inverting a huge sparse banded matrix

I have a matrix of $9,200 \times 9,200$ elements. I have approximately $90$ of these matrices to invert. The reason for this is I am running a nonlinear regression on a problem with significant errors ...
user avatar
2 votes
2 answers
88 views

Inverse of a particular sparse matrix

I need to find the inverse of a sparse square matrix that has the following sparsity pattern. $$\begin{bmatrix} * & * & * & * & * & * & * & * \\ * & * & 0 & 0 &...
user avatar
  • 177
0 votes
0 answers
52 views

Exponential of a special matrix

Problem definition Given an integer $N>1$, let $A_N$ be the following $N\times N$ matrix \begin{equation*}A_N\triangleq \left[\begin{array}{c|c} & I_{N-1} \\ \hline 0_1 & \end{array}\...
user avatar
0 votes
0 answers
13 views

Is there a way to increase the speed of multiplying $(-x^T\delta\ x )$

The x matrix has a size of 1024x1 and the $\delta$ has a size of 1024x1024. Delta is also a symmetric and sparse matrix. I am using the following equation to calculate a variable inside a loop. $$x^T\...
user avatar
1 vote
0 answers
11 views

Sparse least squares where the coeefficient matrix is not stored explicitly

Consider a bounded linear operator $A : U \to V$ where $U$ is finite dimensional and where $V$ is a separable Hilbert space, or with large dimension such that $A$ cannot be stored explicitly, being ...
user avatar
  • 1,437
0 votes
0 answers
30 views

Is the inverse of a Hermitian sparse block matrix a Hermitian block matrix of the same sparse form

Lets assume we have an invertible Hermitian block matrix of the following kind: $$A = \begin{pmatrix} A & B \\B^*& 0 \end{pmatrix},$$ We know that the inverse of a Hermitian matrix is ...
user avatar
1 vote
1 answer
52 views

How to understand each optimization step of Jacobi Iterative

Q: I saw Yousef Saad said "The Jacobi iteration determines the i-th component of the next approximation so as to annihilate the i-th component of the residual vector" in his book <<...
user avatar
  • 51
0 votes
0 answers
41 views

Cholesky factorization of A'QA

My goal is to compute the Cholesky factorization $A'QA$ efficiently, where $Q$ is a large, sparse positive definite matrix and $A$ is typically dense and has significantly fewer columns than $Q$. If $...
user avatar
  • 109
1 vote
0 answers
83 views

Measure of closeness of a matrix to the block diagonal form

Is there a well-behaved measure for closeness of a matrix to the block diagonal form? Permutations of rows and columns are assumed to be allowed. This thread discusses the closeness to the diagonal ...
user avatar
1 vote
0 answers
53 views

Reordering vertices of a graph to make the adjacency matrix a block matrix with band-shaped blocks

Let $G = (V, E)$ be a sparse oriented graph with $n$ vertices (i.e. no loops, no multi-edges, about 1-5% of all possible $n\cdot(n-1)/2$ edges are present). The value of $n$ is about $100$. Let $A$ be ...
user avatar
1 vote
0 answers
89 views

Failure to invert sparse matrix

I have a large block arrowhead matrix which has significant sparsity in the following pattern: $\mathbf{M} = \left( \begin{array}{c|c} \mathbf{A} & \mathbf{B}^{\top}\\ \hline \mathbf{B} & \...
user avatar
  • 41
0 votes
0 answers
129 views

Time complexity of Sparse x Dense matrix multiplication

I'm wondering time complexity of (sparse x dense) matrix multiplication. Let's assume $A$ (nxn sparse matrix), $H$ (nxd dense matrix), and $W$(dxd dense matrix). $A$ has $k$ non-zero elements in it. I'...
user avatar
  • 13
7 votes
1 answer
124 views

Sparse PCA vs Orthogonal Matching Pursuit

Can't wrap my head around the difference between Sparse PCA and OMP. Both try to find a sparse linear combination. Of course, the optimization criteria is different. In Sparse PCA we have: \begin{...
user avatar
2 votes
0 answers
112 views

Solve Ax = b (A and b both large and very sparse), but only for the values in some rows of x

I have a linear system $Ax=b$ where: $A$ is square, large ($m$ and $n$ on the order of $10^5$), asymmetric, very sparse (around $0.05\%$ non-zeros) $b$ is very sparse (also $0.05\% - 0.1\%$ non-zeros)...
user avatar
  • 121
1 vote
0 answers
41 views

Why large linear systems of saddle point type are indefiniteness and often poor spectral properties?

I'm reading the paper "Numerical solution of saddle point problems" by Michele Benzi. In the abstract, he states that these types of large linear systems of saddle point are challenging due ...
user avatar
  • 21
1 vote
1 answer
74 views

LSQR method for solving a linear equation with positive value constraint for one column of the solution

I am solving an overdetermined sparse linear problem (Ax= B) using a C code. The code is using the LSQR method to find the solutions. There are 6 unknowns for every equation. One of the solutions is a ...
user avatar
  • 13
1 vote
1 answer
100 views

Find a sparse surrogate matrix that performs as good as the original one

Let $A\in \mathbb{R}^{m \times n}$ be a dense matrix and $x$ is a given vector in $\mathbb{R}^n$. How can one solve the following problem or its relaxation to find a sparse matrix that acts like $A$? $...
user avatar
  • 825
1 vote
1 answer
60 views

Solving a sparse vector $x$ from system $Ax=b$ at the fastest possible way?

I'm going to solve this linear system: $$Ax=b$$ Where $x$ is sparse. To do that, Inned to minimize this. This is called lasso regression. $$\nabla J = ||Ax - b||_2 + \lambda ||x||_1$$ Where $\lambda &...
user avatar
  • 2,531
2 votes
1 answer
142 views

Relationship between matrices whose singular values are the same

Motivation: I have two different matrices in $\mathbb{R}^{1000 \times 2048}$. $A_1$ is coming from an sparse optimization process whose objective is creating as much as zeros in $A_1$. In this sense, ...
user avatar
  • 825
0 votes
0 answers
32 views

Simultaneously sparsifying symmetrical real matrices

Suppose that we have $m\in N_+$ symmetrical real matrix $A_i,i=1,2...m,A_i\in R^{n\times n}$. Can we find an orthogonal matrix $T\in R^{n\times n}, TT'=T'T=I$ such that all of $B_i=T'A_iT$ are sparse ...
user avatar
0 votes
0 answers
61 views

Show that Restricted Isometry property implies Restricted nullspace property

I need to show that if matrix A satisfies the RIP then it also satisfies the RNP. I need to prove that each of the lemmas holds and then show that RIP implies RNP using the lemmas. Lemma 1: Let the ...
user avatar
  • 11
5 votes
1 answer
451 views

What does LSQR stand for

One of the most popular and efficient iterative methods to solve large sparse systems of equations in the least squares sense is LSQR. It is related to CGLS (Conjugate Gradient Least Squares) in that ...
user avatar
  • 4,133
1 vote
0 answers
35 views

Can the block-Lanczos algorithm possibly converge faster than the single-vector Lanczos?

We use the Lanczos algorithm for finding eigenvalues and eigenvectors of large sparse real matrices to model atomic nuclei. However, for heavier nuclei and their higher energy states, the matrix ...
user avatar
1 vote
0 answers
15 views

Anomaly in sparse recovery when support is known.

I am interested in oracle performance in sparse recovery when support is known and am stuck in an anomaly. Consider a sparse recovery of n dimensional vector with p observations, y = Xh + n, where X ...
user avatar
  • 35
1 vote
2 answers
156 views

Iteratively solving (sparse) homogeneous linear systems

Solving (sparse) non-homogeneous linear systems can be done iteratively, by using the LSQR algorithm or similar. However, in the homogeneous case, we have $Ax =0$, where we typically want to find the ...
user avatar
  • 31.8k
1 vote
1 answer
65 views

Efficiently invert threediagonal symmetric matrix

I need to invert a threediagonal symmetric $1000\times10000$ matrix (or of similar dimensions). Specifically I need to solve the following equation: $$Ax=b$$ with $$A=\begin{pmatrix}v_1&-\frac{dt}{...
user avatar
  • 489
0 votes
1 answer
30 views

In order to induce group sparsity, can we use $\left \| A \right \|_{1,1}$ instead of $\left \| A \right \|_{1,2}$?

Let's define $\left \| A \right \|_{p,q}$ as follows: $$\left \| A \right \|_{p,q} = \sum_{i=1}^n \left \| \alpha^i \right \|_q^p$$. Where $\alpha^i$ is the i-th row of the matrix A. The above norm is ...
user avatar
  • 103
1 vote
0 answers
68 views

Approximate upper bound on eigenvalues of $I-A$ where $A$ is a sparse matrix wherein each row sums to 1.0

Suppose $A$ is a large matrix with the following properties: $A$ is $n\times n$ $A$ is sparse (with each row having at most 8 non-zero coefficients, regardless of $n$) $A$'s diagonal has only zeros. ...
user avatar
  • 807
1 vote
1 answer
128 views

Null-Space Projection with a Long Sparse Matrix

I want to solve the classical projection problem: given $x_0:n\times 1$ and a sparse matrix $C: m \times n$, solve for: $$ x = \operatorname{argmin}|x-x_0|^2,\ s.t. \\ Cx = 0 $$ The three usual ways ...
user avatar
0 votes
0 answers
187 views

Eigenvectors of block diagonal matrix

Consider a finite dimensional block diagonal matrix $A$ over $\mathbb{C}$ given by $$ A = \bigoplus_i A_i, $$ where $A_i$ are mostly the 0 matrix (of some finite dimension), i.e. the matrix is very ...
user avatar
2 votes
1 answer
29 views

Iterative solver for linear least squares, involving a large sparse/structured r.h.s.

Let $B$ be a $n$ by $n$ matrix, and $A$ a $n$ by $m$ matrix. I'm looking for the variable $X$, of size $m$ by $n$, that approximately solves $A X = B$; more precisely, the matrix $X$ that minimizes ...
user avatar
1 vote
0 answers
18 views

Show that norm is reduced in each iteration for weighted additive orthogonal projection

I'm stuck in the following problem from Saad's Iterative Methods for Sparse Linear Systems: In an additive projection procedure, the $k+1$th residual vector is $$\vec{r}_{k+1} = \sum_{i=1}^p w_i (I-...
user avatar
  • 1,911
0 votes
1 answer
45 views

Removing non-diagonal entries from a PSD matrix keeps the PSD property?

I was thinking about positive semidefinite (PSD) sparse matrices and I began to wonder whether the following is true: Let $A$ be a PSD matrix and let $\bar{A}$ be obtained from $A$ by replacing some ...
user avatar
  • 402
1 vote
0 answers
18 views

Optimizing the solution of a sparse linear system with a particular structure

I am trying to solve computationally a sparse linear system of the form $Ax=B.$ A is a square matrix, for example of size $1600\times 1600$ (the exact size depends on the parameters of my program). B ...
user avatar
  • 450
0 votes
0 answers
61 views

Proving that a matrix is sparse

I have the following identity: $$L=(I-A)^TD^{-1} (I-A),$$ where $I$ is the identity matrix, $A$ is a $n \times n$ lower triangular matrix with no more than $m \ll n$ non-zero elements in each row and $...
user avatar
  • 247
0 votes
0 answers
68 views

How to update/recalculate the inverse of matrix after changed one element's value?

I have a large sparse matrix A and have gotten its inverse matrix inv(A) . Then I need to change an element value to get a new ...
user avatar
  • 135
5 votes
1 answer
115 views

Why does MINRES converge in 3 iterations on matrices of specific form?

The MINRES algorithm for solving $Ax = b$ for symmetric $A$ can be described as follows: The $k$-th iterate of the algorithm is $$x_k = \arg\min_{K_k(A)} \lVert Ax-b \rVert_2$$ where $K_k(A)=\text{...
user avatar
  • 4,133
0 votes
1 answer
437 views

Solve banded linear system with large bandwidth but sparse interior band structure

Assume the linear system $Ax = b$, where $A$ is a $N \times N$ banded matrix with lower and upper bandwidth $l$, and $N >> l >> 1$. $A$ has the following structure: All entries of $A$ are ...
user avatar
  • 3
1 vote
0 answers
181 views

Inverse a sparse matrix

I have a sparse singular matrix W where I want to find its inverse Q. My current method is to use $W*Q = I$ for an optimization process of approximating the convergence of cost function norm($I-W*Q$). ...
user avatar
1 vote
1 answer
49 views

Fast algorithms for long sequences of sparse matrix products multiplying a vector?

Context: Having worked with developing algorithms involving huuge linear least squares systems involving sparse matrices, so far I have mostly constructed these huge sparse matrices explicitly and ...
user avatar
  • 24.2k
0 votes
0 answers
27 views

Expressing OneHotEncoding as a linear algebra operation

In ML applications dealing with categorical variables, it is often required to transform them into a OneHotEncoded representation. For example, given a vector of categorical features, $x=(1,3,4,2,3)^T$...
user avatar
  • 101
0 votes
1 answer
50 views

Vector density as a function of sparsity

Many works denote $\phi(x)$ as density of a vector. $$ \phi(x) = \frac{||x||_1^2}{d||x||_2^2} $$ where $x \in \mathbb{R}^d$. Can we say that this quantity decreases as we increase sparsity? For ...
user avatar
2 votes
0 answers
157 views

What is the complexity of determining the eigenvalues of a very sparse matrix?

Suppose I have an $n \times n$ matrix with $O(n)$ nonzero elements. With what time complexity could the eigenvalues or characteristic polynomial of this matrix be computed? More easily, suppose I ...
user avatar