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

国际研究奖学金计划：压缩感知的稳定性和算法分析

• 批准号: 0854991
• 负责人: Jeffrey Blanchard
• 金额: $ 10.88万
• 依托单位: Blanchard Jeffrey D
• 依托单位国家: 美国
• 项目类别: Fellowship Award
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-01-01 至 2010-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0854991&HistoricalAwards=false
• 关键词: International; Research; Fellowship; Program; Stability

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.

0854991 Blanchard该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。国际研究奖学金计划使美国科学家和工程师能够在国外进行9到24个月的研究。 该计划的奖项提供了联合研究的机会，以及使用独特或互补的设施，专业知识和国外的实验条件。布兰查德将与迈克尔·E博士合作。压缩感知是应用谐波分析和电气工程的前沿领域，它确定捕获信号中包含的所有信息内容所需的最少测量次数。 由于物理约束，与信号长度相比，大多数感兴趣的信号具有低信息内容。这种低信息含量被转换为稀疏性的假设，即信号具有相对较少的非零系数。与众所周知的香农采样定理相反，压缩感知已经确定稀疏信号可以从少得多的线性非自适应测量中重建。 事实上，如果信号重构算法是非线性的，则测量的数量可以与信息内容成比例。 压缩感知中信号重构的主要工具是l1最小化，这是一个易于处理的线性规划问题。限制等距性质（RIP）提供了充分的条件上的测量合奏，使得l1-最小化将稳定地重建稀疏信号。当稀疏信号的测量被噪声污染时，如果重建产生与噪声成比例的误差的信号的稀疏近似，则重建是稳定的。测量集合的几何解释提供了l1-最小化重建信号的充分必要条件。然而，这种几何解释不产生可证明稳定的信号重建。RIP是过于限制，和实证研究支持稳定的信号恢复更符合几何解释。主要研究者（PI）将从几何角度进行稳定性分析，以缩小该理论空隙。与测量矩阵相关联的多面体的面的大小的必要和充分条件将被制定，以确保稳定的信号重建从l1-最小化。研究的进展，确定满足这些条件的测量合奏。 替代的非线性算法已经被开发，其减少了计算负担，但仍然稳定地恢复稀疏信号。这些算法也已成功地研究了使用通用的稀疏性措施，如RIP。在l1最小化的情况下，由于分析方法与算法的行为无关，理论离观察还很远。遵循类似的研究方向，PI将对一种混合算法进行分析，该算法迫使l1-最小化像替代算法之一一样发挥作用。通过分析每个算法产生的逐步近似，PI打算在l1-minimization理论和替代非线性算法之间建立可证明的联系。这项研究将在爱丁堡大学与工程和电子学院的Michael Davies教授一起进行。PI将嵌入Davies教授的研究小组，该研究小组的科学家来自电气工程、数学、优化和医学物理学。PI还将与欧盟稀疏近似和压缩传感项目建立联系。跨学科团队和欧洲联盟将为PI提供无与伦比的研究经验和国际合作机会。Davies教授在医学成像和压缩雷达方面的工作为立即实施结果提供了机会。这些经验将有助于PI准备在美国成功的学术研究生涯和持续的国际合作。