On minimal support solutions of underdetermined systems of linear equations
Is Version Of
This paper explores the nature and application of minimal-support solutions of underdetermined systems of linear equations. First, methods for directly solving the problem are evaluated for effectiveness, and cases are shown to demonstrate that these direct methods are unreliable for finding minimal support solutions. The NP-Hardness of minimal-support solution recovery is then demonstrated over any field for the first time in the literature, and further NP-Hardness results are explored after this presentation. Following these expositions, a summary of current techniques in the practice of Compressive Sensing is given, and a novel method for comprehensively solving minimal-support solutions of underdetermined systems over any field is stated, discussed and proven. A summary of findings and avenues for future opportunities concludes the dissertation.