Optimization Online


L1 Minimization via Randomized First Order Algorithms

Anatoli Juditsky (Anatoli.Iouditski***at***imag.fr)
Fatma Kilinc Karzan (fkilinc***at***gatech.edu)
Arkadi Nemirovski (nemirovs***at***isye.gatech.edu)

Abstract: In this paper we propose randomized first-order algorithms for solving bilinear saddle points problems. Our developments are motivated by the need for sublinear time algorithms to solve large-scale parametric bilinear saddle point problems where cheap online assessment of solution quality is crucial. We present the theoretical efficiency estimates of our algorithms and discuss a number of applications, primarily to the problem of $\ell_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 $\ell_1$ minimization problems, our randomized algorithms outperform significantly (and progressively as the sizes of the problem grow) the state-of-the art deterministic methods.

Keywords: Bilinear saddle point problems, Randomized algorithms, L1 minimization, Compressed sensing

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Applications -- Science and Engineering

Citation: School of Industrial and Systems Engineering, Georgia Institute of Technolofy, 765 Ferst Drive NW, Atlanta GA 30332 USA, May 2010

Download: [PDF]

Entry Submitted: 05/16/2010
Entry Accepted: 05/16/2010
Entry Last Modified: 06/05/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society