Minimum L∞ norm solutions to finite dimensional algebraic underdetermined linear systems

Abstract

A new method of solution to the problem of nding the minimum `1 norm solution to an algebraic underdetermined linear system is developed. The new method is a geometrically clear, primal method. Like some existing methods, the new method can be logically divided into two parts. A number of new techniques are suggested in this part of the algorithm, including an iterative ascent procedure. In the second part of the solution process, the particular solution obtained in the rst part is iteratively improved. We have developed a number of new techniques here corresponding to both single and multi-element exchange procedures. Central to the new method is the development of descent criteria for a direction vector, and the stopping condition.The performance of our algorithm is also compared with two well-known methods from the literature. Our method is shown to be much superior to these well known-methods with respect to both the number of iterations and the wall-clock time required. The iterative computational complexity of the new method also compares favourably with most well-known methods. A geometric heuristic is developed for initial active constraint set selection and a number of theoretical results are given. The heuristic stands to be much more valuable if the results presented herein can be generalised