12
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 this problem, $Ax=b$ where $A$ is a $n\times m$ matrix. Let $k=m+1$. Construct a new linear system $\tilde{A}\tilde{x} = \tilde{b}$, where $\tilde{A}$ is a $kn ...
7
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 on Matrix Analysis and Applications 28(3):805–821.
The technical report version of the article is available here:
J. K. Reid and J. A. Scott, Reducing ...
6
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$ with $Ax=b$?
For every coordinate $x_i$ of vector $x$,
introduce $100(n+m)$ new equations $x_i+y_{i,k}=0$ with $k=1,\ldots,100(n+m)$, and
introduce $100(...
6
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 determinant of an arbitrary symmetric $n \times n$ $\{0,1\}$ matrix $M$ (=adjacency matrix of an undirected graph, possibly with self-loops) in $O(n^2)$ time. As the ...
4
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 in NC) and I guess any efficient treatment of sparse matrix operation carries to this algorithm.
Oddly enough the wikipedia page about that exists only in ...
4
This is called the Sparsest Solution Vector problem, and it is indeed NP-hard.
4
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 rational entries, and this problem is sometimes called the sparse reconstruction problem. In this setting, the problem is NP-complete (see Theorem 1).
In coding ...
2
In the proof of theorem 2 in Improved Approximation Algorithms for Rectangle Tiling and Packing by Berman et al, they proved an upper bound of $\frac{11}{5} \max\{W/p,y\}$, where $W$ is the sum of the weight of all elements, $p$ is the number of rectangles and $y$ is the weight of the largest element.
This implies a upper bound of $\frac{11}{5j}$ for your ...
1
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 be transformed into many different bases. The vector will be more 'sparse' in some of those bases than others. In fact, there's even a set of bases where the ...
Only top voted, non community-wiki answers of a minimum length are eligible
