  Reconstruction of signals from undersampled and noisy measurements is a topic
of considerable interest. Sharpness conditions directly control the recovery
performance of restart schemes for first-order methods without the need for
restrictive assumptions such as strong convexity. However, they are challenging
to apply in the presence of noise or approximate model classes (e.g.,
approximate sparsity). We provide a first-order method: Weighted, Accelerated
and Restarted Primal-dual (WARPd), based on primal-dual iterations and a novel
restart-reweight scheme. Under a generic approximate sharpness condition, WARPd
achieves stable linear convergence to the desired vector. Many problems of
interest fit into this framework. For example, we analyze sparse recovery in
compressed sensing, low-rank matrix recovery, matrix completion, TV
regularization, minimization of $\|Bx\|_{l^1}$ under constraints
($l^1$-analysis problems for general $B$), and mixed regularization problems.
We show how several quantities controlling recovery performance also provide
explicit approximate sharpness constants. Numerical experiments show that WARPd
compares favorably with specialized state-of-the-art methods and is ideally
suited for solving large-scale problems. We also present a noise-blind variant
based on the Square-Root LASSO decoder. Finally, we show how to unroll WARPd as
neural networks. This approximation theory result provides lower bounds for
stable and accurate neural networks for inverse problems and sheds light on
architecture choices. Code and a gallery of examples are made available online
as a MATLAB package.
