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 language | English |
---|---|
Title of host publication | Proceedings of the 2017 IEEE Global Conference on Signal and Information Processing (GlobalSIP) |
Publication status | Published - 1 May 2017 |
Keywords / Materials (for Non-textual outputs)
- Mathematics - Optimization and Control