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

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