Unsupervised models can provide supplementary soft constraints to help classify new, "target" data since similar instances in the target set are more likely to share the same class label. Such models can also help detect possible differences between training and target distributions, which is useful in applications where concept drift may take place, as in transfer learning settings. This contribution describes two general frameworks that take as input class membership estimates from existing classifiers learnt on previously encountered "source" data, as well as a set of cluster labels from a cluster ensemble operating solely on the target data to be classified, and yield a consensus labeling of the target data. One of the proposed frameworks admits a wide range of loss functions and classification/clustering methods and exploits properties of Bregman divergences in conjunction with Legendre duality to yield a principled and scalable approach. The other approach is built on probabilistic mixture models and provides additional flexibility of distributed computation that is useful when the target data cannot be gathered in a single place for privacy or security concerns. A variety of experiments show that the proposed frameworks can yield results substantially superior to those provided by popular transductive learning techniques or by naively applying classifiers learnt on the original task to the target data. / text

Compressed sensing and matrix completion are two new data acquisition techniques whose efficiency is achieved by exploring low dimensional structures in high dimensional data. Despite the combinatorial nature of compressed sensing and matrix completion, there has been significant development of computationally efficient algorithms which can produce accurate desired solutions to these problems. In this thesis, we are concerned with the development of low per iteration computational complexity algorithms for compressed sensing and matrix completion. First, we derive a locally optimal stepsize selection rule for the simplest iterative hard thresholding algorithm for matrix completion, and obtain a simple yet efficient algorithm. It is observed to have average case performance superior in some aspects to other matrix completion algorithms. To balance the fast convergence rates of more sophisticated recovery algorithms with the low per iteration computational cost of simple line-search algorithms, we introduce a family of conjugate gradient iterative hard thresholding algorithms for both compressed sensing and matrix completion. The theoretical results establish recovery guarantees for the restarted and projected variants of the algorithms, while the empirical performance comparisons establish significant computational advantages of the proposed methods over other hard thresholding algorithms. Finally, we introduce an alternating steepest descent method and a scaled variant especially designed for the matrix completion problem based on a simple factorization model of the low rank matrix. The computational efficacy of this method is achieved by reducing the high per iteration computational cost of the second order method and fully exploring the numerical linear algebra structure in the algorithm. Empirical evaluations establish the effectiveness of the proposed algorithms, compared with other state-of-the-art algorithms.

Alternating minimization (AltMin) is a generic term for a widely popular approach in non-convex learning: often, it is possible to partition the variables into two (or more) sets, so that the problem is convex/tractable in one set if the other is held fixed (and vice versa). This allows for alternating between optimally updating one set of variables, and then the other. AltMin methods typically do not have associated global consistency guarantees; even though they are empirically observed to perform better than methods (e.g. based on convex optimization) that do have guarantees. In this thesis, we obtain rigorous performance guarantees for AltMin in three statistical learning settings: low rank matrix completion, phase retrieval and learning sparsely-used dictionaries. The overarching theme behind our results consists of two parts: (i) devising new initialization procedures (as opposed to doing so randomly, as is typical), and (ii) establishing exponential local convergence from this initialization. Our work shows that the pursuit of statistical guarantees can yield algorithmic improvements (initialization in our case) that perform better in practice. / text

