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].
198 questions
1
vote
0
answers
32
views
4th Order Tensor multiplication Rules for Sparse Regression analysis
I am working on a problem which involves working with stress and deformation tensors of the order 4. I have a set of data at different time steps for 20 cases and each element stress is 3x3 matrix, so ...
1
vote
1
answer
87
views
Solve L1 Regression where $\left\| \boldsymbol{A} \boldsymbol{x} \right\| \ll \left\| \boldsymbol{x} \right\|$
I'm trying to solve an $l_1$ minimization problem with objective function $h(x)=\|Ax-b\|_1$ for some vector $b$ and sparse matrix $A$. It happens that in my problem there are values of $x$ for which $\...
- 1,968
0
votes
0
answers
54
views
How does L1 regularization lead to sparse parameter matrix?
It is commonly said that L1 regularization on the parameters yields a sparse solution.
For which kind of problems is that true? Does that go only for linear problems (even though neuronal networks ...
- 164
0
votes
1
answer
89
views
Reducing the graph weight matrix to block-diagonal form
Let's imagine that we have a graph (undirected) and a sparse weight matrix (not a complete graph), not necessarily symmetric. The vertices are numbered in some way. Are there any theorems or ...
- 53
0
votes
0
answers
62
views
Construction of sparse matrix for Poisson Equation with Neumann BC
I am solving Poisson's equation in 2D numerically, imposing Neumann Boundary Conditions. I am using the sparse factorization of the problem $L_h u_h = f$. I am having trouble when extending the matrix ...
- 1
0
votes
1
answer
74
views
Projection Methods in Sparse Matrices
Let $A$ be a symmetric positive definite matrix and fix $b \in \mathbb{R}^n$. Consider solving for the solution $x^* = A^{-1}b$ by using a projection method. In other words, we have a sequence of ...
- 25
1
vote
0
answers
46
views
Can We Find a More Sparse $S$?
Original question
I am working with a sparse matrix $S$ with the assumption of sparsity such that in a matrix of $N^2$ elements, at most $2N$ are non-zero. (This sparsity condition could be adjusted ...
- 93
1
vote
0
answers
65
views
Efficient Algorithm for Binary Tensor Decomposition?
I've been working with high-dimensional binary tensors (e.g., tensors with entries that are only 0s and 1s) and I'm looking for an efficient way to decompose them into rank-1 components. The tensors I'...
- 11
0
votes
0
answers
85
views
Constructing a sparse matrix with some constraints
I want to construct a sparse matrix $A \in \mathcal{R}^{K\times L} $ with some rules.
The rules are as follows:
Each row must have $T_r$ nonzero elements
The maximum number of nonzero elements in ...
3
votes
1
answer
189
views
Efficient algorithm to solve a sparse recovery problem
I come across with a problem of the form $y=Hx + z \in \mathbb{R}^m$, where $z\in \mathbb{R}^m$ is the noise vector, and $x \in \mathbb{R}^N$ is partially known. $H\in \mathbb{R}^{m \times N}$ can be ...
0
votes
0
answers
80
views
How to maximize the sparsity of orthogonal matrix?
Given a unit vector $v\in\mathbb{R}^n$, it's needed to find an orthogonal matrix $Q\in \mathbb{R}^{n\times m}$ ($m \leq n$) of maximum sparsity.
What are the bounds of sparsity for such matrix? What ...
- 1,076
0
votes
1
answer
75
views
Solving $Ax=b$: Projection onto subspace with a canonical basis of largest error
The goal is to solve the linear system $Ax = b$, where $A$ is symmetric and positive definite (SPD). Consider the one-dimensional projection method given by equation (1):
$$x_{k+1} = \operatorname{...
- 165
0
votes
0
answers
97
views
Decide whether a 0-1 matrix has full rank
Is there a theorem about when a (sparse) 0-1 matrix $A = (a_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$ has full rank? More concretely, I know the row sums of $A$,
$$ r_i = \sum\limits_{j=1}^m ...
0
votes
1
answer
69
views
Can a sparse linear system be simplifed by dropping zero-valued rows and columns
I am solving a problem in which, the product of the transpose of a sparse matrix $M^T$ and the matrix $M$ is a large, sparse square matrix having the form:
$$
\begin{array}{ccccccccc}
1\; & 2\; &...
- 1,277
0
votes
0
answers
65
views
Is the product $B D B^T$ always a symmetric tridiagonal matrix? Where $D$ is a diagonal matrix and $B$ a sparse matrix.
I have a diagonal matrix ${\bf D}_{n \times n}$ and a rectangular matrix ${\bf B}_{m \times n}$ where $n \gg m$.
All but $m$ rows of ${\bf B}$ have non-zero elements. These $m$ rows have only six non-...
- 1,277