Coordinate Friendly Structures, Algorithms and Applications
Coordinate Friendly Structures, Algorithms and Applications
复制标题
DOI：
10.4310/amsa.2016.v1.n1.a2
复制
发表时间：
2016-01
期刊：
影响因子：
--
通讯作者：
Zhimin Peng;Tianyu Wu;Yangyang Xu;Ming Yan;W. Yin
中科院分区：
文献类型：
--
作者：
Zhimin Peng;Tianyu Wu;Yangyang Xu;Ming Yan;W. Yin
本文主要研究坐标更新方法，这些方法对于解决涉及大维或高维数据集的问题非常有用。它们将问题分解为简单的子问题，每个子问题更新一个或一小块变量，同时修复其他变量。这些方法可以处理线性和非线性映射，光滑和非光滑函数，以及凸和非凸问题。此外，它们很容易并行化。坐标更新方法的良好性能依赖于简单的子问题的求解。为了得到几类新应用的简单子问题，本文系统地研究了执行低成本坐标更新的坐标友好算子。基于所发现的坐标友好算子，以及算子分裂技术，针对机器学习、图像处理以及子优化领域中的各种问题，我们得到了新的坐标更新算法。有几个问题是历史上第一次用坐标更新处理的。通过并行甚至异步计算，所得到的算法可以扩展到大型实例。我们给出了一些数值例子来说明这些算法的有效性。
This paper focuses on coordinate update methods, which are useful for solving problems involving large or high-dimensional datasets. They decompose a problem into simple subproblems, where each updates one, or a small block of, variables while fixing others. These methods can deal with linear and nonlinear mappings, smooth and nonsmooth functions, as well as convex and nonconvex problems. In addition, they are easy to parallelize. The great performance of coordinate update methods depends on solving simple sub-problems. To derive simple subproblems for several new classes of applications, this paper systematically studies coordinate-friendly operators that perform low-cost coordinate updates. Based on the discovered coordinate friendly operators, as well as operator splitting techniques, we obtain new coordinate update algorithms for a variety of problems in machine learning, image processing, as well as sub-areas of optimization. Several problems are treated with coordinate update for the first time in history. The obtained algorithms are scalable to large instances through parallel and even asynchronous computing. We present numerical examples to illustrate how effective these algorithms are.