6
votes
Accepted
Usage and origin of the terms dictionary and atom in compressed sensing
The terms "dictionary" and "atoms" predate compressed sensing, they are more generally used in signal processing. An example is the Gabor atom for wavelets. For an early use of &...
- 188k
6
votes
Accepted
How can one construct a sparse null space basis using recursive LU decomposition?
On the LUQ decomposition
The algorithm implemented in luq (see reference given below) computes bases for the left/right null spaces of a sparse matrix $A$. ...
- 6,045
5
votes
How can one construct a sparse null space basis using recursive LU decomposition?
Not the same algorithm, but here is an alternative that I have used in a recent paper; you can put it together quickly with standard Matlab functions if $A$ is a $m\times n$ matrix with $m\ll n$ (like ...
- 20.2k
5
votes
Accepted
In a large sparse matrix, how many eigenvalues/eigenvectors are “spurious”?
Antisymmetric matrices are normal, hence they can be diagonalized with an orthogonal matrix. So $\|A\|_F^2=\sum |\lambda_i|^2$. If you keep only the $k$ largest eigenvalues (ordered in modulus: $|\...
- 20.2k
4
votes
Accepted
Square root of a large sparse symmetric positive definite matrix
I completely agree with fedja: there is a nice method here (which, unfortunately, does not always work well). If you know bounds for the spectrum of $A$, say $0<a<\lambda<b$, then you (...
- 6,891
4
votes
Accepted
Solving linear system when one eigenvalue is known
Yes and no.
If you modify slightly the implementation of a Krylov subspace method such as GMRES, you can construct a method with a projection subspace that contains the known eigenvector. This ...
- 20.2k
3
votes
Decomposing a matrix into a product of sparse matrices
The question of deciding if a specific matrix is a product of "a few" "sparse" matrices seems very interesting to me and perhaps rather hard.
Likewise the question of how bad things could be if the ...
- 30.1k
3
votes
Expected spectral radius for a sparse Erdős-Rényi binary matrix with a certain density
If you mean that $A$ is the adjacency matrix of an Erdos-Renyi random graph, then the question has been studied, and your conjecture is false (but just barely). See
Krivelevich, Michael; Sudakov, ...
- 96.4k
3
votes
Decomposition of rectangular matrices into a product of a sparse and a small matrices
I do not know yet how to solve your question, but there is a similar question with the same difficulty that allows a nice solution. Note that you are basically asking whether we can efficiently find a ...
- 61.9k
3
votes
Accepted
Parametrising a sparse orthogonal matrix
The smallest number of nonzero entries in an $n\times n$ fully indecomposable$^*$ orthogonal matrix is $4n−4$. A method to construct such a matrix is described in Sparse orthogonal matrices (2003).
$^...
- 188k
3
votes
Parametrising a sparse orthogonal matrix
The four-argument version of Matlab's sprand can generate a sparse orthogonal matrix, with suitable arguments. According to the documentation,
[the matrix] is ...
- 20.2k
2
votes
LASSO problem but with a maximization instead of minimization
That problem does not have a maximum. Unless $A$ or $k$ are zero, you can take $\alpha = Me_j$, where $e_j$ is a vector of the canonical basis, and then the objective function diverges when $M \to \...
- 20.2k
2
votes
Existence of sparse LU decomposition of sparse matrix
It seems that the answer is that with high probability, a random sparse matrix (for an appropriate choice of probability distribution over matrices) does not have a sparse decomposition in this sense. ...
- 547
1
vote
Relation between the algebraic multiplicity of an eigenvalue and the subdiagonal elements of a symmetric tridiagonal matrix
The most natural explanation for this (in my view) lies in the fact that the eigenvectors of such a matrix solve a difference equation. More precisely, if we write $T_{nn}=b_n$, $T_{n,n+1}=T_{n+1,n}=...
- 24.2k
1
vote
Accepted
Probability of accurate sparse recovery
A good starting point is "Mathematics of sparsity (and a few other things)" by E. Candes, or a book on compressed sensing such as "A Mathematical Introduction to Compressive Sensing&...
- 1,724
1
vote
Accepted
How sparse can a matrix mapping between sparse vectors be?
$||v||_0$, so $\leq d-s$: The matrix $A$ needs to have at least one entry for every entry of $v$ (otherwise it can't obtain that entry). It is also sufficient to have so many entries, as if we ...
- 111
1
vote
Covering number in the space of symmetric matrices
One answer for the second case. We can see that we have to look at (for $k \in \mathbb{N}$):
\begin{equation}
\mathcal{M}=\{\Theta \in S_n^{++}(\mathbb{R})| \ \|\Theta\|_0 \leq n +2k, \|\Theta\|_F \...
- 407
1
vote
Accepted
What is the big-O complexity of solving the sparse Laplace equation in the plane?
I'm not sure if this is the final answer, but this paper claims that $O(n^{1.5})$ FLOPS with $O(n\log n)$ storage, is best possible across all possible reorderings of the rows and columns of $A$.
This ...
- 981
1
vote
Sparse, left-looking LU factorization
I was confused -- the algorithm does not produce sorted columns, only topologically sorted ones. To obtain a bona fide matrix, one must use e.g. the trick of transposing it twice.
- 2,519
1
vote
Spectrum of finite-band random matrices?
Yes, convergence to a limiting empirical measure $\mu_\infty$ is well known . Let $L\in \mathbb{N}$, (we will chose $1\ll L \ll n$) and define $Y$ $$Y_{i,j}=\begin{cases}X_{i,j} \text{ if } \exists k\...
- 4,361
1
vote
Sparse matrix approximation using only a few dense columns (or rows)
Since this is getting bumped to the home page, I'll turn my comment into an answer.
We have
$$\|A-A_I\|^2_F = \sum_{i \not \in I} \|a_i\|^2,$$
where $a_i$ are the rows of $A$, so it is clear that ...
- 20.2k
1
vote
Exponential of large matrices
I've done 11kx11k matrices in Python with scipy's sparse matrix exponential function in tens of seconds: https://docs.scipy.org/...
- 111
Only top scored, non community-wiki answers of a minimum length are eligible