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 ...
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 ...
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$ ...
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 ...
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.
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 ...
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 ...
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) ...
1
vote
Accepted
Could an *implicitly* defined graph be a member of a *strongly-explicit* family of expanders?
Yes! But I can see why it is confusing.
A strongly explicit graph family $\{G_n = (V_n,E_n)\}$ (parameterized e.g. by number of vertices $n$) is described by an efficient ($\mathrm{polylog}(n)$ time) ...
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
sparse-matrix × 28matrices × 8
ds.algorithms × 7
linear-algebra × 7
graph-algorithms × 6
reference-request × 3
graph-theory × 3
na.numerical-analysis × 3
matrix-product × 3
compressed-sensing × 3
cc.complexity-theory × 2
np-hardness × 2
approximation-algorithms × 2
optimization × 2
linear-programming × 2
convex-optimization × 2
linear-equations × 2
quantum-computing × 1
automata-theory × 1
time-complexity × 1
ds.data-structures × 1
machine-learning × 1
pr.probability × 1
randomized-algorithms × 1
functional-programming × 1