Publications

2013

• Dobrushin ergodicity coefficient for Markov operators on cones, and beyond
  
  • Gaubert Stéphane
  • Qu Zheng
  , 2013. The analysis of classical consensus algorithms relies on contraction properties of adjoints of Markov operators, with respect to Hilbert's pro- jective metric or to a related family of seminorms (Hopf's oscillation or Hilbert's seminorm). We generalize these properties to abstract consensus operators over normal cones, which include the unital completely positive maps (Kraus operators) arising in quantum information theory. In par- ticular, we show that the contraction rate of such operators, with respect to the Hopf oscillation seminorm, is given by an analogue of Dobrushin's ergodicity coefficient. We derive from this result a characterization of the contraction rate of a non-linear flow, with respect to Hopf's oscillation seminorm and to Hilbert's projective metric.
• Policy iteration algorithm for zero-sum two player stochastic games: complexity bounds involving nonlinear spectral radii
  
  • Akian Marianne
  • Gaubert Stéphane
  , 2013.
• Tropical bounds for eigenvalues
  
  • Akian Marianne
  • Gaubert Stéphane
  • Marchesini Andrea
  , 2013.
• Qualitative non-destructive testing of concrete-like materials
  
  • Audibert Lorenzo
  • Haddar Houssem
  • Girard Alexandre
  , 2013. In this paper we explore the capacity of Qualita-tive Inversion Methods to detect macroscopic cracks or a lattice of small cracks in concrete-like materi-als. These materials are difficult to probe since the heterogeneities size inside the medium and the wave-length of classically used sensors are of the same order of magnitude. We shall demonstrate how this diffi-culty can be avoided in the case of macroscopic cracks by using so-called differential measurements and ap-plication of the Linear Sampling Method. For a lat-tice of small cracks we rather propose to construct a macroscopic indicator based on the eigenvalues of a suitable transmission problem. Introduction We are interested in using elastic waves to perform complete non destructive testing of concrete-like ma-terials. The main difficulty in controlling concrete is its heterogeneous nature. Concrete is made of cement paste, water and aggregates. After a drying period, this mixture results in a heterogeneous material. As far as waves propagation is concerned, the main char-acteristics is the difference of celerity between aggre-gates and cement paste, especially as the wavelength and the size of the aggregates are similar, thus, in what follows, we will model concrete as a biphasic material.This concrete-like material has the following properties: the celerity of pressure wave is 5700ms −1 in aggregates and 4300ms −1 in cement paste. Defect Figure 1: Simulated concrete and numerical set-up for direct and inverse problem
• Block-Coordinate Frank-Wolfe Optimization for Structural SVMs
  
  • Lacoste-Julien Simon
  • Jaggi Martin
  • Schmidt Mark
  • Pletscher Patrick
  , 2013, pp.53-61. We propose a randomized block-coordinate variant of the classic Frank-Wolfe algorithm for convex optimization with block-separable constraints. Despite its lower iteration cost, we show that it achieves a similar convergence rate in duality gap as the full Frank-Wolfe algorithm. We also show that, when applied to the dual structural support vector machine (SVM) objective, this yields an online algorithm that has the same low iteration complexity as primal stochastic subgradient methods. However, unlike stochastic subgradient methods, the block-coordinate Frank-Wolfe algorithm allows us to compute the optimal step-size and yields a computable duality gap guarantee. Our experiments indicate that this simple algorithm outperforms competing structural SVM solvers.
• Monochromatic reconstruction algorithms for two-dimensional multi-channel inverse problems
  
  • Novikov Roman
  • Santacesaria Matteo
  International Mathematics Research Notices, Oxford University Press (OUP), 2013, 2013 (6), pp.1205-1229. We consider two inverse problems for the multi-channel two-dimensional Schrödinger equation at fixed positive energy, i.e. the equation $-\Delta \psi + V(x)\psi = E \psi$ at fixed positive $E$, where $V$ is a matrix-valued potential. The first is the Gel'fand inverse problem on a bounded domain $D$ at fixed energy and the second is the inverse fixed-energy scattering problem on the whole plane $\R^2$. We present in this paper two algorithms which give efficient approximate solutions to these problems: in particular, in both cases we show that the potential $V$ is reconstructed with Lipschitz stability by these algorithms up to $O(E^{-(m-2)/2})$ in the uniform norm as $E \to +\infty$, under the assumptions that $V$ is $m$-times differentiable in $L^1$, for $m \geq 3$, and has sufficient boundary decay. (10.1093/imrn/rns025)
  DOI : 10.1093/imrn/rns025
