Column Partition Based Distributed Algorithms for Coupled Convex Sparse Optimization: Dual and Exact Regularization Approaches
Column Partition Based Distributed Algorithms for Coupled Convex Sparse Optimization: Dual and Exact Regularization Approaches
复制标题
DOI：
10.1109/tsipn.2021.3087110
复制
发表时间：
2020-02
影响因子：
3.2
通讯作者：
Jinglai Shen;Jianghai Hu;Eswar Kumar Hathibelagal Kammara
中科院分区：
文献类型：
--
作者：
Jinglai Shen;Jianghai Hu;Eswar Kumar Hathibelagal Kammara
本文针对一类凸稀疏优化问题，例如，基追踪（BP）、LASSO、基追踪去噪（BPDN）及其扩展，例如，融合了LASSO。我们特别感兴趣的情况下，（标量）决策变量的数量远远大于（标量）测量的数量，每个代理有有限的内存或计算能力，使它只知道一个测量矩阵的列数很少。所考虑的问题是密集耦合，不能制定为可分离的凸规划。为了克服这一困难，我们考虑他们的对偶问题是可分离的或局部耦合。一旦获得对偶解，则在适当的精确正则化条件下，可以从相应的正则化BP类问题的对偶中找到原始解。广泛的现有的分布式计划可以用来解决所获得的双重问题。这产生两个阶段的列分区为基础的分布式计划LASSO和BPDN的问题，这些计划的整体收敛性。数值结果说明了所提出的两阶段分布式计划的性能。
This paper develops column partition based distributed schemes for a class of convex sparse optimization problems, e.g., basis pursuit (BP), LASSO, basis pursuit denosing (BPDN), and their extensions, e.g., fused LASSO. We are particularly interested in the cases where the number of (scalar) decision variables is much larger than the number of (scalar) measurements, and each agent has limited memory or computing capacity such that it only knows a small number of columns of a measurement matrix. The problems in consideration are densely coupled and cannot be formulated as separable convex programs. To overcome this difficulty, we consider their dual problems which are separable or locally coupled. Once a dual solution is attained, it is shown that a primal solution can be found from the dual of corresponding regularized BP-like problems under suitable exact regularization conditions. A wide range of existing distributed schemes can be exploited to solve the obtained dual problems. This yields two-stage column partition based distributed schemes for LASSO-like and BPDN-like problems; the overall convergence of these schemes is established. Numerical results illustrate the performance of the proposed two-stage distributed schemes.