  In this article we dwell into the class of so called ill posed Linear Inverse
Problems (LIP) in machine learning, which has become almost a classic in recent
times. The fundamental task in an LIP is to recover the entire signal / data
from its relatively few random linear measurements. Such problems arise in
variety of settings with applications ranging from medical image processing,
recommender systems etc. We provide an exposition to the convex duality of the
linear inverse problems, and obtain a novel and equivalent convex-concave
min-max reformulation that gives rise to simple ascend-descent type algorithms
to solve an LIP. Moreover, such a reformulation is crucial in developing
methods to solve the dictionary learning problem with almost sure recovery
constraints.