• Motion Planning for Kinematic Systems
  
  • Boizot Nicolas
  • Gauthier Jean-Paul
  IEEE Transactions on Automatic Control, Institute of Electrical and Electronics Engineers, 2013, 58 (6), pp.1430 - 1442. (10.1109/TAC.2012.2232376)
  DOI : 10.1109/TAC.2012.2232376
• The level set method for the two-sided max-plus eigenproblem
  
  • Gaubert Stephane
  • Sergeev Sergei
  Discrete Event Dynamic Systems, Springer Verlag, 2013, 23 (2), pp.105-134. We consider the max-plus analogue of the eigenproblem for matrix pencils Ax=lambda Bx. We show that the spectrum of (A,B) (i.e., the set of possible values of lambda), which is a finite union of intervals, can be computed in pseudo-polynomial number of operations, by a (pseudo-polynomial) number of calls to an oracle that computes the value of a mean payoff game. The proof relies on the introduction of a spectral function, which we interpret in terms of the least Chebyshev distance between Ax and lambda Bx. The spectrum is obtained as the zero level set of this function. (10.1007/s10626-012-0137-z)
  DOI : 10.1007/s10626-012-0137-z
• Asymptotic behavior of the number of Eulerian orientations of graphs
  
  • Isaev Mikhail
  Matematicheskie Zametki / Mathematical Notes, MAIK Nauka/Interperiodica, 2013, 93 (6), pp.828-843. We consider the class of simple graphs with large algebraic connectivity (the second-smallest eigenvalue of the Laplacian matrix). For this class of graphs we determine the asymptotic behavior of the number of Eulerian orientations. In addition, we establish some new properties of the Laplacian matrix, as well as an estimate of a conditionality of matrices with the asymptotic diagonal predominance (10.4213/mzm9249)
  DOI : 10.4213/mzm9249
• La persistance multiplicative des 65536 premiers nombres entiers pour les bases 2 -en bas et à gauche- à 17 -en haut et à droite
  
  • Colonna Jean-François
  , 2013. The multiplicative persistence of the 65536 first integer numbers for the bases 2 -lower left- to 17 -upper right- (La persistance multiplicative des 65536 premiers nombres entiers pour les bases 2 -en bas et à gauche- à 17 -en haut et à droite-)
• La persistance additive des 65536 premiers nombres entiers pour les bases 2 -en bas et à gauche- à 17 -en haut et à droite
  
  • Colonna Jean-François
  , 2013. The additive persistence of the 65536 first integer numbers for the bases 2 -lower left- to 17 -upper right- (La persistance additive des 65536 premiers nombres entiers pour les bases 2 -en bas et à gauche- à 17 -en haut et à droite-)
• La persistance additive des 65536 premiers nombres entiers pour les bases 2 -en bas et à gauche- à 17 -en haut et à droite
  
  • Colonna Jean-François
  , 2013. The additive persistence of the 65536 first integer numbers for the bases 2 -lower left- to 17 -upper right- (La persistance additive des 65536 premiers nombres entiers pour les bases 2 -en bas et à gauche- à 17 -en haut et à droite-)
• Hamilton-Jacobi-Bellman Equations on Multi-Domains
  
  • Rao Zhiping
  • Zidani Hasnaa
  , 2013, 164, pp.93--116. A system of Hamilton Jacobi (HJ) equations on a partition of $\R^d$ is considered, and a uniqueness and existence result of viscosity solution is analyzed. While the notion of viscosity notion is by now well known, the question of uniqueness of solution, when the Hamiltonian is discontinuous, remains an important issue. A uniqueness result has been derived for a class of problems, where the behavior of the solution, in the region of discontinuity of the Hamiltonian, is assumed to be irrelevant and can be ignored (see reference [10]) . Here, we provide a new uniqueness result for a more general class of Hamilton-Jacobi equations. (10.1007/978-3-0348-0631-2_6)
  DOI : 10.1007/978-3-0348-0631-2_6
• La persistance multiplicative des 65536 premiers nombres entiers pour les bases 2 -en bas et à gauche- à 17 -en haut et à droite
  
  • Colonna Jean-François
  , 2013. The multiplicative persistence of the 65536 first integer numbers for the bases 2 -lower left- to 17 -upper right- (La persistance multiplicative des 65536 premiers nombres entiers pour les bases 2 -en bas et à gauche- à 17 -en haut et à droite-)
• Schémas numériques pour la simulation des écoulements diphasiques compressibles transsoniques de type Baer-Nunziato
  
  • Asmaa Tassadit
  • Coquel Frédéric
  • Tran Quang Huy
  , 2013.
• Equations diférentielles stochastiques en pharmacocinétique de population : modèles et méthodologie
  
  • Delattre Maud
  • Lavielle Marc
  , 2013.
