Exploiting the Structure via Sketched Gradient Algorithms

Junqi Tang, Mohammad Golbabaee, Mike Davies

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Sketched gradient algorithms have been recently introduced for efficiently solving the large-scale constrained Least-squares regressions. In this paper we provide novel convergence analysis for the basic method {\it Gradient Projection Classical Sketch} (GPCS) to reveal the fast linear convergence rate of GPCS towards a vicinity of the solution thanks to the intrinsic low-dimensional geometric structure of the solution prompted by constraint set. Similar to our analysis we observe computational and sketch size trade-offs in numerical experiments. Hence we justify that the combination of gradient methods and the sketching technique is a way of designing efficient algorithms which can actively exploit the low-dimensional structure to accelerate computation in large scale data regression and signal processing applications.
Original languageEnglish
Title of host publicationProceedings of the 2017 IEEE Global Conference on Signal and Information Processing (GlobalSIP)
Publication statusPublished - 1 May 2017

Keywords / Materials (for Non-textual outputs)

  • Mathematics - Optimization and Control


Dive into the research topics of 'Exploiting the Structure via Sketched Gradient Algorithms'. Together they form a unique fingerprint.

Cite this