International Research Fellowship Program: Stability and Algorithm Analysis in Compressed Sensing

Blanchard Jeffrey D, Salt Lake City UT

Investigators

Abstract

0854991 Blanchard This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5). The International Research Fellowship Program enables U.S. scientists and engineers to conduct nine to twenty-four months of research abroad. The program's awards provide opportunities for joint research, and the use of unique or complementary facilities, expertise and experimental conditions abroad. This award will support a twelve-month research fellowship by Dr. Jeffrey D. Blanchard to work with Dr. Michael E. Davies at the University of Edinburgh in the UK. Compressed sensing is a cutting edge field of applied harmonic analysis and electrical engineering that determines the minimum number of measurements required to capture all the information content contained in a signal. Due to physical constraints, most signals of interest have low information content compared to the signal length. This low information content is translated to an assumption of sparsity, that the signal has relatively few nonzero coefficients. Contrary to the well-known Shannon sampling theorem, compressed sensing has determined that sparse signals can be reconstructed from far fewer linear, non-adaptive measurements. In fact, the number of measurements can be proportional to the information content provided the signal reconstruction algorithm is nonlinear. A primary tool for signal reconstruction in compressed sensing is l1-minimization, a tractable linear programming problem. The restricted isometry property (RIP) has provided sufficient conditions on the measurement ensemble such that l1-minimization will stably reconstruct sparse signals. When the measurements of a sparse signal are contaminated with noise, the reconstruction is stable if it produces a sparse approximation to the signal with error proportional to the noise. A geometric interpretation of the measurement ensemble has provided a necessary and sufficient condition for l1-minimization to reconstruct the signal. However, this geometric interpretation does not produce provably stable signal reconstruction. RIP is too restrictive, and empirical investigation supports stable signal recovery more in line with the geometric interpretation. The principal investigator (PI) will perform stability analysis from the geometric point of view to shrink this theoretical void. Necessary and sufficient conditions on the size of the faces of a poly-tope associated to the measurement matrix will be formulated to ensure stable signal reconstruction from l1-minimization. The research proceeds by identifying measurement ensembles satisfying these conditions. Alternative nonlinear algorithms have been developed which have reduced computational burdens yet still stably recover sparse signals. These algorithms have also been successfully studied using generic measures of sparsity such as RIP. As in the case of l1-minimization, the theory remains far from observation due to the method of analysis not being tied to the behavior of the algorithm. Following a similar research direction, the PI will perform analysis of a hybrid algorithm that forces l1-minimization to act like one of the alternative algorithms. By analyzing the step by step approximations produced by each algorithm, the PI intends to establish provable connections between the theories of l1-minimization and alternative nonlinear algorithms. This research will be conducted at the University of Edinburgh with Professor Michael Davies of the School of Engineering and Electronics. The PI will be embedded with Prof. Davies research group with scientists from electrical engineering, mathematics, optimization, and medical physics. The PI will also be affiliated with a European Union project on sparse approximation and compressed sensing. The interdisciplinary team and European consortium will provide the PI unmatched research experiences and opportunities for international collaboration. Prof. Davies work in medical imaging and compressive radar provide an opportunity for immediate implementation of results. These experiences will help prepare the PI for a successful academic research career in the United States and continued international collaboration.