CCM Seminar: Stefan Steinerberger

Wednesday Jun 9, 2021, 10:00 AM → 11:15 AM America/New_York

Title:  Exact Support Recovery via (refined) Least Squares

Abstract:   We discuss the problem of exact support recovery in the noisy regime.  Suppose y = Ax + [noise], where A is a (known) random matrix and x is a sparse vector with entries in {-1,0,1}, the goal is to recover x from y.  Recovery is possible even when the linear system is (possibly quite) underdetermined (however, it does strongly depend on the sparsity of x).  I will discuss RLS (refined least squares), a very simple algorithm that can achieve state-of-the-art results.  The main idea behind RLS can easily be implemented in other approaches as well and it seems likely that we have only scratched the surface.  Joint work with Ofir Lindenbaum.