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

173 questions
Filter by
Sorted by
Tagged with
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{aligned} \min_{...
98 views

• 335
12 views

• 101
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 ...
• 21
1 vote
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 ...
88 views

1 vote
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 ...
• 1,437
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 ...
• 253
1 vote
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 <<...
• 51
41 views

• 41
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'...
• 13
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{...
• 83
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)...
• 121
1 vote
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 ...
• 21
1 vote
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 ...
• 13
1 vote
100 views

• 2,531
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, ...
• 825
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 ...
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 ...
• 11
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 ...
• 4,133
1 vote
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 ...
• 227
1 vote
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 ...
• 35
1 vote
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 ...
• 31.8k
1 vote
65 views

• 1,911
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 ...
• 402
1 vote
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 ...
• 450
61 views

• 4,133
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 ...
1 vote
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$). ...
1 vote
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 ...
• 24.2k
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$...
• 101
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 ...
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 ...