- L1 Minimization via Randomized First Order Algorithms Anatoli Juditsky (Anatoli.Iouditskiimag.fr) Fatma Kilinc Karzan (fkilincgatech.edu) Arkadi Nemirovski (nemirovsisye.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/2010Entry Accepted: 05/16/2010Entry Last Modified: 06/05/2011Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.