Document Type


Publication Date

Fall 2022


Eberly College of Arts and Sciences




Basis Pursuit was developed primarily as a tool in the field of signal processing, beginning in the mid 1990’s. The idea is to model the behavior of discrete signals using a wide range of functional behaviors and scales and to obtain an accurate and efficient representation of the signal using a minimal number of functions from a large “dictionary” of possible behaviors. The key observation is by formulating the representation as an ℓ1 optimization, the problem can be posed as a linear program so that the optimal solution uses no more than the number of constraints - it must be a basic feasible solution.

While the problem has been explored in signal processing, we are here interested in the possible application to approximation of functions as classically considered in analysis. We present a number of applications in approximation with a dictionary consisting of multiresolution cubic spline spaces, with varying objective functions, but optimizations that ultimately must minimize a linear objective function. While signal processing applications are concerned with efficient solution of very large linear programs, here we can limit the sizes of the problems and study the nature of the solutions themselves. We use interpolation, uniform approximation, and formulations involving blended approximation, with objective functions involving ℓ1 terms blended with uniform or quadratic penalty functions.