• De la convexité tropicale aux jeux à somme nulle
  
  • Gaubert Stephane
  , 2013.
• Taux de contraction de flots croissants sur un cône et application au contrôle stochastique
  
  • Gaubert Stéphane
  • Qu Zheng
  , 2013.
• Tropicalizing the Simplex Algorithm
  
  • Allamigeon Xavier
  • Benchimol Pascal
  • Gaubert Stéphane
  • Joswig Michael
  , 2013.
• Eulerian modeling of polydisperse evaporating spray under realistic internal combustion engine conditions
  
  • Emre Oguz
  • Massot Marc
  • de Chaisemartin Stéphane
  • Jay Stéphane
  • Laurent Frédérique
  , 2013.
• Graph-Theoretic Algorithms for the “Isomorphism of Polynomials” Problem
  
  • Bouillaguet Charles
  • Fouque Pierre-Alain
  • Véber Amandine
  , 2013, LNCS 7881, pp.17. We give three new algorithms to solve the "isomorphism of polynomial" problem, which was underlying the hardness of recovering the secret-key in some multivariate trapdoor one-way functions. In this problem, the adversary is given two quadratic functions, with the promise that they are equal up to linear changes of coordinates. Her objective is to compute these changes of coordinates, a task which is known to be harder than Graph-Isomorphism. Our new algorithm build on previous work in a novel way. Exploiting the birthday paradox, we break instances of the problem in time q 2n/3 (rigorously) and q n/2 (heuristically), where q n is the time needed to invert the quadratic trapdoor function by exhaustive search. These results are obtained by turning the algebraic problem into a combinatorial one, namely that of recovering partial information on an isomorphism between two exponentially large graphs. These graphs, derived from the quadratic functions, are new tools in multivariate crypt-analysis. (10.1007/978-3-642-38348-9_13)
  DOI : 10.1007/978-3-642-38348-9_13
• Weak law of large numbers for some Markov chains along non homogeneous genealogies
  
  • Bansaye Vincent
  • Huang Chunmao
  , 2013. We consider a population with non-overlapping generations, whose size goes to infinity. It is described by a discrete genealogy which may be time non-homogeneous and we pay special attention to branching trees in varying environments. A Markov chain models the dynamic of the trait of each individual along this genealogy and may also be time non-homogeneous. Such models are motivated by transmission processes in the cell division, reproduction-dispersion dynamics or sampling problems in evolution. We want to determine the evolution of the distribution of the traits among the population, namely the asymptotic behavior of the proportion of individuals with a given trait. We prove some quenched laws of large numbers which rely on the ergodicity of an auxiliary process, in the same vein as \cite{guy,delmar}. Applications to time inhomogeneous Markov chains lead us to derive a backward (with respect to the environment) law of large numbers and a law of large numbers on the whole population until generation $n$. A central limit is also established in the transient case.
• Monument Valley ensoleillée
  
  • Colonna Jean-François
  , 2013. Sunny Monument Valley (Monument Valley ensoleillée)
• Casting constraints in structural optimization via a level-set method
  
  • Allaire Grégoire
  • Jouve François
  • Michailidis Georgios
  , 2013. A novel strategy for handling the molding constraint for cast parts is presented. In a first step, a simple projection method for the velocity field is applied. If the optimized shape violates thickness constraints, this projection method is no longer sufficient and a general molding constraint is applied at the same time with thickness control. We apply an augmented Lagrangian method to impose the constraints and compute a shape derivative for the objective function. We show examples in 3-d.
• Submodular spectral functions of principal submatrices of a hermitian matrix, extensions and applications
  
  • Friedland S.
  • Gaubert S.
  Linear Algebra and its Applications, Elsevier, 2013, 438 (10), pp.3872-3884. We extend the multiplicative submodularity of the principal determinants of a nonnegative definite hermitian matrix to other spectral functions. We show that if $f$ is the primitive of a function that is operator monotone on an interval containing the spectrum of a hermitian matrix $A$, then the function $I\mapsto {\rm tr} f(A[I])$ is supermodular, meaning that ${\rm tr} f(A[I])+{\rm tr} f(A[J])\leq {\rm tr} f(A[I\cup J])+{\rm tr} f(A[I\cap J])$, where $A[I]$ denotes the $I\times I$ principal submatrix of $A$. We discuss extensions to self-adjoint operators on infinite dimensional Hilbert space and to $M$-matrices. We discuss an application to CUR approximation of nonnegative hermitian matrices. (10.1016/j.laa.2011.11.021)
  DOI : 10.1016/j.laa.2011.11.021