Structure-exploiting randomized algorithms for constrained estimation

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.