We begin with a review of compressed sensing and the formulation of the associated combinatorial L0-optimization problem. Using ideas developed for the convex relaxation (L1-minimization), we'll introduce the phase transition framework for comparability of sufficient conditions for guarantees on suboptimal algorithms used to solve the compressed sensing problem. The greedy algorithms in compressed sensing have guarantees based on the restricted isometry property and bounding the restricted isometry constants allows for a translation of sufficient conditions into the phase transition framework. These theoretical, worst-case guarantees are known to be excessively pessimistic, hence an average case analysis is desired. We will conclude the talk with a discussion of our recent GPU implementation of selected greedy algorithms for the purpose of studying the average case performance.
Current 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