Nous proposons dans cette thèse de développer une méthode de restauration aveugle d'images flouées et bruitées où aucune connaissance a priori n'est exigée. Ce manuscrit est composé de trois chapitres : le 1er chapitre est consacré aux travaux de l'état de l'art. Les approches d'optimisation pour la résolution du problème de restauration y sont d'abord discutées. Ensuite les principales méthodes de restauration, dites semi-aveugles car nécessitant un minimum de connaissance a priori sont analysées. Parmi ces méthodes, cinq sont retenues pour évaluation. Le 2ème chapitre est dédié à la comparaison des performances des méthodes retenues dans le chapitre précédent. Les principaux critères objectifs d'évaluation de la qualité des images restaurées sont présentés. Parmi ces critères, la norme L1 de l'erreur d'estimation est sélectionnée. L'étude comparative menée sur une banque d'images monochromes, dégradées artificiellement par deux fonctions floues de supports différents et trois niveaux de bruit a permis de mettre en évidence les deux méthodes les plus pertinentes. La première repose sur une approche alternée mono-échelle où la PSF et l'image sont estimées dans une seule étape. La seconde utilise une approche hybride multi-échelle qui consiste tout d'abord à estimer de manière alternée la PSF et une image latente, puis dans une étape suivante séquentielle, à restaurer l'image. Dans l'étude comparative conduite, l'avantage revient à cette dernière. Les performances de ces méthodes serviront de référence pour comparer ensuite la méthode développée. Le 3ème chapitre porte sur la méthode développée. Nous avons cherché à rendre aveugle l'approche hybride retenue dans le chapitre précédent tout en améliorant la qualité d'estimation de la PSF et de l'image restaurée. Les contributions ont porté sur plusieurs points. Une première série d'améliorations concerne la redéfinition des échelles, celle de l'initialisation de l'image latente à chaque niveau d'échelle, l'évolution des paramètres pour la sélection des contours pertinents servant de support à l'estimation de la PSF et enfin, la définition d'un critère d'arrêt aveugle. Une seconde série de contributions a porté sur l'estimation aveugle des deux paramètres de régularisation impliqués pour éviter d'avoir à les fixer empiriquement. Chaque paramètre est associé à une fonction coût distincte l'une pour l'estimation de la PSF et la seconde pour l'estimation d'une image latente. Dans l'étape séquentielle qui suit, nous avons cherché à affiner le support de la PSF estimée dans l'étape alternée, avant de l'exploiter dans le processus de restauration de l'image. A ce niveau, la seule connaissance a priori nécessaire est une borne supérieure du support de la PSF. Les différentes évaluations conduites sur des images monochromes et hyperspectrales dégradées artificiellement par plusieurs flous de type mouvement, de supports différents, montrent une nette amélioration de la qualité de restauration obtenue par l'approche développée par rapport aux deux meilleures approches de l'état de l'art retenues. / We propose in this thesis manuscript to develop a blind restoration method of single component blurred and noisy images where no prior knowledge is required. This manuscript is composed of three chapters: the first chapter focuses on state-of-art works. The optimization approaches for resolving the restoration problem are discussed first. Then, the main methods of restoration, so-called semi-blind ones because requiring a minimum of a priori knowledge are analysed. Five of these methods are selected for evaluation. The second chapter is devoted to comparing the performance of the methods selected in the previous chapter. The main objective criteria for evaluating the quality of the restored images are presented. Of these criteria, the l1 norm for the estimation error is selected. The comparative study conducted on a database of monochromatic images, artificially degraded by two blurred functions with different support size and three levels of noise, revealed the most two relevant methods. The first one is based on a single-scale alternating approach where both the PSF and the image are estimated alternatively. The second one uses a multi-scale hybrid approach, which consists first of alternatingly estimating the PSF and a latent image, then in a sequential next step, restoring the image. In the comparative study performed, the benefit goes to the latter. The performance of both these methods will be used as references to then compare the newly designed method. The third chapter deals with the developed method. We have sought to make the hybrid approach retained in the previous chapter as blind as possible while improving the quality of estimation of both the PSF and the restored image. The contributions covers a number of points. A first series concerns the redefinition of the scales that of the initialization of the latent image at each scale level, the evolution of the parameters for the selection of the relevant contours supporting the estimation of the PSF and finally the definition of a blind stop criterion. A second series of contributions concentrates on the blind estimation of the two regularization parameters involved in order to avoid having to fix them empirically. Each parameter is associated with a separate cost function either for the PSF estimation or for the estimation of a latent image. In the sequential step that follows, we refine the estimation of the support of the PSF estimated in the previous alternated step, before exploiting it in the process of restoring the image. At this level, the only a priori knowledge necessary is a higher bound of the support of the PSF. The different evaluations performed on monochromatic and hyperspectral images artificially degraded by several motion-type blurs with different support sizes, show a clear improvement in the quality of restoration obtained by the newly designed method in comparison to the best two state-of-the-art methods retained.

