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.