12 votes

Finding the sparsest solution to a system of linear equations

Consider the problem $\text{MAX-LIN}(R)$ of maximizing the number of satisfied linear equations over some ring $R$, which is often NP-hard, for example in the case $R=\mathbb{Z}$ Take an instance of ...
user avatar
  • 2,295
7 votes
Accepted

Reducing the bandwidth of non-symmetric matrix

The following article discusses various approaches to reducing the bandwidth of unsymmetric matrices. J.K. Reid, J. A. Scott: Reducing the total bandwidth of a sparse unsymmetric matrix, SIAM Journal ...
user avatar
6 votes
Accepted

Complexity of $\{0,\pm1\}$ determinant in sparse cases?

Depends how you feel about the exponent of matrix multiplication, as this would come very close to showing $\omega=2$. If the answer to your question were positive, then you could compute the ...
user avatar
6 votes

Finding the sparsest solution to a system of linear equations

The problem is NP-complete, by reduction from the following problem: Given an $m\times n$ matrix $A$ with integer entries and an integer vector $b$ with $n$ entries, does there exist a 0-1 vector $x$ ...
user avatar
  • 5,712
4 votes

Finding the sparsest solution to a system of linear equations

This problem is hard, in various settings. As stated in the other answers to this question, the problem is NP-complete over the integers. In signal processing, the matrix and the vectors have ...
user avatar
  • 2,251
4 votes
Accepted

Checking properties of matrices

The Faddeev-Leverrier algorithm seems to be a good start to answer your question, since it reduces the computation of $\alpha_k$ to matrix multiplications and traces. It runs in polynomial time (even ...
user avatar
  • 676
4 votes

Finding the sparsest solution to a system of linear equations

This is called the Sparsest Solution Vector problem, and it is indeed NP-hard.
user avatar
  • 9,378
3 votes
Accepted

Problem conditions to use Laplacian solvers

It's a good question. You can use a Laplacian solver if $A$ is symmetric and diagonally semi-dominant (SDD). This is the subject of Theorem 9.2 in your reference book from Vishnoi. A good exposition ...
user avatar
  • 814
2 votes
Accepted

When is it hard to invert a sparse matrix?

Jacobi or Gauss-Seidel are not really state of the art for solving systems of linear equations. It is more done by preconditioned conjugated gradient (for symmetric positive semi-definite matrices) ...
user avatar
1 vote

The connection between compressed sensing and sparse representation

Consider a real world 'signal' - a discrete set of numbers representing something real (e.g. an image, an audio recording, etc.). These numbers form a vector in some vector space. Any such vector can ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible