2017/05/15 by Junqi Tang, Tang, Junqi, Mohammad Golbabaee +3
Computer Science · Engineering · #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1705.05348
openalex publication_date 2017/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.