Fast First-Order Methods for Large-Scale Structured and Sparse Optimization

用于大规模结构化和稀疏优化的快速一阶方法

• 批准号: 1016571
• 负责人: Donald Goldfarb
• 金额: $ 45万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2014-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1016571&HistoricalAwards=false
• 关键词: Fast; First; Order; Methods; Large

Algorithms for large-scale optimization have traditionally exploitedsparsity and structure in problem data. Many important optimization problems today, such as those that arise in statistical machine learning (ML) and in compressive sensing (CS) are extremely large-scale convexproblems with completely dense and/or unstructured problem data. However, there is often sparsity and structure in the solutions to these problems. The goal of this research project is the development offirst-order algorithms, including gradient methods for non-smooth functions,smoothed penalty methods for constrained problems, multiple splitting methods,alternating-direction augmented-Lagrangian methods, andblock coordinate descent methods, for extremely large-scale convex optimization problems that take advantage of solution structure and/or sparsity. Rigorous convergence analysis for these methods will be provided androbust software implementations will be developed. Although these methods are expected to have wide applicability, the focus will be on applications in CS and ML. Specifically, the investigators propose to develop and analyze new scalable algorithms for (i) CS signal recovery, including algorithms that are able to exploit more detailed a priori knowledge in addition to sparsity; (ii) matrix rank minimization, the matrix analog of CS, and its variants; and (iii) a broad array of ML problems that exploit the special sparsity/structure of the solutions to these problems.The research that is proposed under this grant is focused on the development of algorithms with provable performance guarantees that are capable of solving extremely large scale optimization problems whose solutions are either sparse or have special structure. Such problems arise under the paradigm of compressive sensing, which allows signals (e.g., radar) and images (e.g., CT and MRI scans) to be obtained with far fewer measurements than predicted by traditional theory, various extensions of CS, and in a broad array of problems in machine learning. All of these problems are aimed at extracting a "sparse" or low-dimensional true model from a high dimensional or dense empirical model or data. They have important applications in extracting information from surveillance video and hyper-spectral images, face recognition, medical imaging and data mining,as well as many other areas of strategic interest such as national security and biotechnology.

大规模优化算法传统上利用问题数据的稀疏性和结构。当今许多重要的优化问题，例如统计机器学习（ML）和压缩感知（CS）中出现的问题，都是具有完全密集和/或非结构化问题数据的超大规模凸问题。然而，这些问题的解决方案往往是稀疏和结构化的。本研究计划的目标是发展一阶算法，包括非光滑函数的梯度法、约束问题的平滑罚函数法、多重分裂法、交替方向增广拉格朗日法和块坐标下降法，以解决利用解结构和/或稀疏性的超大规模凸优化问题。这些方法的严格收敛分析将提供androbust软件实现将开发。虽然这些方法预计将具有广泛的适用性，但重点将放在CS和ML中的应用上。具体来说，研究人员建议开发和分析新的可扩展算法（i）CS信号恢复，包括能够利用更详细的先验知识，除了稀疏算法;（ii）矩阵秩最小化，CS的矩阵模拟，及其变体;和（iii）一系列广泛的ML问题，利用特殊的稀疏性/这些问题的解决方案的结构。根据该资助提出的研究重点是开发具有可证明性能保证的算法，这些算法能够解决超大规模优化问题，其解决方案要么稀疏要么有特殊的结构。 这种问题在压缩感测的范例下出现，压缩感测允许信号（例如，雷达）和图像（例如，CT和MRI扫描）的测量结果要比传统理论、CS的各种扩展以及机器学习中的一系列问题所预测的要少得多。所有这些问题的目的都是从高维或密集的经验模型或数据中提取“稀疏”或低维的真实模型。它们在从监控视频和高光谱图像中提取信息、人脸识别、医学成像和数据挖掘以及国家安全和生物技术等许多其他战略利益领域都有重要应用。