# Exploiting the Structure via Sketched Gradient Algorithms

arXiv: https://arxiv.org/abs/1705.05348 · HTML: https://mlsanity.com/paper/1705.05348/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2017.

## Built on by (most cited first, 1 of 1)

- [Accelerating Plug-and-Play Image Reconstruction via Multi-Stage Sketched Gradients](https://mlsanity.com/paper/2203.07308/) (2022)

## Abstract (arXiv)

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.