Fonction caractéristique (théorie des ensembles)

En mathématiques, une fonction caractéristique, ou fonction indicatrice, est une fonction définie sur un ensemble E qui explicite l’appartenance ou non à un sous-ensemble F de E de tout élément de E. Formellement, la fonction caractéristique d’un sous-ensemble F d’un ensemble E est une fonction : \begin{array}{rcl} \chi_F : E & \longrightarrow & {0,1} \ x & \longmapsto & \left{\begin{matrix} 1 \ \mbox{si} \ x \ \in \ F \ 0 \ \mbox{si} \ x \ \notin \ F \end{matrix}\right. \end{array} D'autres notations souvent employées pour la fonction caractéristique de F sont 1 et 𝟙, voire I (i majuscule). Le terme de fonction indicatrice est parfois utilisé pour fonction caractéristique. Cette dénomination évite la confusion avec la fonction caractéristique utilisée en probabilité mais en induit une autre, avec la fonction indicatrice en analyse convexe. (Attention : la fonction 1 peut désigner aussi la fonction identité). Propriétés Le principa

Algorithms and methods for sparse approximation in structured dictionaries

Lorenzo Peotta

In the last decade we observed an increasing interaction between data compression and sparse signals approximations. Sparse approximations are desirable because they compact the energy of the signals in few elements and correspond to a structural simplification of the approximated signals. In the first part of this dissertation we consider the low bit rate image coding problem. The state of the art in image compression is to use two-dimensional (2-D) wavelets. The main advantage of wavelet bases lie in their multiscale nature and in their ability to sparsely represent functions that are piecewise smooth. Their main problem on the other hand, is that 2-D wavelets are not able to deal with the natural geometry of images, i.e. they cannot sparsely represent objects that are smooth away from regular submanifolds. We propose an approach based on building a sparse approximation of the edge part of images in a redundant geometrically inspired library of functions, followed by suitable coding techniques. The edge-oriented dictionary is built by anisotropically scaling, orienting and bending a generating function. The new bending transform generates elementary waveforms that efficiently approximate the edges; with few waveforms we are able to approximate long edges. The sparse approximations over the redundant dictionary are computed using a sub-optimal greedy strategy, as indeed finding the best m-terms non-linear approximations in general dictionaries is a NP-hard problem. Recently there has been an intense activity in the field of sparse approximations with redundant dictionaries, largely motivated by the practical performances of algorithms such as Matching Pursuit and Basis Pursuit. However, most of the theoretical results obtained so far are valid only for the restricted class of incoherent dictionaries. The second part of the dissertation investigates a new class of overcomplete dictionaries, called block incoherent dictionaries, where coherence can be arbitrarily large. We show that a simple greedy algorithm can correctly identify stable subdictionaries (called blocks) and demonstrate how one can use the extra coherence freedom for approximation purposes. With the aim of improving the sparse approximations over redundant dictionaries obtained with greedy algorithms, in the last part we develop a new decomposition algorithm characterized by the computational cost of MP and global optimization properties typical of the re-weighted minimum norm algorithms such as FOCUSS. We introduce the concept of sub-dictionary, a subset of the redundant dictionary which depends on the signal to be approximated, and we propose a sub-dictionary selection algorithm based on greedy techniques. The low computational cost greedy algorithm selects a sub-dictionary that contains the solution of more complex algorithms, which are utilized to obtain the approximation over the sub-dictionary. In the first part we studied image and video sparse approximation, however the concepts we present in the second part of the dissertation are general and can be applied to any kind of structured signal.

EPFL2007

Numerical simulation of 3D free surface flows, with multiple incompressible immiscible phases. Applications to impulse waves

Alexandre Caboussat, Marco Picasso

A numerical method for the solution to the density-dependent incompressible Navier-Stokes equations modeling the flow of N immiscible incompressible liquid phases with a free surface is proposed. It allows to model the flow of an arbitrary number of liquid phases together with an additional vacuum phase separated with a free surface. It is based on a volume-of-fluid approach involving N indicator functions (one per phase, identified by its density) that guarantees mass conservation within each phase. An additional indicator function for the whole liquid domain allows to treat boundary conditions at the interface between the liquid domain and a vacuum. The system of partial differential equations is solved by implicit operator splitting at each time step: first, transport equations are solved by a forward characteristics method on a fine Cartesian grid to predict the new location of each liquid phase; second, a generalized Stokes problem with a density-dependent viscosity is solved with a FEM on a coarser mesh of the liquid domain. A novel algorithm ensuring the maximum principle and limiting the numerical diffusion for the transport of the N phases is validated on benchmark flows. Then, we focus on a novel application and compare the numerical and physical simulations of impulse waves, that is, waves generated at the free surface of a water basin initially at rest after the impact of a denser phase. A particularly useful application in hydraulic engineering is to predict the effects of a landslide-generated impulse wave in a reservoir. Copyright (c) 2014 John Wiley & Sons, Ltd.

Wiley-Blackwell2014

Algorithms and methods for sparse approximation in structured dictionaries

Lorenzo Peotta

EPFL2007