Linear and quadratic programming for sparse signal recovery
In this work, we consider the problem of sparse signal recovery known as compressed sensing using $\ell_1$-minimization. We show how the $\ell_1$-minimization problem (also known as basis pursuit) can be transformed into an equivalent linear programming (LP) problem, and provide a proof of the equivalence of these two problems. We conduct an experimental comparison of modern solvers (Gurobi, HiGHS, CPLEX, and Clarabel) for solving the LP problem on test data generated according to theoretical recovery guarantees for matrices with normally distributed elements. The results show that the open-source solver Clarabel is a competitive alternative to proprietary solvers in terms of speed. We also propose a method for verifying the uniqueness of the obtained solution using an auxiliary quadratic programming problem with a strictly convex objective function. A geometric interpretation of the uniqueness conditions is provided, and the application of the method is demonstrated on an example of a matrix with integer elements.