Groupe d’études et de recherche en analyse des décisions

G-2018-104

Sparse solutions of linear systems via maximum feasible subsets

Algorithms for finding sparse solutions of underdetermined systems of linear equations have been the subject of intense interest in recent years, sparked by the development of compressed sensing, where this is a central problem. There are also reasons for interest in finding sparse solutions for general linear systems of equations and inequalities. This paper describes several new and effective linear-programming-based algorithms for both underdetermined sets of linear equations, and general linear systems, derived from algorithms for solving the maximum feasible subset problem. The algorithms allow greater compression and potentially better denoising in the compressed sensing application, and are the first methods applied to general linear systems. Extensive experimental results are reported.

, 21 pages