Time-Data Tradeoffs in Structured Signals Recovery via Proximal-Gradient Homotopy Method

In this paper, we characterize data-time tradeoffs of the proximal-gradient homotopy method used for solving penalized linear inverse problems under sub-Gaussian measurements. Our results are sharp up to an absolute constant factor. We also show that, in the absence of the strong convexity assumption, the proximal-gradient homotopy update can achieve a linear rate of convergence when the number of measurements is sufficiently large. Numerical simulations are provided to verify our theoretical results. All proofs are included in the online full version of this paper.