Exploiting the Structure via Sketched Gradient Algorithms

Junqi Tang, Mohammad Golbabaee, Mike Davies

Research output: Contribution to conferencePaperpeer-review

Abstract

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 languageUndefined/Unknown
Publication statusPublished - 15 May 2017
EventIEEE Global Conference on Signal and Information Processing 2017 - Montreal, Canada
Duration: 14 Nov 201716 Nov 2017
https://2017.ieeeglobalsip.org/

Conference

ConferenceIEEE Global Conference on Signal and Information Processing 2017
Abbreviated titleGlobalSIP
Country/TerritoryCanada
CityMontreal
Period14/11/1716/11/17
Internet address

Keywords

  • math.OC

Cite this