Sparse and Regularized Optimization

稀疏和正则优化

• 批准号: 0914524
• 负责人: Stephen Wright
• 金额: $ 27.4万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0914524&HistoricalAwards=false
• 关键词: Sparse; Regularized; Optimization

Most algorithmic research in optimization has focused on modelsconsisting of a single objective together with a number ofconstraints, all defined precisely and deterministically, where anexact solution is required. This paradigm is inadequate in manyapplications. First, there is often uncertainty in the model and data;this is being dealt with by a recent upsurge of work in stochastic androbust optimization. Second, users often require a simple approximatesolution rather than a more complicated exact solution. When theproblem is formulated in the appropriate space, simplicity is oftenmanifested as sparsity - the vector of variables has relatively fewnonzeros. Inclusion of nonsmooth regularization terms in theformulation can steer the model toward sparse solutions. This proposalfocuses chiefly on algorithms and theory for sparse and regularizedoptimization, and on application of the methods to such importantareas as compressed sensing, machine learning, computationalstatistics, and image processing. The project also takes ahigher-level view, cross-fertilizing algorithmic ideas acrossdifferent application areas, and devising and analyzing algorithms ingeneral settings that encompass many specific applications. Optimization methods can be used to solve a great variety of practicalproblems, such as design of cancer treatment plans, removing noise andblur from images and videos, identifying genomic and environmentalrisk factors for diseases, and reconstructing pictures, signals, andother data sets from limited random samples. Precise mathematicalformulations of these optimization problems are available, and exactsolutions can often be obtained, but what is needed in many cases is asimple, approximate solution that is easy to compute, understand, andapply. To take one example: Many images can be stored by taking asmall number of random combinations of the pixels that make up theimage. The optimization algorithm that reconstructs the originalpicture from the samples should look for the simplest picture that isroughly consistent with the random observations; this image is likelyto appear more natural than complicated images that give an exactmatch to the data. This project investigates how the mathematicalstatements of problems like this one, and the mathematical methodsthat solve them, can be modified to produce simple solutions.

最优化中的大多数算法研究都集中在由单个目标和多个约束组成的模型上，所有这些约束都是精确和确定的，其中需要精确的解。这一范例在许多应用中是不充分的。首先，模型和数据经常存在不确定性；最近在随机和稳健优化方面的工作热潮正在处理这一问题。其次，用户通常需要一个简单的近似解，而不是更复杂的精确解。当问题在适当的空间中被表述时，简单性通常表现为稀疏性--变量的向量具有相对较少的非零点。在公式中加入非光滑正则化项可以将模型引向稀疏解。本文主要研究稀疏和正则化优化的算法和理论，以及这些方法在压缩感知、机器学习、计算统计和图像处理等重要领域的应用。该项目还采取了更高层次的观点，在不同的应用领域交叉培养算法思想，并在涵盖许多特定应用的一般设置中设计和分析算法。最优化方法可用于解决各种实际问题，如癌症治疗计划的设计，图像和视频中的噪声和模糊去除，识别疾病的基因组和环境风险因素，以及从有限的随机样本重建图片、信号和其他数据集。这些优化问题有精确的数学公式，通常可以得到精确的解，但在许多情况下，需要的是易于计算、理解和应用的简单、近似的解。举个例子：许多图像可以通过取组成图像的像素的少量随机组合来存储。从样本重建原始图像的优化算法应该寻找与随机观测大致一致的最简单的图像；该图像可能比与数据精确匹配的复杂图像看起来更自然。这个项目研究如何修改数学描述，以及解决这些问题的数学方法，以产生简单的解决方案。