Convex Optimization 2026, 25 - Sparse Descriptions & Interpolation with Convex Functions

Basis pursuit finds a fit of a data set as a linear combination of a small subset of a very large number of basis functions. Usually, the basis functions form an over-complete basis. The result should yield a set basis of functions itself (p. 348). The resulting function f has a sparse coefficient vector x (card(x)), which is small itself. The set of chosen indices 𝔹 is a sparse description of the data. It's mathematically identical to the regressor selection problem, but the scale of optimization differs (6.5.4).

A convex function fitted to data minimizes ∑_i=1^m(y_i - f(u_i))². This problem is infinite-dimensional, so it can be rewritten to be QP. Its optimal value is zero iff the given data can be interpolated by a convex function. Adding bounds, finding the smallest possible value for f(u₀), it'll solve as an LP. Convex interpolation can be extended to monotone convex functions by demanding that all subgradients of variables are nonnegative (6.5.5).