Event Detail

Event Type: 
Department Colloquium
Date/Time: 
Thursday, February 17, 2022 - 16:00 to 17:00
Location: 
on Zoom

Speaker Info

Institution: 
Johns Hopkins University
Abstract: 

The identification of sparse vectors from few linear measurements is a fundamental technology in data science that is key for variable selection in machine learning as well as in engineering, e.g., for accelerated imaging in a recent generation of magnetic resonance imaging scanners. We present the first global linear convergence result for Iteratively Reweighted Least Squares (IRLS), an algorithmic framework that is suitable to solve large-scale instances of ℓ1-minimization, which is the convex optimization problem at the core of sparse recovery. Furthermore, we present new guarantees for ℓ1-minimization in the presence of heavy-tailed measurement matrices, which include the first result for heavy-tailed measurements in the presence of dictionary-sparse vectors, and which weaken the requirements on entrywise distributions of the measurement matrix in the standard compressed sensing setting. Finally, we show that centrally symmetric random polytopes spanned by heavy-tailed vectors contain large canonical bodies, and present how this implies robust guarantees for noise-blind compressed sensing.