Parallel Sparse Optimization

[摘要] This thesis proposes parallel and distributed algorithms for solving very largescalesparse optimization problems on computer clusters and clouds. Many modernapplications problems from compressive sensing, machine learning and signal andimage processing involve large-scale data and can be modeled as sparse optimizationproblems. Those problems are in such a large-scale that they can no longerbe processed on single workstations running single-threaded computing approaches.Moving to parallel/distributed/cloud computing becomes a viable option. I proposetwo approaches for solving these problems. The first approach is the distributedimplementations of a class of efficient proximal linear methods for solving convexoptimization problems by taking advantages of the separability of the terms in the objective.The second approach is a parallel greedy coordinate descent method (GRock),which greedily choose several entries to update in parallel in each iteration. I establishthe convergence of GRock and explain why it often performs exceptionally well forsparse optimization. Extensive numerical results on a computer cluster and AmazonEC2 demonstrate the efficiency and elasticity of my algorithms.

[发布机构] Rice University

[效力级别] optimization