0311-MCA

A usual task in processing signals, images as well as spherical data maps, is to decompose the data into its elementary building blocks. This can be formulated as an inverse problem where the data is assumed to have been generated according to the following model : y = X i αiφi + η (5.1) that is a linear combination of relevant waveforms φi ∈ R n with weights αi . Here η represents possible contamination by additive, typically Gaussian white noise. Given data y ∈ R n , one then wants to recover the underlying structures that is to say estimate a set of waveforms φi that build the data and their corresponding weights ˜αi . The solution to this estimation problem will depend heavily on the available prior information. Of interest here is the case where one is given a priori a set a waveforms from which to select a good subset. This set may be a basis, a frame or several bases or frames grouped into a large redundant dictionary. Possible dictionaries in 1D and 2D include Fourier and related bases, wavelet bases, as well as other more recent multiscale systems such as the ridgelet (Cand`es and Donoho 1999b) and curvelet frames (Donoho and Duncan 2000; Starck et al. 2002a), etc. Depending on the morphology of the data, each of these dictionaries will have different performance characteristics in a non-linear approximation scheme. For instance, sparse approximations of piecewise smooth signals or images with point singularities are easily obtained using wavelets. However these are no longer optimal in the case of piecewise smooth images with singularities along smooth curves or edges. Such images are more efficiently approximated using curvelets which are highly anisotropic and thus exhibit high directional selectivity. Digital implementations of both ridgelet and curvelet transforms and their application to image denoising are described in (Starck et al. 2002a).

In their pioneering work, Freeden and Maier (Freeden and Maier 2002; Freeden et al. 2003) gave a wavelet transform and reconstruction scheme on the sphere which is based on the spherical harmonic transform. Following this idea, Starck et al. (Starck et al. 2006) have proposed a new invertible isotropic undecimated wavelet transform (UWT) on the sphere which preserves the same desirable properties as the standard isotropic UWT for flat 2D maps (Starck et al. 1998): the reconstruction is simple and immediate since it is just the addition of all the wavelet bands with the coarsest scale. Based on this new decomposition, other multiscale transforms such as the pyramidal wavelet transform, the ridgelet transform and the curvelet transform have been successfully constructed on the sphere (Starck et al. 2006). Each of these decompositions on the sphere will sparsely represent parts of the image based on their morphological properties. Wavelets will easily detect more or less isotropic localized structures, while curvelets are better suited for efficiently detecting highly anisotropic objects.

A data set y has an exact representation over any complete basis of the data space, or several such exact representations in the case of redundant overcomplete dictionaries. However, these representations are not equally interesting in terms of data modeling or feature detection. In fact, a strong a priori is to favor representations of y that use only a small number of waveforms leading to a more concise and possibly more interpretable representation of the data. In fact, building sparse representations or approximations is the (he)art of structured data processing: the design of good detection, denoising, restoration and compression algorithms relies on the availability of good dictionaries and good selection algorithms. Indeed, selecting the smallest subset of waveforms from a large dictionary, that will linearly combine to reproduce the salient features of a given signal or image, is a hard combinatorial problem. Several pursuit algorithms have been proposed that can help build very sparse decompositions such as the greedy Matching Pursuit (MP) (Mallat and Zhang 1993) algorithm which refines the signal approximation by picking at each iteration the one waveform which best correlates with the current approximation error. Basis Pursuit (BP) (Chen et al. 1999) is a global procedure which seeks an approximation ˜y to y by solving the linear programming problem:

min α kαk1 subject to y = Φα. (5.2) where the 1 norm measures sparsity in place of the `0 counting norm.

Inpainting algorithms strive to interpolate through the gaps in the image relying on the available pixels, the continuation of edges, the periodicity of textures, etc. Seeking a sparse representation of the incomplete sine-wave outside the gap, that is without fitting the gap, enables the recovery of the complete monochromatic sinewave.