Sparse Recovery over Nonlinear Dictionaries

Sparse modeling seeks to represent signals as a linear combination of a small number of atoms from an overparametrized dictionary. Despite the success of these linear models, they can be too restrictive for applications involving nonlinear measurements. Using nonlinear atoms, however, poses an additional obstacle to the sparse recovery problem, since it remains non-convex even after relaxing the sparsity objective (e.g., using atomic norms). We address this issue in the context of continuous dictionaries by posing nonlinear sparse recovery as a sparse functional program that explicitly minimizes the functional equivalent of the '₀-norm, i.e., the function support measure. By proving that strong duality holds for these optimization problems, we show that nonlinear sparse recovery over continuous dictionaries precludes relaxations since it may be solved efficiently using duality. This result is non-parametric, in that it does not assume the data follows the measurement model, and does not require incoherence assumptions, such as the restricted isometry/eigenvalue property. We also use strong duality to derive a relation between minimizing the support of a function and minimizing its L₁-norm, although this does not imply that the latter leads to sparse solutions. We illustrate this new approach in a nonlinear line spectrum estimation problem.