Randomized first order algorithms with applications to l1-minimization

• 成果类型: Article
• 署名作者: Juditsky, Anatoli; Karzan, Fatma Kilinc; Nemirovski, Arkadi
• 署名单位: Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); Carnegie Mellon University; University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0575-2
• 发表日期: 2013
• 页码: 269-310
• 关键词: INEQUALITIES

摘要

In this paper we propose randomized first-order algorithms for solving bilinear saddle points problems. Our developments are motivated by the need for sub-linear time algorithms to solve large-scale parametric bilinear saddle point problems where cheap online assessment of the solution quality is crucial. We present the theoretical efficiency estimates of our algorithms and discuss a number of applications, primarily to the problem of l(1) minimization arising in sparsity-oriented signal processing. We demonstrate, both theoretically and by numerical examples, that when seeking for medium-accuracy solutions of large-scale l(1) minimization problems, our randomized algorithms outperform significantly (and progressively as the sizes of the problem grow) the state-of-the art deterministic methods.