Nous proposons une méthode pour placer automatiquement des sondes dans une scène par minimisation d’une fonction d’erreur. Nous guidons les sondes vers les sites d’échantillonnage optimaux en appliquant la descente de gradient à une fonction d’erreur qui représente la similarité entre la structure en construction et un ensemble de référence. En utilisant la pondération inverse à la distance comme fonction interpolante, nous avons construit avec fiabilité des ensembles de sondes dans trois scènes. En comparant nos résultats avec ceux produits par un ensemble de sondes de référence placées sur une grille régulière, nous atteignons théoriquement notre objectif dans une des trois scènes, où nous obtenons des valeurs d’erreur inférieures à la référence avec beaucoup moins de sondes. Nous avons eu des succès partiels dans les autres scènes, selon le nombre d’échantillons utilisés. / Diffuse global illumination within a 3D scene can be approximated in real time using irradiance probes. Probe placement typically relies on significant human input, and final quality of the approximation is often left to the subjectivity of a lighting artist. As demand for realism in rendering increases, the need to enhance the quality of such approximations is greater. We propose a method to automatically place probes in a scene by minimizing an error function. We guide probes to optimal sampling locations by applying gradient descent to an error function that represents similarity between our interpolated results and reference irradiance values. Using weighted nearest neighbour interpolation, we were able to reliably construct probe sets with minimal input in three scenes. Comparing our results to those produced by a set of probes placed on a 3D grid, we were theoretically successful in one scene, in which we could obtain lower error values with fewer probes. We obtained partial success in the other scenes, depending on the number of samples used.

En milieu industriel, si l'analyse en ligne d'effluents gazeux à l'aide de la chromatographie en phase gazeuse est actuellement réalisée sans difficultés majeure, l'analyse des liquides reste une des principales problématiques à résoudre. En effet, comparée à une analyse réalisée au laboratoire, l'analyse en ligne d'un échantillon liquide permettrait de s'affranchir de l'étape de prélèvement et de préparation avant injection ainsi que des problèmes de contamination et de représentativité de l'échantillon. Des systèmes d'injection de liquide en ligne sont actuellement disponibles, cependant, des difficultés d'injection liées à la discrimination des analytes sont rencontrées. C'est dans ce contexte qu'une vanne dédiée à l'injection des liquides en ligne a été développée, puis validée en laboratoire, et enfin mise en œuvre sur des applications industrielles pétrolières. Un tout autre enjeu, lié entre autres à la réduction des coûts de maintenance et d'installation, ainsi qu'à la compatibilité de systèmes analytiques destinés à l'industrie et aux micro-pilotes, a orienté des développements instrumentaux vers la miniaturisation des systèmes. Un assemblage de différentes briques technologiques a ensuite été réalisé afin d'évaluer la faisabilité d'un système miniaturisé incorporant la technologie d'injection des liquides en ligne. Finalement et toujours dans ce contexte de miniaturisation, des colonnes monolithiques courtes ont été mises en œuvre en chromatographie en phase gazeuse à haute pression, au laboratoire pour commencer, puis sur des effluents industriels gazeux. Elles ont permis de réaliser des analyses très rapides avec une grande efficacité par unité de longueur tout en pouvant agir sur la sélectivité des colonnes grâce à un contrôle de leurs propriétés de surface / In industry, although on-line analysis of gaseous effluents using gas chromatography is carried out without major difficulty, the analysis of liquids remains problematic and is one of the main issues to be solved. Indeed, compared to an analysis carried out in a laboratory, the on-line analysis of a liquid sample would bypass the steps of sampling and preparation prior to injection and would avoid problems of contamination and representativeness of the sample. Systems for injecting liquids on-line are currently available; however, difficulties are encountered, due to the discrimination of analytes. It is in this context that a valve dedicated to the on-line injection of liquids was developed, validated under laboratory conditions and finally implemented in the oil industry. Another issue, related, amongst other things, to the reduction of maintenance and installation costs, as well as to the compatibility of analytical systems for industry and for micro-pilots, steered instrumental developments towards the miniaturization of systems. Different technological bricks were therefore brought together to assess the feasibility of a miniaturized system involving the technology for on-line injection of liquid. Finally, and still in the context of miniaturization, short monolithic columns were implemented in gaseous phase chromatography at high pressure, first in the laboratory and then on industrial gas effluents. They allowed very fast analyses to be performed which had greater efficiency per unit of length while still being able to act on the selectivity of the columns thanks to the control of their surface properties

L’émergence récente de grands réseaux, surtout réseaux sociaux en ligne (OSN), a révélé la difficulté de crawler le réseau complet et a déclenché le développement de nouvelles techniques distribuées. Dans cette thèse, nous concevons et analysons des algorithmes basés sur les marches aléatoires et la diffusion pour l'échantillonnage, l'estimation et l'inférence des fonctions des réseaux. La thèse commence par le problème classique de trouver les valeurs propres dominants et leurs vecteurs propres de matrices de graphe symétriques, comme la matrice Laplacienne de graphes non orientés. En utilisant le fait que le spectre est associé à une équation de type différentiel Schrödinger, nous développons des techniques évolutives à l’aide de la diffusion sur le graphe. Ensuite, nous considérons l’échantillonnage des fonctions de réseau (comme somme et moyenne) en utilisant les marches aléatoires sur le graphe. Afin d'éviter le temps «burn-in» de marche aléatoire, avec l'idée de régénération à un nœud fixe, nous développons un estimateur de la fonction de somme qui est non asymptotiquement non-biaisé et dérivons une approximation à la postérieure Bayésienne. La dernière partie de la thèse étudie l'application de la théorie des valeurs extrêmes pour faire une inférence sur les événements extrêmes à partir des échantillons stationnaires des différentes marches aléatoires pour l’échantillonnage de réseau / The recent emergence of large networks, mainly due to the rise of online social networks, brought out the difficulty to gather a complete picture of a network and it prompted the development of new distributed techniques. In this thesis, we design and analyze algorithms based on random walks and diffusion for sampling, estimation and inference of the network functions, and for approximating the spectrum of graph matrices. The thesis starts with the classical problem of finding the dominant eigenvalues and the eigenvectors of symmetric graph matrices like Laplacian of undirected graphs. Using the fact that the eigenspectrum is associated with a Schrödinger-type differential equation, we develop scalable techniques with diffusion over the graph and with gossiping algorithms. They are also adaptable to a simple algorithm based on quantum computing. Next, we consider sampling and estimation of network functions (sum and average) using random walks on graph. In order to avoid the burn-in time of random walks, with the idea of regeneration at its revisits to a fixed node, we develop an estimator for the aggregate function which is non-asymptotically unbiased and derive an approximation to its Bayesian posterior. An estimator based on reinforcement learning is also developed making use of regeneration. The final part of the thesis deals with the use of extreme value theory to make inference from the stationary samples of the random walks. Extremal events such as first hitting time of a large degree node, order statistics and mean cluster size are well captured in the parameter “extremal index”. We theoretically study and estimate extremal index of different random walk sampling techniques

