Underdetermined system of equations arise in some practical applications and this blog is about a very naive attempt to solve them when the solutions are restricted to be sparse.

Suppose we have the system:

\displaystyle  Ax=y

where {A} is any {N\times  M} matrix, {x} is an {M\times 1} vector and {y} is an {N\times 1} vector. To make this problem underdetermined let {N < M}. Suppose also that we are searching for the sparsest solution, i.e. a solution {x} with the maximum number of zeros.

The most straight forward way to find all those sparse solutions is to extract all the possible sets of {M-N} elements of {x}, set them to zero, and solve the remaining linear system. That might not have been very clear, so, look at this detailed algorithm:

  • Initialize the sparsest solution {x} to be, say, {x=(1,1,\cdots,1)} (i.e., {x} has {M} ones), which ofcourse is not sparse at all
  • Let {\Omega=\{1,2,\cdots,M\}} and find all {S \subset  \Omega} such that {|S|=M-N}. Let {S_i, \forall i \in \{1,2,\cdots \binom{M}{M-N}\}} be the enumeration of these sets
  • for each {i \in  \{1,2,\cdots \binom{M}{M-N}\}} do the following
    • Solve the linear system in which {x_j = 0, \forall j  \in S_i}
    • if the obtained solution is sparser than the one we have up to now, update the sparse solution

Based on the above example, consider this example:

\displaystyle  \begin{array}{rcl}  2x_1 +  3x_2 + 2x_3 + x_4 &=& 2\\ 2x_1 + 3x_2 + 4x_3 - x_4 &=& 4  \end{array}

when {x_1=0, x_2=0}, we get, after solving the remaining system of equations, {x_3=1,x_4=0}. So, the sparsest solution possible has three zeros (as all {x_i}‘s cannot be zero evidently). The important point here is that, to obtain this solution, one has to check for each and every {i \in \{1,2,\cdots \binom{M}{M-N}\}}, which is not very practical. (I am not sure if it can be done any more cleverly but I am assuming this algorithm shows the general properties of all the possible algorithms which solve this problem.). For example, when {N\approx \frac{M}{2}} and {M} large we know that this value becomes very huge.

First question here is, what is the order of {\binom{M}{N}} in terms of {M} when {N\approx \frac{M}{2}}? Atleast in the simple case when {M} is even and {N=\frac{M}{2}}, it can be shown that this value grows faster than {2^{\frac{M}{2}}}. A proof is given below:

\displaystyle  \begin{array}{rcl}   \binom{2r}{r} &=& \frac{(r+1) * (r+2) * \cdots *  2r}{1*2*\cdots*r}\\ &=&\frac{r+1}{1}*\frac{r+2}{2}* \cdots  *\frac{2r-1}{r-1} *\frac{2r}{r}\\ &\geq& 2*2*\cdots*2*2\\  &=&2^r \end{array}

Hence, the algorithm described above would take an exponential time to run. It seems it can be shown that this problem is NP-complete. Any comments on how to show this are ofcourse welcome.