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:
where is any matrix, is an vector and is an vector. To make this problem underdetermined let . Suppose also that we are searching for the sparsest solution, i.e. a solution 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 elements of , 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 to be, say, (i.e., has ones), which ofcourse is not sparse at all
- Let and find all such that . Let be the enumeration of these sets
- for each do the following
- Solve the linear system in which
- 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:
when , we get, after solving the remaining system of equations, . So, the sparsest solution possible has three zeros (as all ‘s cannot be zero evidently). The important point here is that, to obtain this solution, one has to check for each and every , 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 and large we know that this value becomes very huge.
First question here is, what is the order of in terms of when ? Atleast in the simple case when is even and , it can be shown that this value grows faster than . A proof is given below:
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.