Dans cette thèse, nous étudions les graphes aléatoires en utilisant des outils de la théorie des matrices aléatoires et l’analyse probabilistique afin de résoudre des problèmes clefs dans le domaine des réseaux complexes et Big Data. Le premier problème qu’on considère est de détecter un sous graphe Erdős–Rényi G(m,p) plante dans un graphe Erdős–Rényi G(n,q). Nous dérivons les distributions d’une statistique basée sur les propriétés spectrales d’une matrice définie du graphe. Ensuite, nous considérons le problème de la récupération des sommets du sous graphe en présence de l’information supplémentaire. Pour cela nous utilisons l’algorithme «Belief Propagation». Le BP sans informations supplémentaires ne réussit à la récupération qu’avec un SNR effectif lambda au-delà d’un seuil. Nous prouvons qu’en présence des informations supplémentaires, ce seuil disparaît et le BP réussi pour n’importe quel lambda. Finalement, nous dérivons des expressions asymptotiques pour PageRank sur une classe de graphes aléatoires non dirigés appelés « fast expanders », en utilisant des techniques théoriques à la matrice aléatoire. Nous montrons que PageRank peut être approché pour les grandes tailles du graphe comme une combinaison convexe du vecteur de dégré normalisé et le vecteur de personnalisation du PageRank, lorsque le vecteur de personnalisation est suffisamment délocalisé. Par la suite, nous caractérisons les formes asymptotiques de PageRank sur le Stochastic Block Model (SBM) et montrons qu’il contient un terme de correction qui est fonction de la structure de la communauté. / In this thesis, we study random graphs using tools from Random Matrix Theory and probability to tackle key problems in complex networks and Big Data. First we study graph anomaly detection. Consider an Erdős-Rényi (ER) graph with edge probability q and size n containing a planted subgraph of size m and probability p. We derive a statistical test based on the eigenvalue and eigenvector properties of a suitably defined matrix to detect the planted subgraph. We analyze the distribution of the derived test statistic using Random Matrix Theoretic techniques. Next, we consider subgraph recovery in this model in the presence of side-information. We analyse the effect of side-information on the detectability threshold of Belief Propagation (BP) applied to the above problem. We show that BP correctly recovers the subgraph even with noisy side-information for any positive value of an effective SNR parameter. This is in contrast to BP without side-information which requires the SNR to be above a certain threshold. Finally, we study the asymptotic behaviour of PageRank on a class of undirected random graphs called fast expanders, using Random Matrix Theoretic techniques. We show that PageRank can be approximated for large graph sizes as a convex combination of the normalized degree vector and the personalization vector of the PageRank, when the personalization vector is sufficiently delocalized. Subsequently, we characterize asymptotic PageRank on Stochastic Block Model (SBM) graphs, and show that it contains a correction term that is a function of the community structure.

Les artistes apprécient les images vectorielles car elles sont compactes et facilement manipulables. Cependant, beaucoup d’artistes expriment leur créativité en dessinant, en peignant ou encore en prenant des photographies. Digitaliser ces contenus produit des images rasterisées. L’objectif de cette thèse est de convertir des images rasterisées en images vectorielles qui sont facilement manipulables. Nous avons formulé le problème de vectorisation comme un problème de minimisation d’énergie que nous avons défini par deux termes. Le premier terme, plutôt classique, mesure la fidélité de l’image vectorielle générée avec l’image rasterisée d’origine. La nouveauté principale est le second terme qui mesure la simplicité de l’image vectorielle générée. Le terme de simplicité est global et contient des variables discrètes, ce qui rend sa minimisation difficile. Nous avons proposé deux algorithmes de vectorisation : un pour la vectorisation de croquis et un autre pour la vectorisation multicouches d’images couleurs. Ces deux algorithmes commencent par extraire des primitives géométriques (un squelette pour les croquis et une segmentation pour les images couleurs) qu’ils assemblent ensuite pour former l’image vectorielle. Dans la dernière partie de la thèse, nous proposons un nouvel algorithme qui est capable de vectoriser des croquis sans étapes préliminaires : on extrait et assemble les primitives simultanément. Nous montrons le potentiel de ce nouvel algorithme pour une variété de problèmes de vision par ordinateur comme l’extraction de réseaux linéiques, l’extraction d’objets et la compression d’images. / Artists appreciate vector graphics for their compactness and editability. However many artists express their creativity by sketching, painting or taking photographs. Digitizing these images produces raster graphics. The goal of this thesis is to convert raster graphics into vector graphics that are easy to edit. We cast image vectorization as an energy minimization problem. Our energy is a combination of two terms. The first term measures the fidelity of the vector graphics to the input raster graphics. This term is a standard term for image reconstruction problems. The main novelty is the second term which measures the simplicity of the vector graphics. The simplicity term is global and involves discrete unknowns which makes its minimization challenging. We propose two stochastic optimizations for this formulation: one for the line drawing vectorization problem and another one for the color image vectorization problem. These optimizations start by extracting geometric primitives (skeleton for sketches and segmentation for color images) and then assembling these primitives together to form the vector graphics. In the last chapter we propose a generic optimization method for the problem of geometric shape extraction. This new algorithm does not require any preprocessing step. We show its efficiency in a variety of vision problems including line network extraction, object contouring and image compression.

