Mustafa Devrim Kaba – “Abstract Simplicial Complexes and Generalized Nullspace Property”
“Abstract Simplicial Complexes and Generalized Nullspace Property”
Abstract: In this talk we are going to discuss an alternative view point on why, how and when sparse recovery via l1-minimization (a.k.a. Basis Pursuit) works. By generalizing a well-known necessary and sufficient condition for the success of l1-minimization — namely the Nullspace Property — we will arrive at a characterization of the largest sparsity pattern that can be recovered for a given dictionary/measurement matrix. We coin a name for this largest object and call it “the maximum abstract simplicity complex associated with a dictionary” (Tmax). We will show how Tmax admits alternative characterizations in terms of certain extreme points and points of minimal support. Then, we will show how these characterizations become extremely useful when characterizing the largest sparsity patterns that can be recovered for various popular dictionary classes. In particular, we are going to present the graph incidence matrices and (partial) Discrete Fourier transform as show cases.
This is a joint work with Rene Vidal, Daniel Robinson and Enrique Mallada.
Bio: Mustafa Devrim Kaba is an Assistant Research Scientist at the Applied Mathematics and Statistics Dept. of JHU. He had his PhD degrees from Middle East Technical University (Ankara,Turkey) in Arithmetic Algebraic Geometry (2011) and later in Systems and Control Theory (2014) from University of Groningen (Groningen, the Netherlands). He worked at Computer Vision and Image Analytics Lab of General Electric Global Research Center (Niskayuna, NY) for three years before joining JHU in 2017.