Information and System Group

November 5, 2012

1		2014-07-29	Precise Undersampling Theorems	Oliver	(doc)
			The Shannon–Nyquist–Kotelnikov–Whittaker sampling theorem states precise number of measurements required to reconstruct any band limited signal. Undersampling theorems in Compressive sensing (CS) state that we may gather far fewer samples than the usual sampling theorem while exactly reconstructing the object of interest provided the object obeys a sparsity condition. While there are many ways to demonstrate such undersampling phenomena in CS, combinatorial geometry based approach is the only one mathematically rigorous approach to precisely quantify the true sparsity undersampling trade-off curve of standard algorithms and standard compressed sensing matrices. The approach predicts the exact location in sparsity-undersampling domain where standard algorithms exhibit phase transitions in performance.