Exploiting the Structure via Sketched Gradient Algorithms
From MaRDI portal
Publication:6286705
arXiv1705.05348MaRDI QIDQ6286705FDOQ6286705
Authors: J. Tang, Mohammad Golbabaee, M. E. Davies 
Publication date: 15 May 2017
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.
This page was built for publication: Exploiting the Structure via Sketched Gradient Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6286705)
