Ill-posed and underdetermined systems of linear equations arise in many applications ranging from healthcare to signal processing. Extensive research in the last decade has proven that ?structured? signals can be recovered ?accurately?, even if the number of observations is less than the signals? dimensions. Despite the existence of many complex structures in real-world signals, the scope of structured signal recovery has mainly remained limited to basic structures, such as sparsity and low-rankness. Extending the notion of structure and proposing efficient recovery schemes for such structured signals is one of the major open challenges in signal processing and information theory. Any progress in this direction can potentially impact many application areas such as magnetic resonance imaging (MRI).
This research involves developing a novel and transformative approach to structured signal recovery by addressing the following questions: (i) Do there exist practical and efficient signal recovery algorithms that can recover signals from their undersampled sets of linear measurements with little or no prior information about their structures? Such algorithms are referred to as universal algorithms in information theory. (ii) What are the fundamental performance limits of such universal algorithms? Universal schemes have been developed and are popular in other applications. For instance, universal compression algorithms such as the omnipresent Lempel-Ziv code achieve the optimal performance without requiring any knowledge about the distribution of the data. Recent results, by the PIs and others, theoretically prove the existence of universal signal recovery algorithms. This research investigates the existence and fundamental performance limits of computationally efficient universal recovery algorithms.
