4
$\begingroup$

Given a matrix $A \in F^{n \times m},$ $m\gg n,$ and a given $b \in F^n,$ with $F$ any (possibly finite) field, is there an algorithm that approximates the size of the minimal support solution for the system $Ax=b?$

I asked this question yesterday during an (otherwise unusual) conversation with my advisor, after he noticed that brute-force methods for finding solutions as minimal as possible yield solutions with $\|x\|_0 \ll n;$ for instance, he mentioned that for some randomly generated matrix with ten thousand rows and two hundred thousand columns, and for some randomly generated vector with ten thousand entries, vector solutions with weight $\|x\|_0 \approx 20$ were found.

He said something about the support vectors being "very close" without specifying what that meant; perhaps $\|A_j-A_k\|_2$ small with respect to that distance for unsupported columns.

Since yesterday, I have started thinking about this question as another possible piece of my dissertation, and would appreciate any direction to literature addressing algorithms that can approximate the size of minimal support solutions quickly, or generate approximate minimal support solutions. I know Donoho has a paper utilizing the approximate $\ell_1$ minimization solution, but I do not know if any techniques exist for minimal support approximation for matrices over finite fields, or if any other approximation techniques have been published.

Thank you in advance for pointing in the direction of any literature or open questions along these lines — exploring this question would be very helpful for my dissertation!

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you have to find an $x$ so that $Ax=b$, or can you be content with $Ax \approx b$ for some measure of error? $\endgroup$
    – usul
    Commented Sep 30, 2016 at 13:30
  • $\begingroup$ Some measure of error could be acceptable. $\endgroup$
    – Thomas Rasberry
    Commented Sep 30, 2016 at 17:56

2 Answers 2

Reset to default
4
$\begingroup$

The problem you want to solve reduces to "exact cover by 3-sets" and is therefore NP-hard in general. The following proves this in the case $F=\mathbb{R}$, but the proof holds for an arbitrary field:

B. K. Natarajan, Sparse approximate solutions to linear systems, SIAM J. Comput. 24 (1995) 227–234.

In the cases where $F=\mathbb{R}$ or $\mathbb{C}$, the problem can be solved in polynomial time when $A$ is drawn at random (with high probability, and for several choices of probability distribution). As you indicated, the sparsest solution can be found by L1 minimization in these cases. This is the subject of compressed sensing, which was developed over the last decade after the seminal work of both Donoho and Candes, Romberg and Tao. See the following book for an introduction to this theory and a thorough survey of the vast literature:

S. Foucart, H. Rauhut, A mathematical introduction to compressive sensing, Birkhäuser, 2013.

I am not as familiar with the finite field setting. Unfortunately, much of the theory of compressed sensing leverages norms and inner products, which are not present in this setting.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for your reply! I think that $\mathbb{R}$ or $\mathbb{C}$ would be an acceptable setting at this stage - since the problem is, indeed, NP-Hard, then I would want to see if there are any relaxation methods or approximate methods that I could connect to this problem (even over a finite field for relaxation/approximation). I was thinking, possibly, branch-and-bound or relating it to integer programming, somehow. $\endgroup$
    – Thomas Rasberry
    Commented Sep 30, 2016 at 13:17
2
$\begingroup$

A numerical method and several studies are given in

Exact and Approximate Sparse Solutions of Underdetermined Linear Equations, SIAM J. Sci. Comput., 31(1), 23–44. Sadegh Jokar and Marc E. Pfetsch, DOI:10.1137/070686676

They solve for all sparsest solutions (even if these are not unique) but only up to dimensions in some tens. However, I do not know of any other study doing $\ell^0$ minimization with guarantees in the realm of problems where $\ell^1$ is not equivalent.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .