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 the first theoretical convergence analysis for both algorithms. An efficient implementation using a tailored line-search scheme is also proposed. We demonstrate our methods' computational efficiency compared to the classical accelerated gradient method, and the variance-reduced stochastic gradient methods through numerical experiments in various large synthetic/real data sets.
Junqi Tang (the University of Edinburgh)
Mohammad Golbabaee (the University of Edinburgh)
Mike E Davies (University of Edinburgh)
Mike Davies holds the Jeffrey Collins Chair in Signal and Image Processing at UoE, where he also leads the Edinburgh Compressed Sensing Research Group and from 2013-2016 was Head of the Institute for Digital Communications (IDCOM). He received an M.A. in engineering from Cambridge University in 1989 and his Ph.D. from University College London (UCL) in 1993. His awards include: Royal Society University Research Fellow, Texas Instruments Distinguished Visiting Professor at Rice University, European Research Council Advanced Grant, IEEE Fellow, EURASIP Fellow and a Royal Society Wolfson Research Merit Award. Currently he also leads the University Defence Research Collaboration (UDRC), a U.K. programme of signal processing research in defence in collaboration with the U.K. Defence Science and Technology Laboratory (DSTL). His research has focused on nonlinear time series, source separation, sparse representations and compressed sensing. He has made key contributions to these fields including: the development of signal embedding theorems for nonlinear dynamical time series and the development of new theoretical and algorithmic results in Independent Component Analysis. Most recently he has pioneered the use of sparse representations as a fundamental tool in signal processing, source separation and compressed sensing. This work includes: the proposal and analysis of the highly popular Iterative Hard Thresholding algorithm for sparse reconstruction; the development of a theory for the sampling of structured sparse signal models as well as the development of a variety of new practical sampling and reconstruction techniques that exploit structured sparsity. He has also explored the application of these ideas to advanced medical imaging and RF based sensing and machine learning.
Related Events (a corresponding poster, oral, or spotlight)
2017 Talk: Gradient Projection Iterative Sketch for Large-Scale Constrained Least-Squares »
Mon Aug 7th 04:24 -- 04:42 AM Room Parkside 2