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

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

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.