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

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

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.