La classification de signaux en grande dimension rend nécessaire la sélection d'un petit nombre de structures caractéristiques pour représenter chaque signal. Les approximations non-linéaires donnent lieu à des représentations concises, parce qu'elles s'adaptent à la structure de chaque signal analysé. Leur emploi est prometteur. Une première partie du travail du thèse définit des représentations adaptatives rapides de signaux comme combinaisons linéaires d'atomes extraits d'un dictionnaire de vecteurs. A partir de l'algorithme de Matching Pursuit, plusieurs méthodes itératives sont proposées pour mettre en lumière les structures caractéristiques des signaux sonores. Le Matching Pursuit Harmonique décompose un signal en composantes harmoniques élémentaires. Le Matching Pursuit "Chirpé" extrait les variations de fréquence instantanée en tirant parti d'une analyse fine des crêtes du dictionnaire de Gabor multi-échelle. Les approximations fournies par le Matching Pursuit Haute-résolution préservent les transitoires des signaux analysés, en imposant des contraintes de résolution temporelle. Nous accélérons ces techniques en employant des sous-dictionnaires de maxima locaux. Notre travail est consacré dans un second temps à l'étude de l'"Analyse Discriminante Non-linéaire". Pour classifier des signaux, les méthodes d'Analyse Discriminante Linéaire réduisent la dimension en les projetant sur un sous-espace pré-déterminé. Une projection adaptative, en fonction du signal analysé, extrait de celui-ci des caractéristiques qui lui sont propres. Celles-ci le distinguent et permettent de le classifier efficacement. Nous déterminons la stratégie optimale de projection adaptative pour la classification de bruits gaussiens colorés. Afin de classifier des transitoires, nous explorons enfin une méthode utilisant les maxima du module de la transformée en ondelettes et des arbres de décision. Cette approche permet de surmonter les difficultés liées à l'invariance par translation des signaux à classifier.

<p>In this thesis we study approximation of negative plurisubharmonic functions by functions defined on strictly larger domains. We show that, under certain conditions, every function <i>u</i> that is defined on a bounded hyperconvex domain Ω in C<i>n</i><i> </i>and has essentially boundary values zero and bounded Monge-Ampère mass, can be approximated by an increasing sequence of functions {<i>u</i><i>j</i>} that are defined on strictly larger domains, has boundary values zero and bounded Monge-Ampère mass. We also generalize this and show that, under the same conditions, the approximation property is true if the function u has essentially boundary values G, where G is a plurisubharmonic functions with certain properties. To show these approximation theorems we use subextension. We show that if Ω_1 and Ω_2 are hyperconvex domains in C<i>n</i> and if u is a plurisubharmonic function on Ω_1 with given boundary values and with bounded Monge-Ampère mass, then we can find a plurisubharmonic function û defined on Ω_2, with given boundary values, such that û <= u on Ω and with control over the Monge-Ampère mass of û.</p>

Le placement de caméra en environnement virtuel consiste à positionner et orienter une caméra virtuelle 3D de façon à respecter un ensemble de propriétés visuelles ou cinématographiques définies par l'utilisateur. Réaliser cette tâche est difficile en pratique. En effet, l'utilisateur possède une vision claire du résultat qu'il souhaite obtenir en termes d'agencement des objets à l'image. Toutefois le processus classique de placement de caméra est particulièrement contre-intuitif. L'utilisateur doit effectuer une inversion mentale afin d'inférer la position et l'orientation de la caméra dans l'environnement 3D amenant au résultat souhaité. Des méthodes d'aide au placement de caméra apparaissent donc particulièrement profitables pour les utilisateurs. Dans cette thèse, nous identifions trois axes de recherche relativement peu couverts par la littérature dédiée au placement de caméra et qui nous apparaissent pourtant essentiels. D'une part, les approches existantes n'offrent que peu de flexibilité tant dans la résolution que dans la description d'un problème en termes de propriétés visuelles, en particulier lorsque celui-ci ne possède aucune solution. Nous proposons une méthode de résolution flexible qui calcule l'ensemble des solutions, maximisant la satisfaction des propriétés du problème, que celui-ci soit sur-contraint ou non. D'autre part, les méthodes existantes ne calculent qu'une seule solution, même lorsque le problème possède plusieurs classes de solutions équivalentes en termes de satisfaction de propriétés. Nous introduisons la méthode des volumes sémantiques qui calcule l'ensemble des classes de solutions sémantiquement équivalentes et propose un représentant de chacune d'elles à l'utilisateur. Enfin, le problème de l'occlusion, bien qu'essentiel dans la transmission de l'information, n'est que peu abordé par la communauté. En conséquence, nous présentons une nouvelle méthode de prise en compte de l'occlusion dans des environnements dynamiques temps réel.