Les variations d’efficacité du traitement visuel dans le temps ont été étudiées par échantillonnage temporel aléatoire. Vingt-quatre adultes ont identifié des stimuli composés de bruit blanc visuel et d’images d’objets familiers (expérience 1) ou de visages célèbres (expérience 2). Le ratio signal-bruit variait à travers le temps selon des fonctions d’échantillonnage générées par l’intégration d’ondes sinusoïdales de différentes fréquences (5 à 55 Hz) et de phases et amplitudes aléatoires. Des vecteurs de classification (VC) temporels ont été calculés en soustrayant la somme pondérée des ratios signal-bruit associés aux mauvaises réponses de celle associée aux bonnes réponses. Des images de classification (IC) temps-fréquence ont été obtenues en appliquant la même procédure aux résultats d’analyses temps-fréquence réalisées sur la fonction d’échantillonnage de chaque essai. Les VC temporels des deux expériences sont très variables entre les participants. Par contre, les IC temps-fréquence sont remarquablement similaires à travers les participants (cohérence inter-sujets de .93 et .57 pour l’expérience 1 et 2 respectivement). Des comparaisons par test t nous indiquent de nombreuses différences entre les IC temps-fréquence des objets et visages familiers, mais aussi des objets non familiers et des mots analysés dans des études précédentes. Ainsi, ces IC sont sensibles à la classe de stimuli présentés, mais aussi à la familiarité de ces derniers. Les résultats témoignent d’une variation rapide dans l’efficacité de l’encodage visuel durant les 200 premières millisecondes d’exposition au stimulus et suggèrent que les IC du domaine temps-fréquence reflètent un aspect hautement fondamental du traitement visuel, hypothétiquement rattaché aux oscillations cérébrales. / Variations in visual processing effectiveness through time were investigated using random temporal stimulus sampling. Twenty-four adults named photographs of either familiar objects (experiment 1) or famous faces (experiment 2). Stimuli were made by a linear combination of the target image and high density white visual noise. Signal-to-noise ratio varied throughout the 200 ms stimulus duration. A new temporal sampling function was generated on each trial by the integration of random amplitude and phase sinusoidal waves of frequency between 5 and 55 Hz (in 5 Hz steps). Temporal classification vectors (CV) were calculated by subtracting the weighted sum of the signal-to-noise ratio associated to errors from that associated to correct responses. Time-frequency classification images (CI) were obtained by applying the same procedure on the outcome of time-frequency analyses applied to the sampling functions of each trial. In both experiments, the temporal CVs were highly variable across participants, but the time-frequency CIs were remarkably similar across participants (inter-subject coherence of .93 and .57 for experiments 1 and 2 respectively). T-tests revealed multiple differences between the time-frequency CIs obtained with familiar objects and faces, but also with non-familiar objects and words analyzed in previous studies. Therefore, theses CIs are sensitive to stimulus type, but also to stimulus familiarity. The present results indicate rapid variations of visual encoding effectiveness in the initial 200 ms of stimulus exposure and suggests that the time-frequency CIs tap a highly fundamental aspect of visual processing, hypothetically linked to brain oscillations.

Pour construire des intervalles de confiance, nous pouvons utiliser diverses approches bootstrap. Nous avons un problème pour le contexte spécifique d’un paramètre de proportion lorsque l’estimateur usuel, la proportion de succès dans l’échantillon ˆp, est nul. Dans un contexte classique d’observations indépendantes et identiquement distribuées (i.i.d.) de la distribution Bernoulli, les échantillons bootstrap générés ne contiennent que des échecs avec probabilité 1 et les intervalles de confiance bootstrap deviennent dégénérés en un seul point, soit le point 0. En contexte de population finie, nous sommes confrontés aux mêmes problèmes lorsqu’on applique une méthode bootstrap à un échantillon de la population ne contenant que des échecs. Une solution possible s’inspire de l’estimateur utilisé dans les méthodes de [Wilson, 1927] et [Agresti et Coull, 1998] où ceux-ci considèrent ˜p l’estimateur qui prend la proportion de succès d’un échantillon augmenté auquel on a ajouté deux succès et deux échecs. La solution que nous introduisons consiste à effectuer le bootstrap de la distribution de ˆp mais en appliquant les méthodes bootstrap à l’échantillon augmenté de deux succès et deux échecs, tant en statistique classique que pour une population finie. Les résultats ont démontré qu’une version de la méthode percentile est la méthode bootstrap la plus efficace afin d’estimer par intervalle de confiance un paramètre de proportion autant dans un contexte i.i.d. que dans un contexte d’échantillonnage avec le plan aléatoire simple sans remise. Nos simulations ont également démontré que cette méthode percentile pouvait compétitionner avantageusement avec les meilleures méthodes traditionnelles. / A few bootstrap approaches exist to create confidence intervals. Some difficulties appear for the specific case of a proportion when the usual estimator, the proportion of success in a sample, is 0. In the classical case where the observations are independently and identically distributed (i.i.d.) from a Bernoulli distribution, the bootstrap samples only contain zeros with probability 1 and the resulting bootstrap confidence intervals are degenerate at the value 0. We are facing the same problem in the survey sampling case when we apply the bootstrap method to a sample with all observations equal to 0. A possible solution is suggested by the estimator found in the confidence intervals of [Wilson, 1927] and [Agresti et Coull, 1998] where they use ˜p the proportion of success in a augmented sample consisting of adding two successes and two failures to the original sample. The proposed solution is to use the bootstrap method on ˆp but where the bootstrap is based on the augmented sample with two additional successes and failures, whether the sample comes from i.i.d. Bernoulli variables or from a simple random sample. Results show that a version of the percentile method is the most efficient bootstrap method to construct confidence intervals for a proportion both in the classical setting or in the case of a simple random sample. Our results also show that this percentile interval can compete with the best traditional methods.

Les matériaux actuellement utilisés comme capteurs passifs de polluants atmosphériques, la mousse de polyuréthane et la résine XAD®-2, ne sont optimisés ni pour l'adsorption de composés polaires ni pour le captage de particules. Pour remédier à ces limitations, la mousse de carbure de silicium (SiC) est proposée comme alternative. Plusieurs campagnes de mesures ont été mises en place pour comparer SiC et XAD®-2. Les composés recherchés étaient des HAP, des PCB et des pesticides.Une méthode d'analyse combinant ASE, SPE et SPME a été développée et optimisée pour ces polluants. Celle-ci permet d'atteindre de faibles limites de détection et quantification pour les composés recherchés.Les campagnes réalisées montrent que la mousse de SiC est toujours plus efficace que la résine XAD®-2 pour le piégeage de composés particulaires et polaires. De plus, la SiC peut être greffée avec du carbone ou des nanotubes de carbone pour augmenter sa surface spécifique, ce qui la rend également plus performante pour l'adsorption de composés volatils. Les débits d'échantillonnage moyens de la mousse ont été calculés et sont comparable aux valeurs rapportées dans la littérature pour la résine XAD®-2. / Materials currently used as passive samplers for atmospheric pollutants, polyurethane foam and XAD®-2 resin, are not suited ta trapping polar compounds nor particles. Ta overcome these limitations, silicon carbide (SiC) foam is presented as an alternative. Several sampling campaigns monitoring PAH, PCB and pesticides were done ta compare SiC and XAD®-2. An analytical method coupling ASE, SPE and SPME was developed and optimised for these pollutants. lt allowed low limits of detection and quantification ta be reached for all compounds of interest.Sampling campaigns showed that SiC foam is consistently more efficient than XAD®-2 resin at trapping particulate and polar compounds. Moreover, SiC foam can be grafted with carbon or carbon nanotubes ta increase its specific surface area, which also makes it better at adsorbing volatile compounds. Average sampling rates were calculated for SiC foam and they are comparable ta the values reported in the literature for XAD®-2 resin.

La première partie de cette thèse concerne l'inférence de modèles statistiques non normalisés. Nous étudions deux méthodes d'inférence basées sur de l'échantillonnage aléatoire : Monte-Carlo MLE (Geyer, 1994), et Noise Contrastive Estimation (Gutmann et Hyvarinen, 2010). Cette dernière méthode fut soutenue par une justification numérique d'une meilleure stabilité, mais aucun résultat théorique n'avait encore été prouvé. Nous prouvons que Noise Contrastive Estimation est plus robuste au choix de la distribution d'échantillonnage. Nous évaluons le gain de précision en fonction du budget computationnel. La deuxième partie de cette thèse concerne l'échantillonnage aléatoire approché pour les distributions de grande dimension. La performance de la plupart des méthodes d’échantillonnage se détériore rapidement lorsque la dimension augmente, mais plusieurs méthodes ont prouvé leur efficacité (e.g. Hamiltonian Monte Carlo, Langevin Monte Carlo). Dans la continuité de certains travaux récents (Eberle et al., 2017 ; Cheng et al., 2018), nous étudions certaines discrétisations d’un processus connu sous le nom de kinetic Langevin diffusion. Nous établissons des vitesses de convergence explicites vers la distribution d'échantillonnage, qui ont une dépendance polynomiale en la dimension. Notre travail améliore et étend les résultats de Cheng et al. pour les densités log-concaves. / The first part of this thesis concerns the inference of un-normalized statistical models. We study two methods of inference based on sampling, known as Monte-Carlo MLE (Geyer, 1994), and Noise Contrastive Estimation (Gutmann and Hyvarinen, 2010). The latter method was supported by numerical evidence of improved stability, but no theoretical results had yet been proven. We prove that Noise Contrastive Estimation is more robust to the choice of the sampling distribution. We assess the gain of accuracy depending on the computational budget. The second part of this thesis concerns approximate sampling for high dimensional distributions. The performance of most samplers deteriorates fast when the dimension increases, but several methods have proven their effectiveness (e.g. Hamiltonian Monte Carlo, Langevin Monte Carlo). In the continuity of some recent works (Eberle et al., 2017; Cheng et al., 2018), we study some discretizations of the kinetic Langevin diffusion process and establish explicit rates of convergence towards the sampling distribution, that scales polynomially fast when the dimension increases. Our work improves and extends the results established by Cheng et al. for log-concave densities.

La matière sombre est considérée comme l'un des plus grands mystères dans la cosmologie moderne. En effet, on peut dire que l’on connaît plus sur ce que la matière sombre n'est pas que sur sa vraie nature. La collaboration SuperCDMS travaille sans répit pour réussir à faire la première détection directe de la matière sombre. À cet effet, la collaboration a eu recours à plusieurs expériences et simulations à diverses échelles, pouvant aller de l'usage d'un seul détecteur semi-conducteur, jusqu'à la création d'expériences à grande échelle qui cherchent à faire cette première détection directe de la matière sombre. Dans ce texte, on verra différentes méthodes pour nous aider à mieux comprendre les erreurs systématiques liées à la position du détecteur utilisé dans le cadre des expériences IMPACT@TUNL et IMPACT@MTL, soit l'usage des simulations et de la radiologie industrielle respectivement. On verra aussi comment l'implémentation de la méthode de réduction de variance connue comme échantillonnage préférentiel, peut aider à améliorer l'exécution des simulations de l'expérience à grande échelle planifiée pour le laboratoire canadien SNOLAB. En outre, on verra comment l'échantillonnage préférentiel s'avère utile non seulement pour mieux profiter des ressources disponibles pour la collaboration, mais aussi pour avoir une meilleure compréhension des source de bruits de fond qui seront présentes à SNOLAB, tels que les signaux générés par la désintégration radioactive de divers isotopes. / Dark matter is one of the biggest mysteries of modern-day cosmology. Simply put, we know much more about what it is not, rather than what it actually is. The SuperCDMS collaboration works relentlessly toward making the first direct detection of this type of matter. To this effect, multiple experiments and simulations have been performed, ranging from small-scale testing of the detectors to large-scale, long-term experiments, looking for the actual detection of dark matter. In this work, I will analyze different methods to help understand the systematic errors linked to detector position in regard to the small-scale experiments IMPACT@TUNL and IMPACT@MTL, through simulation and industrial radiography respectively. We will also see how the implementation of the variance reduction method known as importance sampling can be used to improve the simulation performance of the large-scale experiment in the Canadian laboratory SNOLAB. Additionally, we will see how this method can provide not only better management of the computing resources available to the collaboration, but also how it can be used to better the understanding of the background noises, such as the signals generated by radioactive decay of different isotopes, that will be present at SNOLAB.