Groupe thématique SMAI-AFA

Proposition de Thèse au L2MA (Arts et Métiers ParisTech de Lille)

Eric Nyiri — 2010-05-04T08:10:48Z

Proposition de Thèse au Laboratoire de Métrologie et de Mathématiques Appliquées (L2MA) du centre Arts et Métiers ParisTech de Lille

sujet : Approximation en norme L1 par splines polynomiales

contacts : olivier.gibaru@ensam.eu ou eric.nyiri@ensam.eu

date limite de candidature : 3 juin 2010

financement : Poste de doctorant contractuel ED SMI

site web de l'annonce : http://www.adum.fr/as/ed/voirproposition.pl ?site=smi&matricule_prop=2006

site web de l'école doctorale 432, "Sciences des Métiers de l'Ingénieur" commune à "Arts et Métiers ParisTech" et à "MINES ParisTech" : http://www.paris.ensam.fr/ed

Résumé :

Le travail de thèse proposé concerne la détermination de la meilleure approximation au sens de la norme L1 de fonctions intégrables dans un sous espace vectoriel de dimension fini.

L'approximation au sens de la norme L1 a été étudiée en premier lieu dans certains cas particuliers par Chebyshev au 19eme siècle. Une étude générale a été proposée par Kripke et Rivlin en 1963. L'utilisation de cette norme connaît depuis le travail de Candès en 2004, alors au CalTech, un regain d'intérêt dans le domaine du traitement de l'image et du signal. Le problème principal de la norme L1 est qu'elle n'est pas strictement convexe. Ainsi la minimisation est en général un problème non linéaire. Contrairement à la norme L2, la solution n'est pas unique et la minimisation conduit à la résolution d'un système numérique de grande taille. Néanmoins cette norme présente la particularité dans le cas de l'interpolation de données discrètes par des splines polynomiales, de ne pas présenter de sur-oscillations (ou phénomène de Gibbs) lorsque les données présentent des variations brusques. Cette propriété, ainsi que d'autres, présentant un intérêt majeur pour les applications en géométrie, a été démontrée récemment par notre équipe

Les travaux déjà réalisés donnent à partir d'études théoriques locales basées sur des critères géométriques de très bons résultats comparativement aux méthodes traditionnelles d'interpolation. Le but de cette thèse sera donc d'étendre ces recherches autour de l'interpolation au cas de l'approximation. Nous souhaitons définir des algorithmes rapides utilisant des propriétés locales géométriques afin d'effectuer ce calcul de meilleure approximation au sens de la norme L1 de données discrètes issus de signaux ou d'images par des splines polynomiales. Une étude sur les critères à minimiser devra être conduite afin d'évaluer leur pertinence vis-à-vis des applications considérées. Ces travaux très en amont pourront trouver des applications au sein du laboratoire dans le domaine de la robotique en lien avec l'équipe INMS du LSIS d'Aix en Provence, de l'imagerie avec la North Carolina State University et l'estimation de dérivées pour l'observation ou l'identification de systèmes non linéaires en automatique. Cette dernière partie pourra être traitée en lien avec l'équipe projet ALIEN de l'INRIA.

Le doctorant abordera des méthodes nouvelles d'approximation utilisant la norme L1 pour le domaine du traitement du signal, de la géométrie et de l'image. Il abordera ce problème au travers d'une expertise dans le domaine des splines polynomiales et avec une approche très géométrique propre à notre équipe. Le doctorant aura la possibilité, suite à l'obtention de résultats théoriques, d'envisager la programmation d'algorithmes dans un contexte de parallélisation massive. Nous disposons en effet d'un système à base d'une carte Tesla de NVDIA à 240 cœurs GPU permettant ce travail d'implémentation et de tests.

Partenaires : Équipe INMS du LSIS d'Aix-en-Provence, J.E. Lavery du North Carolina State University/ US Navy et l'INRIA EPI ALIEN

