Second-order methods for large-scale optimization in compressed sensing

压缩感知大规模优化的二阶方法

• 批准号: 0811106
• 负责人: Jennifer Erway
• 金额: $ 14.49万
• 依托单位: Wake Forest University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-07-15 至 2012-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0811106&HistoricalAwards=false
• 关键词: Second; order; methods; large; scale

Nonlinear image reconstruction based upon sparse representations of signals and images has received widespread attention recently with the advent of compressed sensing. This emerging theory indicates that, when feasible, judicious selection of the type of distortion induced by measurement systems may lead to dramatically improved inverse problem solutions. In particular, when the signal or image of interest is very sparse (i.e., zero-valued at most locations) or highly compressible in some basis, relatively few indirect observations are necessary to reconstruct the most significant non-zero signal components. Compressed sensing theory states that sparse signals can be recovered very accurately with high probability from indirect measurements by solving an appropriate optimization problem. This research aims at the development of significantly more efficient methods for solving compressed sensing minimization problems. A crucial property of the proposed methods is that the algorithms are designed to be "matrix-free", i.e., they do not require the storage of (potentially very large) second-derivative matrices. Instead, these methods use matrices only as operators for matrix-vector products.This research also includes the application of the developed solvers to real large-scale problems from image processing (e.g., coded aperture superresolution, hyperspectral image reconstruction, and compressive video reconstruction), as well as theoretical proofs of convergence and numerical stability of the algorithms."Compressed sensing" is an emerging field in computational mathematics that aims to improve signal (and image) reconstruction with less data. More efficient methods for compressed sensing can benefit such fields as medical imaging, astrophysics, biosensing, and geophysical data analysis. The basic theory exploits the fact that many natural signals in science and engineering are "sparse"--that is, they can be represented as a weighted combination of a small subset of commonly occurring signals. When a signal is sparse, scientists can accurately reconstruct the original signal using a relatively small number of measurements of the original signal. However, in practice finding the right weighted combination of signals can create staggering numerical and computational complexity. This research aims to develop novel optimization methods that can quickly find accurate solutions to these large-scale problems. For example, consider an astronomer wishing to image the night sky, which consists of small, bright stars against a dark background. A conventional digital camera or imaging system would need a very high resolution and sensitive photodetector to effectively localize the different stars, but collecting this large number of pixels can be very costly and energy inefficient. This work allows the astronomer to collect a relatively small number of random projection measurements of the scene and use these to reconstruct the image with a high probability of accuracy. Fast and accurate optimization algorithms for sparse signal reconstruction can impact many other areas of image and signal processing as well, from reducing the dose of CT scans in biomedical imaging and improving image resolution in video surveillance systems for airport security, to more efficiently transmitting communication signals from distant satellites and NASA spacecraft and more carefully monitoring the health of a forest ecosystem using hyperspectral imaging.

近年来，随着压缩感知技术的出现，基于信号和图像稀疏表示的非线性图像重建得到了广泛的关注。这一新兴理论表明，在可行的情况下，明智地选择由测量系统引起的失真类型可能会导致显着改善反问题的解决方案。特别地，当感兴趣的信号或图像非常稀疏时（即，在大多数位置为零值）或在某些基础上高度可压缩，因此需要相对较少的间接观测来重构最重要的非零信号分量。压缩感知理论指出，稀疏信号可以通过解决适当的优化问题从间接测量中以高概率非常准确地恢复。本研究旨在开发更有效的方法来解决压缩感知最小化问题。所提出的方法的一个关键特性是算法被设计为“无矩阵”，即，它们不需要存储（可能非常大的）二阶导数矩阵。相反，这些方法只使用矩阵作为矩阵向量乘积的运算符。这项研究还包括将开发的求解器应用于图像处理的真实的大规模问题（例如，编码孔径超分辨率、超光谱图像重建和压缩视频重建），以及算法的收敛性和数值稳定性的理论证明。“压缩感知”是计算数学中的一个新兴领域，旨在用更少的数据改善信号（和图像）重建。更有效的压缩感知方法可以使医学成像、天体物理学、生物传感和地球物理数据分析等领域受益。 基本理论利用了这样一个事实，即科学和工程中的许多自然信号是“稀疏的”-也就是说，它们可以表示为一个小的子集，通常发生的信号的加权组合。 当信号稀疏时，科学家可以使用原始信号的相对少量的测量来精确地重建原始信号。 然而，在实践中，找到正确的加权信号组合可能会产生惊人的数值和计算复杂性。 这项研究旨在开发新的优化方法，可以快速找到这些大规模问题的精确解决方案。 例如，考虑一个天文学家希望对夜空成像，夜空由黑暗背景下的小而明亮的星星组成。 传统的数码相机或成像系统需要非常高分辨率和灵敏的光电探测器来有效地定位不同的恒星，但收集大量的像素可能非常昂贵且能源效率低下。 这项工作使天文学家能够收集相对少量的场景随机投影测量值，并使用这些数据以高精度重建图像。 用于稀疏信号重建的快速准确的优化算法也可以影响图像和信号处理的许多其他领域，从减少生物医学成像中的CT扫描剂量和提高机场安全视频监控系统中的图像分辨率，到更有效地传输来自远程卫星和NASA航天器的通信信号，以及使用高光谱成像更仔细地监测森林生态系统的健康状况。