In the past decade there has been significant progress in understanding when convex relaxations are effective for finding low complexity models from a near minimal number of data samples  (e.g. sparse/low rank recovery from a few linear
measurements). Despite such advances convex optimization techniques are often prohibitive in practice due to computational/memory constraints. Furthermore, in some cases convex programs are also suboptimal in terms of sample complexity
and provably require significantly more data samples than what is required to uniquely specify the low complexity model of interest. In fact for many such problems certain sample complexity “barriers” have emerged so that there are no
known computationally tractable algorithm that can beat the sample complexity achieved by such convex relaxations. Motivated by a problem in imaging, In this talk I will discuss my recent results towards breaking such barriers via natural
nonconvex optimization techniques.