The Basis Pursuit Denoising problem, also known as the least absolute shrinkage and selection operator (Lasso) problem, is a cornerstone of compressive sensing, statistics and machine learning. In high-dimensional problems, recovering an exact sparse solution requires robust and efficient optimization algorithms. State-of-the-art algorithms for the Basis Pursuit Denoising problem, however, were not traditionally designed to work well in high dimension; they often lack scalable parallelism, scale poorly in size, or are prone to produce unreliable numerical results. The lack of scalability, in particular, makes it challenging to apply the Basis Pursuit Denoising problem on big data sets without access to adequate and costly computational resources. As a consequence, without efficient and robust algorithms to minimize monetary and energy costs, these limitations prevent new scientific discoveries. In this talk, I will present a simple algorithm that overcomes these limitations and can solve the Basis Pursuit Denoising problem efficiently to machine precision. This approach relies on novel connections between the Basis Pursuit Denoising problem and a first-order Hamilton-Jacobi partial differential equation (PDE). Specifically, I will show that applying a nonsmooth steepest gradient descent to compute the solution to an appropriate Hamilton-Jacobi PDE yields a simple scheme that recovers the solution of the Basis Pursuit Problem along its entire solution path. Finally, I will present some preliminary numerical results to illustrate my algorithm’s high efficiency and precision.

Zoom link:  https://ncsu.zoom.us/j/97638681103?pwd=dDJrRkE3d3NQZEhrRlhOMDc4T0pRUT09