The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
67 views

Asymptotic eigenvalue analysis for a sparse random matrix

We have an asymptotic analysis problem for the eigenvalue performance of the following random matrix: $H=\{h_{ij}\}_{N_r\times N_t}$, where each entry $h_{ij}$ is with a probability $p$ to obey the ...
6
votes
1answer
134 views

Hamiltonicity criteria for sparse graphs

Given a sparse graph, how can one go about proving that it is Hamiltonian? (Assuming it actually is, of course). There are three main classes of criteria for Hamiltonicity that I am aware of: ...
1
vote
1answer
121 views

Estimate the determinant of sparse 0-1 matrix

There is a matrix A where each entry is either 0 or 1. Each column has exactly a 1's and each row has at most b 1's. What's the upper bound of abs(|A|)? The condition is stronger than the Hadamard's ...
1
vote
1answer
106 views

Transform $a\mathbf x+\mathbf b$, then make it $k$-sparse, resulting least modification?

Consider vector $\mathbf x = (x_1,x_2,\cdots,x_n)$, $a$ a scalar, $\mathbf b = (b_0,\cdots,b_0)$ and $k < n$. I want to transform $\mathbf x$ ($\mathbf y = a\mathbf x+\mathbf b$) such that if I ...
2
votes
0answers
174 views

Inverse of sparse matrix is not generally sparse [closed]

I have a question regarding inverse of square sparse matrices(or can be restricted to real symmetric positive definite matrices). I encountered several times the web pages which states that the ...
1
vote
1answer
199 views

probability of having linearly independent sparse vectors over finite fields

Suppose that there are $i< N$ linearly independent $N$-dimensional vectors $\mathbf{v}_1,\mathbf{v}_2,\ldots,\mathbf{v}_i$ over a finite field $\mathbb{F}_q$, whose elements are denoted as ...
1
vote
1answer
154 views

sparse binary vector

I want to know if the following problem has been solved max_w w'Rw where the entries of the vector w are binary (w_i= {0,1} )
0
votes
1answer
174 views

$\ell_o$ Minimization (Minimizing the support of a vector)

I have been looking into the problem $\min: \|x \|_0$ subject to$: Ax=b$. $\|x \|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current form. Most of my time ...
8
votes
4answers
3k views

Eigenvectors and eigenvalues of Tridiagonal matrix

Hi, is it possible to analytically evaluate the eigenvectors and the eigenvalues of a tridiagonal matrix of the form : $$ \mathcal{T}^{a}_n(p,q) = \begin{pmatrix} 0 & q & 0 & 0 ...
2
votes
1answer
408 views

minimizing functions over simple matrix inequalities

I'm wondering if anything is known about minimizing convex, not necessarily linear functions subject to "simple" matrix equalities. To be precise, consider the following example: $min \Sigma x_i ln ...
0
votes
0answers
211 views

L1-regularized Least Squares on a matrix with Toeplitz Blocks (not block-Toeplitz)

I am trying to speed up a sparse signal recovery algorithms. My sensing matrix is a set of Toeplitz Blocks, M = [T1,T2,T3,...,Tk] The objective is min ||Mx - b||_2^2 + ||x||1 What I'm actually ...
5
votes
5answers
1k views

Computer algebra system for calculation of characteristic polynomial of sparse matrix

I have a $n \times n$ matrix, for which i need to calculate the characteristic polynomial. The matrix is over $GF(2)$, and $n \approx 10^4$. However the matrix is very sparse, with around $ n $ non ...
2
votes
0answers
236 views

Sparse Eigenvectors for the Discrete Fourier Transform matrix

There are many ways to choose eigenbasis for the Discrete Fourier Transform matrix since it has only $4$ distinct eigenvalues taken from $\{\pm 1,\pm i\}$. Has there been any refereed work that ...
0
votes
2answers
826 views

How to accelerate/avoid multiplication for large matrices in Matlab? [closed]

The setting is here. X: 6000x8000 non-sparse matrix B: 8000x1 sparse vector with only tens of non-zeros d: positive number M: is sparsified X'X, i.e. thresholding the elements smaller than d ...
5
votes
1answer
503 views

Are there interesting problems involving arbitrarily long time series of small matrices?

Are there well-known or interesting applied problems (especially of the real-time signal processing sort) where arbitrarily long time series of small (say $d \equiv \dim \le 30$ for a nominal bound, ...