E. Nyiri, O. Gibaru, P. Auquiert (2010), Fast $L_1-C^k$ polynomial spline interpolation algorithm with shape-preserving properties, Computer Aided Geometric Design, (révisé) P. Auquiert, O. Gibaru, E. Nyiri (2007), C1 and C2-continuous polynomial parametric Lp splines (p ≥ 1). Computer Aided Geometric Design 24, pp. 373-394. P. Auquiert, O. Gibaru, E. Nyiri (2007), On the cubic L1 spline interpolant to the Heaviside function, Numer. Algor. 46, pp. 321.332. P.L. Chebyshev, Sur les questions de minima qui se rattachent à la représentation approximative des fonctions, Oeuvres I (1859) 273-378. B.R. Kripke, T.J. Rivlin (1965), Approximation in the metric of L1(X,µ), Transactions of the American Mathematical Society, Vol. 119, N°1, pp.101-122. J.E. Lavery H. Cheng, S.-C. Fang (2005), Shape-preserving properties of univariate cubic L1 splines, Journal of Computational and Applied Mathematics 174, pp. 361.382. J.E. Lavery (2006), Shape-preserving first-derivative-based parametric and non parametric cubic L1 spline curves, Comput. Aided Geom. Design 23, pp. 276-296 T. Tao, E. Candès (2006), "Near-optimal signal recovery from random projections : universal encoding strategies ?", IEEE Transactions on Information Theory 52 (12) : 5406–5425

Seventh International Conference on Curves and Surfaces 24/06/2010-30/06/2010

Eric Nyiri — 2010-05-02T14:33:00Z

La 7ème Conference "Curves and Surfaces" organisée par SMAI-AFA aura lieu à Avignon FRANCE du 24 au 30 juin 2010

SMAI-AFA workshop "High Dimensional Problems and Solutions", 21/06/2010 and 22/06/2010

Eric Nyiri — 2010-01-15T17:18:19Z

"High Dimensional Problems and Solutions"

A SMAI-AFA workshop, with the support of the Fondation Science Mathematique de Paris.

Location : Université Pierre et Marie Curie 175, rue du Chevaleret, 75013 Paris

Dates : June 21 and 22

Organizers : Albert Cohen and Ronald DeVore

The objective of this workshop is to gather experts from various discipline (approximation theory, harmonic analysis, learning theory, signal processing, numerical analysis of PDE's) and compare the approaches for tackling problems involving high dimensions.

First confirmed participants : Christoph Schwab, Steve Smale, Yvon Maday, Rob Nowak, Przemek Wojtaczyck, Dominique Picard, Gerard Kerkyacharian, Martin Wainwright, Guergana Petrova and Mauro Maggioni.

Inscription is free but mandatory in order to plan a sufficiently large room : please send email to cohen@ann.jussieu.fr

Journées du Groupe de Travail en Modélisation Géométrique (GTMG), Dijon, 31/03/2010 et 01/04/2010.

Eric Nyiri — 2010-01-14T08:04:21Z

- Recherche

Journées Nationales d'Informatique Mathématique, 21/01/2010 et 22/01/2010

Eric Nyiri — 2009-12-01T13:02:40Z

Les Journées Nationales d'Informatique Mathématique

organisées par le GDR IM, auront lieu les 21 et 22 janvier 2010 à l'Université Paris 6 (campus Jussieu)

Elles commenceront le 21 janvier à 10h30 et se termineront le 22 janvier à 16h. Les déjeuners sont pris en charge par le GDR, ainsi qu'un buffet-cocktail le jeudi soir sur place.

Les orateurs invités sont
Günter Rote (Berlin) : "On pseudotriangulations"
Xuding Zhu (Taiwan) : "Thue choice number of paths"

Vous recevrez le programme complet prochainement, mais réservez dès à présent ces dates !

Merci de transmettre autour de vous, en particulier aux doctorants.

Christiane Frougny Directrice-adjointe du GDR IM

LIAFA, CNRS UMR 7089, Université Paris Diderot - Paris 7 Case 7014 75205 Paris Cedex 13

Courriel : Christiane.Frougny@liafa.jussieu.fr

http://www.liafa.jussieu.fr/ cf Tel : +33 1 44 27 54 43 - Fax : +33 1 44 27 68 49 Bureau : 6A 31 bis, 175 rue du Chevaleret - 75013 Paris

Compte rendu de l'assemblée générale du 13 novembre 2009

Eric Nyiri — 2009-11-17T10:07:43Z

Veuillez trouver ci-dessous, la compte rendu de l'Assemblé générale du groupe SMAI-AFA qui a eu lieu le 13 novembre 2009.

Compte Rendu AG SMAI-AFA

Documents de la journée du 13 novembre 2009

Eric Nyiri — 2009-11-16T12:48:52Z

Documents de la

Journée "Approximation, Géométrie et Image", organisée par le groupe thématique SMAI-AFA.

vendredi 13 novembre 2009 de 9h45 à 17h

Arts et Métiers ParisTech

Simon Foucart "Reconstructions parcimonieuses : réelle contre complexe"

Présentation de Simon Foucart

Romain Raffin "Reconstruction de surfaces paramétriques à partir de surfaces maillées par des surfaces de subdivision"

Présentation de Romain Raffin

Assemblée AFA

Compte Rendu AG SMAI-AFA

Journée Approximation, Géométrie et Image, le 13/11/2009

Eric Nyiri — 2009-10-08T18:29:45Z

Journée "Approximation, Géométrie et Image", organisée par le groupe thématique SMAI-AFA.

vendredi 13 novembre 2009 de 9h45 à 17h

Arts et Métiers ParisTech

Plan d'accès à Arts et Métiers ParisTech

Lieu :

Attention changement de salle : Accueil Amphi Bézier

Arts et Métier ParisTech
151, boulevard de l'hôpital,
75013 Paris

Programme :
10h00 - 10h35 : Rida Farouki "Pythagorean-hodograph curves : theory, algorithms, and applications"
10h35 - 11h10 : Simon Foucart "Reconstructions parcimonieuses : réelle contre complexe"
11h10 - 11h45 : Bruno Levy "Génération automatique de maillages hex-dominants par optimisation d'une fonction objectif."
Déjeuner
13h45 - 14h45 : Assemblée AFA
15h00 - 15h35 : Tom Claeys "Comportement asymptotique pour des déterminants de Toeplitz et l'équation de Painlevé V"
15h35 - 16h10 : Gabriel Peyré "Compression d'images par triangulations anisotropes géodésiques"
16h10 - 16h45 : Romain Raffin "Reconstruction de surfaces paramétriques à partir de surfaces maillées par des surfaces de subdivision"

Programme, résumés et plan d'accès

Organisateur : Eric Nyiri

Inscriptions : L'inscription est gratuite, mais pour des questions de logistique merci de bien vouloir annoncer votre participation en contactant Eric Nyiri : eric.nyiri@ensam.eu

Intervenants de la journée

Tom Claeys (Laboratoire Painlevé, Université de Lille I)
Titre : "Comportement asymptotique pour des déterminants de Toeplitz et l'équation de Painlevé V"
Résumé : Pour des symboles réguliers, le comportement asymptotique des déterminants de Toeplitz est décrit par un résultat classique de Szegö. Dans le cas non-régulier où on a des singularités du type Fisher-Hartwig, d'autres résultats sont connus. Nous considérons des symboles qui interpolent entre les symboles de Szegö et les symboles de Fisher-Hartwig. Cette transition peut être décrite en utilisant une solution de l'équation de Painlevé V. Il s'agit d'une collaboration avec A. Its et I. Krasovsky.

Rida Farouki (University of California, Davis, USA)
Titre : "Pythagorean-hodograph curves : theory, algorithms, and applications""
Résumé : By virtue of their special algebraic structures, Pythagorean-hodograph (PH) curves offer unique computational advantages for geometric design, computer graphics and animation, robotics and manufacturing, and related fields. Efficient algorithms for the construction of planar and spatial PH curves are based on complex number and quaternion representations, and are extensible to higher dimensions and the Minkowski metric using Clifford algebra models. Among their special attributes, they provide exact computation of arc length and offset (parallel) curves ; versatile real-time CNC interpolator algorithms for motion control applications ; and rational rotation-minimizing frames for spatial motion planning and camera orientation control. The presentation provides a broad overview of the basic theory, practical algorithms, and diverse applications of this remarkable class of curves.

Simon Foucart (Laboratoire Jacques-Louis Lions, Paris 6)
Titre : "Reconstructions parcimonieuses : réelle contre complexe"
Résumé : La minimisation L1 offre un moyen de reconstruire signaux ou images à partir d'une quantité très limitée d'information. Cela découle du fait que les solutions parcimonieuses de nombreux systèmes linéaires sous-déterminés sont celles ayant la plus petite norme L1. Ces systèmes linéaires sont caractérisés par une propriété de leur noyau, laquelle s'interprète différemment dans le cadre réel et dans le cadre complexe. Nous allons montrer que pour un système linéaire réel, les deux interprétations a priori distinctes sont en fait équivalentes. Ceci signifie que la minimisation L1 permet de reconstruire les vecteurs parcimonieux complexes dès qu'elle le permet pour les vecteurs parcimonieux réels

Bruno Levy (INRIA Nancy)
Titre : "Génération automatique de maillages hex-dominants par optimisation d'une fonction objectif."
Résumé : Les maillages à base d'hexaèdres sont particulièrement utiles pour les simulations numériques de fluides, mais connus pour être difficile à générer. Les méthodes fondées sur l'avancée d'un front à partir du bord se heurtent au problème de mailler la cavité résultant de la collision du front sur l'axe médian. Inversement, les méthodes fondées sur des octrees génèrent sur le bord du domaine un maillage fortement irrégulier. Nous présentons le mailleur VHD (Variational Hex Dominant), fondé sur la minimisation d'une fonction objectif globale $F$, dépendant de la position de tous les sommets du maillage volumique. La fonction $F$ est une généralisation de l'énergie de Lloyd, connue en théorie de l'échantillonnage. En particulier, $F$ est définie de manière à pouvoir prendre en compte un champ d'anisotropie prédéfini, contraignant les directions préférentielles pour les arêtes des hexaèdres.

Gabriel Peyré (Ceremade, Paris-Dauphine)
Titre : "Compression d'images par triangulations anisotropes géodésiques"
Résumé : J'expliquerai dans cet exposé comment la géométrie locale des images peut être encodée à l'aide d'un champ de tenseurs, qui correspond à une métrique Riemannienne. Ce champ de tenseurs décrit l'anisotropie locale des contours et des textures oscillantes. Ce champ est intégré en une métrique globale à l'aide de calculs de distances géodésiques par l'algorithme de Fast Marching. Un échantillonneur glouton par points éloignés ainsi qu'une triangulation de Delaunay géodésique permet la construction d'une approximation adaptative par éléments finis. Cette approximation est à la base d'un compresseur d'images géométriques qui encode à la fois la connectivité de la triangulation et la position des points.

Romain Raffin (LSIS, Ecole Supérieure d'Ingénieurs de Luminy, Université de Provence)
Titre : "Reconstruction de surfaces paramétriques à partir de surfaces maillées par des surfaces de subdivision"
Résumé : Le passage de surfaces paramétriques à des maillages d'approximation est un problème connu et actif depuis les débuts de la CAO. Le problème inverse est lui aussi un sujet de recherches constant. Évidemment, la surface idéale aurait à la fois une description paramétrique et discrète. Les surfaces de subdivision (schémas de Loop, Catmull-Clark, Butterfly, etc) permettraient de mettre en place cette dualité. Les règles de subdivision entraînent hélas souvent la contraction des objets pour tendre vers une surface limite. Nous travaillons sur le passage d'une surface maillée discrète à une surface paramétrique par l'utilisation de surface de subdivision. La contraction des surfaces est contrôlée géométriquement et aboutit à des interpolations des surfaces maillées. Finalement, un polyèdre de contrôle est généré, utilisable pour une surface paramétrique ou des maillages d'approximations.

COLLOQUE INTERNATIONAL NTA09, du 27/10/2009 au 28/10/2009

Eric Nyiri — 2009-09-23T16:18:44Z

- Recherche

MOMA 09, 2nd Meeting on Optimization Modelization and Approximation 19/11/2009 - 21/11/2009 - Casablanca, Morocco.

Eric Nyiri — 2009-04-27T17:46:22Z

MOMA 09, 2nd Meeting on Optimization Modelization and Approximation 19/11/2009 - 21/11/2009 - Casablanca, Morocco.

http://www-lmpa.univ-littoral.fr/MOMA09/