# WARPd: A linearly convergent first-order method for inverse problems with approximate sharpness conditions

arXiv: https://arxiv.org/abs/2110.12437 · HTML: https://mlsanity.com/paper/2110.12437/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 148 references that are in the map.
- First posted on arXiv 24 Oct 2021.

## Builds on (most cited first, 25 of 25)

- [Deep Convolutional Neural Network for Inverse Problems in Imaging](https://mlsanity.com/paper/1611.03679/) (2016)
- [Algorithm Unrolling: Interpretable, Efficient Deep Learning for Signal and Image Processing](https://mlsanity.com/paper/1912.10557/) (2019)
- [Learning a Variational Network for Reconstruction of Accelerated MRI Data](https://mlsanity.com/paper/1704.00447/) (2017)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [On instabilities of deep learning in image reconstruction - Does AI come at a cost?](https://mlsanity.com/paper/1902.05300/) (2019)
- [Theoretical Linear Convergence of Unfolded ISTA and its Practical Weights and Thresholds](https://mlsanity.com/paper/1808.10038/) (2018)
- [A Review of Convolutional Neural Networks for Inverse Problems in Imaging](https://mlsanity.com/paper/1710.04011/) (2017)
- [Advancing machine learning for MR image reconstruction with an open competition: Overview of the 2019 fastMRI challenge](https://mlsanity.com/paper/2001.02518/) (2020)
- [The gap between theory and practice in function approximation with deep neural networks](https://mlsanity.com/paper/2001.07523/) (2020)
- [Can stable and accurate neural networks be computed? -- On the barriers of deep learning and Smale's 18th problem](https://mlsanity.com/paper/2101.08286/) (2021)
- [From error bounds to the complexity of first-order descent methods for convex functions](https://mlsanity.com/paper/1510.08234/) (2015)
- [Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications](https://mlsanity.com/paper/1706.04957/) (2017)
- [Learning The Invisible: A Hybrid Deep Learning-Shearlet Framework for Limited Angle Computed Tomography](https://mlsanity.com/paper/1811.04602/) (2018)
- [Splitting methods with variable metric for KL functions](https://mlsanity.com/paper/1405.1357/) (2014)
- [A Unified Approach to Error Bounds for Structured Convex Optimization Problems](https://mlsanity.com/paper/1512.03518/) (2015)
- [The Numerics of Phase Retrieval](https://mlsanity.com/paper/2004.05788/) (2020)
- [Results of the 2020 fastMRI Challenge for Machine Learning MR Image Reconstruction](https://mlsanity.com/paper/2012.06318/) (2020)
- [Local Linear Convergence of Forward-Backward under Partial Smoothness](https://mlsanity.com/paper/1407.5611/) (2014)
- [Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness](https://mlsanity.com/paper/2105.12715/) (2021)
- [Total Deep Variation: A Stable Regularizer for Inverse Problems](https://mlsanity.com/paper/2006.08789/) (2020)
- [New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measure](https://mlsanity.com/paper/1511.02974/) (2015)
- [On the convex geometry of blind deconvolution and matrix completion](https://mlsanity.com/paper/1902.11156/) (2019)
- [Restarting accelerated gradient methods with a rough strong convexity estimate](https://mlsanity.com/paper/1609.07358/) (2016)
- [Proof methods for robust low-rank matrix recovery](https://mlsanity.com/paper/2106.04382/) (2021)
- [A multilevel based reweighting algorithm with joint regularizers for sparse recovery](https://mlsanity.com/paper/1604.06941/) (2016)

## Built on by (most cited first, 1 of 1)

- [On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samples](https://mlsanity.com/paper/2203.13908/) (2022)

## Abstract (arXiv)

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|l1 under constraints (l1-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.