Exploiting the structure via sketched gradient algorithms

Junqi Tang, Mohammad Golbabaee, Mike Davies

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

1 Citation (SciVal)


Sketched gradient algorithms [1] 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 Gradient Projection Classical Sketch (GPCS) to reveal the fast linear convergence rate of GPCS 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 publication2017 IEEE Global Conference on Signal and Information Processing (GlobalSIP)
ISBN (Electronic)978-1-5090-5990-4
ISBN (Print)978-1-5090-5991-1
Publication statusPublished - 8 Mar 2018


Dive into the research topics of 'Exploiting the structure via sketched gradient algorithms'. Together they form a unique fingerprint.

Cite this