La première partie de cette thèse (articles I et II) est consacrée à l'étude du comportement asymptotique des solutions d'un système dynamique du second ordre avec dissipation évanescente. Le système dynamique est étudié dans sa version continue et dans sa version discrète via un algorithme.La deuxième partie de cette thèse (articles III à VI) est consacrée à l'étude de plusieurs algorithmes de type proximal. Nous montrons que ces algorithmes convergent vers des solutions de certains problèmes de minimisation. Dans chaque cas, une application est donnée dans le cadre de la décomposition de domaine pour les EDP. / The first part of this thesis is devoted to the study of the asymptotic behavior of solutions of a second order dynamic system with vanishing dissipation. The dynamic system is studied in its continuous version and in its discrete version via an algorithm.The second part is about the study of several proximal-type algorithms. We show that these algorithms converge to solutions of some minimization problems. In each case, an application is given in the area of domain decomposition for PDE's.

Slepá dekonvoluce je metoda, při které je rozptylová funkce a skutečný obraz rekonstruován zároveň. Cílem této práce je představit různé metody slepé dekonvoluce a najít optimální metodu rekonstrukce původního obrazu a rozptylové funkce. Jako nejvhodnější metoda slepé dekonvoluce byl zvolen algoritmus střídavé minimalizace, který byl upraven a testován. Vlastnosti navrženého algoritmu byly testovány na uměle degradovaných datech a na reálných datech pořízených skenovacím transmisním elektronovým mikroskopem. Účinnost algoritmu byla hodnocena hned několika hodnotícími kritérii. Byla zjištěna omezení algoritmu a tím specifikováno jeho využití.

<div>Smart warehouses have become more popular in these days, with Automated Guided Vehicles (AGVs) being used for order pickups. They also allow efficient cost management with optimized storage and retrieval. Moreover, optimization of resources in these warehouses is essential to ensure maximum efficiency. In this thesis, we consider a three dimensional smart warehouse system equipped with heterogeneous AGVs (i.e., having different speeds). We propose scheduling and placement policies that jointly consider all the different design parameters including the scheduling decision probabilities and storage assignment locations. In order to provide differentiated service levels, we propose a prioritized probabilistic scheduling and placement policy to minimize a weighted sum of mean latency and latency tail probability (LTP). Towards this goal, we first derive closed-form expressions for the mean latency and LTP. Then, we formulate an optimization problem to jointly optimize a weighted sum of both the mean latency and LTP. The optimization problem is solved efficiently over the scheduling and decision variables. For a given placement of the products, scheduling decisions of customers’ orders are solved optimally and derived in closed forms. Evaluation results demonstrate a significant improvement of our policy (up to 32%) as compared to the state of other algorithms, such as the Least Work Left policy and Join the Shortest Queue policy, and other competitive baselines.</div>

This Master Thesis deals with image restoration using deconvolution. The terms introducing into deconvolution theory like two-dimensional signal, distortion model, noise and convolution are explained in the first part of thesis. The second part deals with deconvolution methods via utilization of the Bayes approach which is based on the probability principle. The third part is focused on the Alternating Minimization Algorithm for Multichannel Blind Deconvolution. At the end this algorithm is written in Matlab with utilization of the NAG C Library. Then comparison of different optimization methods follows (simplex, steepest descent, quasi-Newton), regularization forms (Tichonov, Total Variation) and other parameters used by this deconvolution algorithm.