L'objectif principal de cette thèse a été de développer des nouveaux outils mathématiques pour l'étude des phénomènes stochastiques en biologique moléculaire. Les modèles mathématiques pour la dynamique stochastique des réseaux de réactions biochimiques sont basés sur les processus de Markov à sauts. On propose des approximations hybrides pour les processus de Markov à sauts multi-échelles. En utilisant comme argument heuristique un développement limité du générateur du processus à sauts (procédé connu en chimie et en physique sous le nom de développement de Kramers-Moyal) nous identifions plusieurs types d'asymptotiques hybrides : processus déterministes par morceaux et diffusions hybrides. Le développement de Kramers-Moyal permet d'obtenir de manière systématique des modèles hybrides, qui sont simulés par la suite avec des algorithmes adaptés. Les approximations déterministes par morceaux sont étudiées avec des méthodes mathématiques rigoureuses. On montre la convergence faible du processus de Markov à sauts vers deux types de processus déterministes par morceaux : avec et sans sauts dans les variables continues. Les approximations hybrides peuvent être simplifiées davantage en utilisant des méthodes de moyennisation. On propose aussi quelques résultats dans cette direction.

<p>In the maximum solution equation problem a collection of equations are given over some algebraic structure. The objective is to find an assignment to the variables in the equations such that all equations are satisfied and the sum of the variables is maximised. We give tight approximability results for the maximum solution equation problem when the equations are given over finite abelian groups. We also prove that the weighted and unweighted versions of this problem have asymptotically equal approximability thresholds.</p><p>Furthermore, we show that the problem is equally hard to solve as the general problem even if each equation is restricted to contain at most three variables and solvable in polynomial time if the equations are restricted to contain at most two variables each. All of our results also hold for the generalised version of maximum solution equation where the elements of the group are mapped arbitrarily to non-negative integers in the objective function.</p>

<p>The thesis consists of four papers on combinatorial auctions and a summary. The first part is more of a practical nature and contains two papers. In the first paper, we study the performance of a caching technique in an optimal algorithm for a multi-unit combinatorial auction.</p><p>In the second paper, we compare the revenues from a second-price combinatorial auction against a second-price one-shot simultaneous auction. In particular, we show that when the synergy parameter is small, the combinatorial auction gives a higher expected revenue than the one-shot. This is in contrast to an earliear result by Krishna and Rosenthal. We also compare the two mechanisms under the assumption that bidders are risk-averse. Such bidders are more sensitive to financial loss (winner's curse) that they tend to bid less aggressively, which leads to lower revenues. Since a direct analytical approach turns out to be difficult, we present numerical results that show which auction mechanism maximizes the seller's revenue depending on the values of synergy and aversion parameter.</p><p>The second part is more theoretical. Here, we analyze the asymptotic performance of a greedy algorithm for a problem inspired by combinatorial auctions. In particular, we consider a special case in which every bid contains exactly 3 items, and use a Poisson process to model an auction with a random (Poisson) No. of bids. For this restricted case, winner determination problem is equivalent to a maximal 3-set packing on a weighted hypergraph, and hence NP-complete. However, the greedy algorithm approximates this special case within a factor of 3.</p><p>In the third paper, we compute the asymptotic expected size of the partial allocation and its corresponding expected total revenue from the greedy algorithm, for some distribution of bid prices.</p><p>In the final paper, we study the case of a deterministic number of bids, which is proportional to the number of distinguishable items in the auction, say M. Then, we prove that the number of bids allocated, suitably normalized, converges to a Normal random variable as M goes to infinity. As a prelude, we also prove that, both the number of bids allocated and those submitted, again suitably normalized, jointly converge in distribution to a continuous 2-dimensional Gaussian process as M goes to infinity.</p>

This thesis considers likelihood inferences for generalized linear models with additional random effects. The likelihood function involved ordinarily cannot be evaluated in closed form and numerical integration is needed. The theme of the thesis is a closed-form approximation based on Laplace's method. We first consider a special yet important case of the above general setting -- the Mantel-Haenszel-type model with overdispersion. It is seen that the Laplace approximation is very accurate for likelihood inferences in that setting. The approach and results on accuracy apply directly to the more general setting involving multiple parameters and covariates. Attention is then given to how to maximize out nuisance parameters to obtain the profile likelihood function for parameters of interest. In evaluating the accuracy of the Laplace approximation, we utilized Gauss-Hermite quadrature. Although this is commonly used, it was found that in practice inadequate thought has been given to the implementation. A systematic method is proposed for transforming the variable of integration to ensure that the Gauss-Hermite quadrature is effective. We found that under this approach the Laplace approximation is a special case of the Gauss-Hermite quadrature. / Graduation date: 1994

by Charles Rockland. / "June 1985." / Bibliography: p. 111-113. / Army Research Office Grant (DAAG29-84-K-0005)

We consider the scheduling problem of minimizing the average weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios compared to the previously best-known deterministic on-line algorithms, which are (4+epsilon)-competitive in either case. Our preemptive algorithm is 2-competitive, which actually meets the competitive ratio of the currently best randomized on-line algorithm for this scenario. Our nonpreemptive algorithm has a competitive ratio of 3.28. Both results are characterized by a surprisingly simple analysis; moreover, the preemptive algorithm also works in the less clairvoyant environment in which only the ratio of weight to processing time of a job becomes known at its release date, but neither its actual weight nor its processing time. In the corresponding nonpreemptive situation, every on-line algorithm has an unbounded competitive ratio

Nick De Claris. / "December 30, 1954." / Bibliography: p. 27. / Army Signal Corps Contract DA36-039 sc-42607 Project 132B Dept. of the Army Project 3-99-12-022