Gradient Projection Iterative Sketch for Large-Scale Constrained Least-Squares

2016/09/29 by Junqi Tang, Tang, Junqi, Mohammad Golbabaee +3 · 2 citations
Computer Science · Engineering · Mathematics · #FOS: Mathematics #Numerical methods in inverse problems #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1609.09419

openalex publication_date 2016/09/29 · openalex created_date 2016/10/07 · openalex updated_date 2026/07/28

Abstract

We propose a randomized first order optimization algorithm Gradient Projection Iterative Sketch (GPIS) and an accelerated variant for efficiently solving large scale constrained Least Squares (LS). We provide theoretical convergence analysis for both proposed algorithms and demonstrate our methods' computational efficiency compared to classical accelerated gradient method, and the state of the art variance-reduced stochastic gradient methods through numerical experiments in various large synthetic/real data sets.

Cited by

• Exploiting the Structure via Sketched Gradient Algorithms
• Sequential Least-Squares Estimators with Fast Randomized Sketching for Linear Statistical Models

Related

• Exploiting the Structure via Sketched Gradient Algorithms
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• Compare different SG-Schemes based on large least square problems
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• Sequential Preconditioned Conjugate Gradient Method for Linear Statistical Models