This paper proposes an accelerated sketched gradient method  which was based on equipping a combination of the metaalgorithms Classical Sketch (CS)  and Iterative Hessian Sketch (IHS)  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.
|Title of host publication
|Signal Processing with Adaptive Sparse Structured Representations (SPARS17)
|Number of pages
|Published - 1 Feb 2017
|Signal Processing with Adaptive Sparse Structured Representations (SPARS)