# A theory of optimal convex regularization for low-dimensional recovery

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Dec 2021.

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

- [Optimal Regularization for a Data Source](https://mlsanity.com/paper/2212.13597/) (2022)
- [The Star Geometry of Critic-Based Regularizer Learning](https://mlsanity.com/paper/2408.16852/) (2024)
- [Optimal Regularization Under Uncertainty: Distributional Robustness and Convexity Constraints](https://mlsanity.com/paper/2510.03464/) (2025)
- [A Unified Framework for Pattern Recovery in Penalized and Thresholded Estimation and its Geometry](https://mlsanity.com/paper/2307.10158/) (2023)

## Abstract (arXiv)

We consider the problem of recovering elements of a low-dimensional model from under-determined linear measurements. To perform recovery, we consider the minimization of a convex regularizer subject to a data fit constraint. Given a model, we ask ourselves what is the "best" convex regularizer to perform its recovery. To answer this question, we define an optimal regularizer as a function that maximizes a compliance measure with respect to the model. We introduce and study several notions of compliance. We give analytical expressions for compliance measures based on the best-known recovery guarantees with the restricted isometry property. These expressions permit to show the optimality of the ℓ1-norm for sparse recovery and of the nuclear norm for low-rank matrix recovery for these compliance measures. We also investigate the construction of an optimal convex regularizer using the examples of sparsity in levels and of sparse plus low-rank models.