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

该奖项由2009年美国复苏和再投资法案(公法111-5)资助。国际研究奖学金计划使美国科学家和工程师能够在国外进行9至24个月的研究。该计划的奖项提供了联合研究的机会，并利用国外独特或互补的设施、专业知识和实验条件。该奖项将支持Jeffrey D.Blanchard博士与英国爱丁堡大学的Michael E.Davies博士合作的为期12个月的研究奖学金。压缩传感是应用谐波分析和电气工程的前沿领域，它确定了捕获信号中包含的所有信息内容所需的最少测量次数。由于物理限制，与信号长度相比，大多数感兴趣的信号具有较低的信息量。这种低信息量被转化为稀疏性的假设，即信号具有相对较少的非零系数。与著名的香农采样定理相反，压缩传感确定了可以从更少的线性、非自适应测量中重构稀疏信号。事实上，如果信号重建算法是非线性的，则测量的数量可以与信息量成正比。压缩感知中信号重构的一个主要工具是L1最小化，这是一个容易处理的线性规划问题。受限等距性质(RIP)为测量系综提供了充分条件，使得L1最小化可以稳定地重构稀疏信号。当稀疏信号的测量值被噪声污染时，如果它产生与噪声成比例的误差的信号的稀疏近似，则重建是稳定的。对测量系综的几何解释为L1最小化重构信号提供了充要条件。然而，这种几何解释并不能产生可证明是稳定的信号重建。RIP过于严格，经验研究支持稳定的信号恢复，更符合几何解释。首席调查员(PI)将从几何角度进行稳定性分析，以缩小这一理论空白。关于与测量矩阵相关的多面体的面的大小的充要条件将被公式化，以确保从L1最小化中稳定地重构信号。研究通过确定满足这些条件的测量集合来进行。已经开发出了替代的非线性算法，它们减少了计算负担，但仍然稳定地恢复稀疏信号。这些算法也已成功地使用稀疏性的通用度量(如RIP)进行了研究。与L1最小化的情况一样，由于分析方法与算法的行为无关，该理论仍远未被观察到。按照类似的研究方向，PI将执行一种混合算法的分析，该混合算法迫使L1最小化起到替代算法之一的作用。通过分析每个算法产生的逐步近似，PI打算在L1最小化理论和可选的非线性算法之间建立可证明的联系。这项研究将在爱丁堡大学与工程和电子学院的Michael Davies教授一起进行。PI将与来自电气工程、数学、优化和医学物理的科学家组成的戴维斯教授研究小组一起嵌入。PI还将隶属于欧盟关于稀疏近似和压缩传感的项目。跨学科团队和欧洲联盟将为国际合作提供无与伦比的研究经验和机会。戴维斯教授在医学成像和压缩雷达领域的工作为立即实施成果提供了机会。这些经验将有助于为PI在美国成功的学术研究生涯和继续国际合作做好准备。

0854991BlanchardThis 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 themethod 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.