October 9, 2025, 12:15-13:15
Room LEE D 105

Gabriel Provencher Langlois - "Exact and efficient basis pursuit denoising via differential inclusions"

Abstract: Basis pursuit denoising (BPDN), also known as the lasso problem or ℓ1-regularized least-squares, is a cornerstone of compressive sensing, statistics and machine learning. While various algorithms for BPDN have been proposed, they invariably suffer from drawbacks and must either favor efficiency at the expense of accuracy or vice versa. As such, state-of-the-art algorithms remain ineffective for high-dimensional applications requiring accurate solutions within a reasonable amount of computational time. In this talk, I will present an exact and efficient algorithm for BPDN based on differential inclusions that overcome these drawbacks. Specifically, I will prove that a selection principle from the theory of differential inclusions turns the dual problem of BPDN into calculating the trajectory of an integrable projected dynamical system, that is, whose trajectory and asymptotic limit can be computed exactly. The analysis naturally yields an exact algorithm, numerically up to machine precision, that is also very fast. Numerical experiments confirm that the algorithm outperforms the state-of-the-art algorithms in both accuracy and efficiency. Finally, I will briefly discuss how I expect that the results and analysis can be adapted to compute exact or approximate solutions to a broader class of polyhedral-constrained optimization problems.