Computational Mathematics and Scientific Computing Seminar

Time and Location:

Speaker:

Link:

Basis Pursuit Denoising (BPDN) is a cornerstone of compressive sensing, statistics and machine learning. Its applicability to high-dimensional signal reconstruction, feature selection, and regression problems has motivated much research and effort to develop algorithms for performing BPDN effectively, yielding state-of-the-art algorithms via first-order optimization, coordinate descent, or homotopy methods. Recent work, however, has questioned the stability, accuracy and efficiency of these state-of-the-art algorithms for BPDN. For example, the glmnet package for BPDN, which is state-of-the-art due to its claimed efficiency, suffers from instability and can yield inaccurate solutions that lead to many so-called false discoveries. Another example is existing homotopy methods for BPDN; most require technical assumptions that may not hold in practice to compute exact solution paths. Without a stable, exact, and fast algorithm, these shortcomings will continue to hinder BPDN for high-dimensional applications. In this talk, I will present a novel homotopy algorithm based on differential inclusions that is stable and performs BPDN exactly (numerically, up to machine precision). I will also present some numerical experiments to illustrate the efficiency of our algorithm and discuss various theoretical implications of our algorithm.