No description available.

Many problems in signal processing, machine learning and computer vision can be solved by learning low rank models from data. In computer vision, problems such as rigid structure from motion have been formulated as an optimization over subspaces with fixed rank. These hard-rank constraints have traditionally been imposed by a factorization that parameterizes subspaces as a product of two matrices of fixed rank. Whilst factorization approaches lead to efficient and kernelizable optimization algorithms, they have been shown to be NP-Hard in presence of missing data. Inspired by recent work in compressed sensing, hard-rank constraints have been replaced by soft-rank constraints, such as the nuclear norm regularizer. Vis-a-vis hard-rank approaches, soft-rank models are convex even in presence of missing data: but how is convex optimization solving a NP-Hard problem? This thesis addresses this question by analyzing the relationship between hard and soft rank constraints in the unsupervised factorization with missing data problem. Moreover, we extend soft rank models to weakly supervised and fully supervised learning problems in computer vision. There are four main contributions of our work: (1) The analysis of a new unified low-rank model for matrix factorization with missing data. Our model subsumes soft and hard-rank approaches and merges advantages from previous formulations, such as efficient algorithms and kernelization. It also provides justifications on the choice of algorithms and regions that guarantee convergence to global minima. (2) A deterministic \rank continuation" strategy for the NP-hard unsupervised factorization with missing data problem, that is highly competitive with the state-of-the-art and often achieves globally optimal solutions. In preliminary work, we show that this optimization strategy is applicable to other NP-hard problems which are typically relaxed to convex semidentite programs (e.g., MAX-CUT, quadratic assignment problem). (3) A new soft-rank fully supervised robust regression model. This convex model is able to deal with noise, outliers and missing data in the input variables. (4) A new soft-rank model for weakly supervised image classification and localization. Unlike existing multiple-instance approaches for this problem, our model is convex.

Ce mémoire de thèse à été réalisée dans le cadre d'une collaboration scientifique avec "La Manufacture Française des Pneumatiques Michelin". Il porte sur l'analyse mathématique et numérique de la convergence et de la stabilité de formulations mixtes ou hybrides de problèmes d'optimisation sous contrainte avec la méthode des multiplicateurs de Lagrange et dans le cadre de la méthode éléments finis étendus (XFEM). Tout d'abord, nous essayons de démontrer la stabilité de la discrétisation X-FEM pour le problème d'élasticité linéaire incompressible en statique. Le deuxième axe, qui représente le contenu principal de la thèse est dédié à l'étude de certaines méthodes de multiplicateur de Lagrange stabilisées. La particularité de ces méthodes est que la stabilité du multiplicateur est assurée par l'ajout de termes supplémentaires dans la formulation faible. Dans ce contexte, nous commençons par l'étude de la méthode de stabilisation de Barbosa-Hughes appliquée au problème de contact unilatéral sans frottement avec XFEM cut-off. Ensuite, nous construisons une nouvelle méthode basée sur des techniques de projections locales pour stabiliser un problème de Dirichlet dans le cadre de X-FEM et une approche de type domaine fictif. Nous faisons aussi une étude comparative entre la stabilisation avec la technique de projection locale et la stabilisation de Barbosa-Hughes. Enfin, nous appliquons cette nouvelle méthode de stabilisation aux problèmes de contact unilatéral en élastostatique avec frottement de Tresca dans le cadre de X-FEM. / This Ph.D. thesis was done in collaboration with "La Manufacture Française des Pneumatiques Michelin". It concerns the mathematical and numerical analysis of convergence and stability of mixed or hybrid formulation of constrained optimization problem with Lagrange multiplier method in the framework of the eXtended Finite Element Method (XFEM). First we try to prove the stability of the X-FEM discretization for incompressible elastostatic problem by ensured a LBB condition. The second axis, which present the main content of the thesis, is dedicated to the use of some stabilized Lagrange multiplier methods. The particularity of these stabilized methods is that the stability of the multiplier is provided by adding supplementary terms in the weak formulation. In this context, we study the Barbosa-Hughes stabilization technique applied to the frictionless unilateral contact problem with XFEM-cut-off. Then we present a new consistent method based on local projections for the stabilization of a Dirichlet condition in the framework of extended finite element method with a fictitious domain approach. Moreover we make comparative study between the local projection stabilization and the Barbosa-Hughes stabilization. Finally we use the local projection stabilization to approximate the two-dimensional linear elastostatics unilateral contact problem with Tresca frictional in the framework of the eXtended Finite Element Method X-FEM.

科学研究費補助金 研究種目:基盤研究(C) 課題番号:10650238 研究代表者:安田 仁彦 研究期間:1998-1999年度