# Novel min-max reformulations of Linear Inverse Problems

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jul 2020.

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

- [Fast Algorithm for Constrained Linear Inverse Problems](https://mlsanity.com/paper/2212.01068/) (2022)

## Abstract (arXiv)

In this article, we dwell into the class of so-called ill-posed Linear Inverse Problems (LIP) which simply refers to the task of recovering the entire signal from its relatively few random linear measurements. Such problems arise in a variety of settings with applications ranging from medical image processing, recommender systems, etc. We propose a slightly generalized version of the error constrained linear inverse problem and obtain a novel and equivalent convex-concave min-max reformulation by providing an exposition to its convex geometry. Saddle points of the min-max problem are completely characterized in terms of a solution to the LIP, and vice versa. Applying simple saddle point seeking ascend-descent type algorithms to solve the min-max problems provides novel and simple algorithms to find a solution to the LIP. Moreover, the reformulation of an LIP as the min-max problem provided in this article is crucial in developing methods to solve the dictionary learning problem with almost sure recovery constraints.