Structure-exploiting randomized algorithms for constrained estimation

Junqi Tang, Mohammad Golbabaee, Mike Davies

Research output: Chapter or section in a book/report/conference proceedingChapter in a published conference proceeding

10 Downloads (Pure)


This paper proposes an accelerated sketched gradient method [1] which was based on equipping a combination of the metaalgorithms Classical Sketch (CS) [2] and Iterative Hessian Sketch (IHS) [3] with the Projected / Proximal Gradient Descent (PGD) algorithm and Nesterov’s acceleration scheme for efficiently solving large scale constrained Least-squares and regularized Least-squares. As a first order solver, the PGD can provide us flexibility in handling the constraints and scalability in computation. The proposed algorithm satisfies a number of our expectations as an efficient large scale constrained/regularized LS solver, which are mainly inherited from the scalability and flexibility of the PGD combined with dimensionality reducing properties of the sketching techniques: (a) computational efficiency, (b) efficiency on high speed storage, and (c) flexibly to incorporate a wide range of constraints and non-smooth regularization.
Original languageEnglish
Title of host publicationSignal Processing with Adaptive Sparse Structured Representations (SPARS17)
Number of pages3
Publication statusPublished - 1 Feb 2017

Publication series

NameSignal Processing with Adaptive Sparse Structured Representations (SPARS)


Dive into the research topics of 'Structure-exploiting randomized algorithms for constrained estimation'. Together they form a unique fingerprint.

Cite this