Wavelet Footprints: Theory, Algorithms and Applications

In recent years, wavelet-based algorithms have been successful in different signal processing tasks. The wavelet trans- form is a powerful tool because it manages to represent both tran- sient and stationary behaviors of a signal with few transform coeffi- cients. Discontinuities often carry relevant signal information, and therefore, they represent a critical part to analyze. In this paper, we study the dependency across scales of the wavelet coefficients generated by discontinuities. We start by showing that any piece- wise smooth signal can be expressed as a sum of a piecewise poly- nomial signal and a uniformly smooth residual (see Theorem 1 in Section II). We then introduce the notion of footprints, which are scale space vectors that model discontinuities in piecewise polyno- mial signals exactly. We show that footprints form an overcomplete dictionary and develop efficient and robust algorithms to find the exact representation of a piecewise polynomial function in terms of footprints. This also leads to efficient approximation of piece- wise smooth functions. Finally, we focus on applications and show that algorithms based on footprints outperform standard wavelet methods in different applications such as denoising, compression, and (nonblind) deconvolution. In the case of compression, we also prove that at high rates, footprint-based algorithms attain optimal performance (see Theorem 3 in Section V).