Seminar Details
2024-10-24 (14h) : Alternating projections and Convex infeasibility: theory and applications
At Euler building (room A.002)
Organized by Mathematical Engineering
Speaker :
Luiz-Rafael dos Santos (Universidade Federal de Santa Catarina, Brazil)
Abstract :
In this talk, we first demonstrate that inconsistency arising from the infeasibility of closed convex sets can be leveraged to enhance the performance of alternating projections and their corresponding convergence rates, surprisingly leading to finite convergence under suitable error bounds. In the second part, we apply this concept to develop a new and numerically competitive method for solving the basis pursuit problem. Basis pursuit (BP) seeks the vector with the smallest l1-norm among the solutions to a given linear system, and it is a well-known convex relaxation of the sparse affine feasibility (SAF) problem. SAF aims to find sparse solutions to underdetermined systems, a key issue in compressed sensing, a technique used to recover sparse signals from incomplete measurements. Although SAF is NP-hard, there are instances where its solution coincides with that of BP. The importance of basis pursuit led to a great deal of research into efficient methods for solving it, particularly in large-scale settings, often via linear programming reformulations. However, our approach tackles basis pursuit in its original form, employing a scheme that uses alternating projections within subproblems. These subproblems are purposefully inconsistent, involving two disjoint sets. Numerical experiments show that the proposed algorithm is competitive.