Source author record

Bernard Mourrain

Bernard Mourrain appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.AG Symbolic Computation math.AC math.NA Graphics Machine Learning math.FA math.OC

Catalog footprint

What is connected

28works

8topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Tensor decomposition for learning Gaussian mixtures from moments

In data processing and machine learning, an important challenge is to recover and exploit models that can represent accurately the data. We consider the problem of recovering Gaussian mixture models from datasets. We investigate symmetric tensor decomposition methods for tackling this problem, where the tensor is built from empirical moments of the data distribution. We consider identifiable tensors, which have a unique decomposition, showing that moment tensors built from spherical Gaussian mixtures have this property. We prove that symmetric tensors with interpolation degree strictly less than half their order are identifiable and we present an algorithm, based on simple linear algebra operations, to compute their decomposition. Illustrative experimentations show the impact of the tensor decomposition method for recovering Gaussian mixtures, in comparison with other state-of-the-art approaches.

preprint2022arXiv

Univariate Rational Sums of Squares

Given rational univariate polynomials f and g such that gcd(f, g) and f / gcd(f, g) are relatively prime, we show that g is non-negative on all the real roots of f if and only if g is a sum of squares of rational polynomials modulo f. We complete our study by exhibiting an algorithm that produces a certificate that a polynomial g is non-negative on the real roots of a non-zero polynomial f , when the above assumption is satisfied.

preprint2020arXiv

Punctual Hilbert Schemes and Certified Approximate Singularities

In this paper we provide a new method to certify that a nearby polynomial system has a singular isolated root with a prescribed multiplicity structure. More precisely, given a polynomial system f $=(f\_1, \ldots, f\_N)\in C[x\_1, \ldots, x\_n]^N$, we present a Newton iteration on an extended deflated system that locally converges, under regularity conditions, to a small deformation of $f$ such that this deformed system has an exact singular root. The iteration simultaneously converges to the coordinates of the singular root and the coefficients of the so called inverse system that describes the multiplicity structure at the root. We use $$α$$-theory test to certify the quadratic convergence, and togive bounds on the size of the deformation and on the approximation error. The approach relies on an analysis of the punctual Hilbert scheme, for which we provide a new description. We show in particular that some of its strata can be rationally parametrized and exploit these parametrizations in the certification. We show in numerical experimentation how the approximate inverse system can be computed as a starting point of the Newton iterations and the fast numerical convergence to the singular root with its multiplicity structure, certified by our criteria.

preprint2016arXiv

Geometrically continuous splines for surfaces of arbitrary topology

We analyze the space of geometrically continuous piecewise polynomial functions or splines for quadrangular and triangular patches with arbitrary topology and general rational transition maps. To define these spaces of G 1 spline functions, we introduce the concept of topological surface with gluing data attached to the edges shared by faces. The framework does not require manifold constructions and is general enough to allow non-orientable surfaces. We describe compatibility conditions on the transition maps so that the space of differentiable functions is ample and show that these conditions are necessary and sufficient to construct ample spline spaces. We determine the dimension of the space of G 1 spline functions which are of degree k on triangular pieces and of bi-degree (k, k) on quadrangular pieces, for k big enough. A separability property on the edges is involved to obtain the dimension formula. An explicit construction of basis functions attached respectively to vertices, edges and faces is proposed and examples of bases of G 1 splines of small degree for topological surfaces with boundary and without boundary are detailed.

preprint2016arXiv

On deflation and multiplicity structure

This paper presents two new constructions related to singular solutions of polynomial systems. The first is a new deflation method for an isolated singular root. This construction uses a single linear differential form defined from the Jacobian matrix of the input, and defines the deflated system by applying this differential form to the original system. The advantages of this new deflation is that it does not introduce new variables and the increase in the number of equations is linear in each iteration instead of the quadratic increase of previous methods. The second construction gives the coefficients of the so-called inverse system or dual basis, which defines the multiplicity structure at the singular root. We present a system of equations in the original variables plus a relatively small number of new variables that completely deflates the root in one step. We show that the isolated simple solutions of this new system correspond to roots of the original system with given multiplicity structure up to a given order. Both constructions are "exact" in that they permit one to treat all conjugate roots simultaneously and can be used in certification procedures for singular roots and their multiplicity structure with respect to an exact rational polynomial system.

preprint2016arXiv

Tensor decomposition and homotopy continuation

A computationally challenging classical elimination theory problem is to compute polynomials which vanish on the set of tensors of a given rank. By moving away from computing polynomials via elimination theory to computing pseudowitness sets via numerical elimination theory, we develop computational methods for computing ranks and border ranks of tensors along with decompositions. More generally, we present our approach using joins of any collection of irreducible and nondegenerate projective varieties $X_1,\ldots,X_k\subset\mathbb{P}^N$ defined over $\mathbb{C}$. After computing ranks over $\mathbb{C}$, we also explore computing real ranks. Various examples are included to demonstrate this numerical algebraic geometric approach.

preprint2015arXiv

Border Basis relaxation for polynomial optimization

A relaxation method based on border basis reduction which improves the efficiency of Lasserre's approach is proposed to compute the optimum of a polynomial function on a basic closed semi algebraic set. A new stopping criterion is given to detect when the relaxation sequence reaches the minimum, using a sparse flat extension criterion. We also provide a new algorithm to reconstruct a finite sum of weighted Dirac measures from a truncated sequence of moments, which can be applied to other sparse reconstruction problems. As an application, we obtain a new algorithm to compute zero-dimensional minimizer ideals and the minimizer points or zero-dimensional G-radical ideals. Experimentations show the impact of this new method on significant benchmarks.

preprint2015arXiv

Certifying isolated singular points and their multiplicity structure

This paper presents two new constructions related to singular solutions of polynomial systems. The first is a new deflation method for an isolated singular root. This construc-tion uses a single linear differential form defined from the Jacobian matrix of the input, and defines the deflated system by applying this differential form to the original system. The advantages of this new deflation is that it does not introduce new variables and the increase in the number of equations is linear instead of the quadratic increase of previous methods. The second construction gives the coefficients of the so-called inverse system or dual basis, which defines the multiplicity structure at the singular root. We present a system of equations in the original variables plus a relatively small number of new vari-ables. We show that the roots of this new system include the original singular root but now with multiplicity one, and the new variables uniquely determine the multiplicity structure. Both constructions are "exact", meaning that they permit one to treat all conjugate roots simultaneously and can be used in certification procedures for singular roots and their multiplicity structure with respect to an exact rational polynomial system.

preprint2015arXiv

On the construction of general cubature formula by flat extensions

We describe a new method to compute general cubature formulae. The problem is initially transformed into the computation of truncated Hankel operators with flat extensions. We then analyse the algebraic properties associated to flat extensions and show how to recover the cubature points and weights from the truncated Hankel operator. We next present an algorithm to test the flat extension property and to additionally compute the decomposition. To generate cubature formulae with a minimal number of points, we propose a new relaxation hierarchy of convex optimization problems minimizing the nuclear norm of the Hankel operators. For a suitably high order of convex relaxation, the minimizer of the optimization problem corresponds to a cubature formula. Furthermore cubature formulae with a minimal number of points are associated to faces of the convex sets. We illustrate our method on some examples, and for each we obtain a new minimal cubature formula.

preprint2015arXiv

On the dimension of spline spaces on planar T-meshes

We analyze the space of bivariate functions that are piecewise polynomial of bi-degree \textless{}= (m, m') and of smoothness r along the interior edges of a planar T-mesh. We give new combinatorial lower and upper bounds for the dimension of this space by exploiting homological techniques. We relate this dimension to the weight of the maximal interior segments of the T-mesh, defined for an ordering of these maximal interior segments. We show that the lower and upper bounds coincide, for high enough degrees or for hierarchical T-meshes which are enough regular. We give a rule of subdivision to construct hierarchical T-meshes for which these lower and upper bounds coincide. Finally, we illustrate these results by analyzing spline spaces of small degrees and smoothness.

preprint2014arXiv

Bounds on the dimension of trivariate spline spaces: A homological approach

We consider the vector space of globally differentiable piecewise polynomial functions defined on a three-dimensional polyhedral domain partitioned into tetrahedra. We prove new lower and upper bounds on the dimension of this space by applying homological techniques. We give an insight into different ways of approaching this problem by exploring its connections with the Hilbert series of ideals generated by powers of linear forms, fat points, the so-called Fröberg-Iarrobino conjecture, and the weak Lefschetz property.

preprint2014arXiv

Exact relaxation for polynomial optimization on semi-algebraic sets

In this paper, we study the problem of computing by relaxation hierarchies the infimum of a real polynomial function f on a closed basic semialgebraic set and the points where this infimum is reached, if they exist. We show that when the infimum is reached, a relaxation hierarchy constructed from the Karush-Kuhn-Tucker ideal is always exact and that the vanishing ideal of the KKT minimizer points is generated by the kernel of the associated moment matrix in that degree, even if this ideal is not zero-dimensional. We also show that this relaxation allows to detect when there is no KKT minimizer. We prove that the exactness of the relaxation depends only on the real points which satisfy these constraints.This exploits representations of positive polynomials as elementsof the preordering modulo the KKT ideal, which only involves polynomials in the initial set of variables. Applications to global optimization, optimization on semialgebraic sets defined by regular sets of constraints, optimization on finite semialgebraic sets, real radical computation are given.

preprint2014arXiv

Extensors and the Hilbert scheme

The Hilbert scheme $\mathbf{Hilb}_{p(t)}^{n}$ parametrizes closed subschemes and families of closed subschemes in the projective space $\mathbb{P}^n$ with a fixed Hilbert polynomial $p(t)$. It is classically realized as a closed subscheme of a Grassmannian or a product of Grassmannians. In this paper we consider schemes over a field $k$ of characteristic zero and we present a new proof of the existence of the Hilbert scheme as a subscheme of the Grassmannian $\mathbf{Gr}_{p(r)}^{N(r)}$, where $N(r)= h^0 (\mathcal{O}_{\mathbb{P}^n}(r))$. Moreover, we exhibit explicit equations defining it in the Plücker coordinates of the Plücker embedding of $\mathbf{Gr}_{p(r)}^{N(r)}$. Our proof of existence does not need some of the classical tools used in previous proofs, as flattening stratifications and Gotzmann's Persistence Theorem. The degree of our equations is $\text{deg} p(t)+2$, lower than the degree of the equations given by Iarrobino and Kleiman in 1999 and also lower (except for the case of hypersurfaces) than the degree of those proved by Haiman and Sturmfels in 2004 after Bayer's conjecture in 1982. The novelty of our approach mainly relies on the deeper attention to the intrinsic symmetries of the Hilbert scheme and on some results about Grassmannian based on the notion of extensors.

preprint2014arXiv

Flat extensions in *-algebras

The main result of the paper is a flat extension theorem for positive linear functionals on *-algebras. The theorem is applied to truncated moment problems on cylinder sets, on matrices of polynomials and on enveloping algebras of Lie algebras.

preprint2014arXiv

Toric Border Bases

We extend the theory and the algorithms of Border Bases to systems of Laurent polynomial equations, defining "toric" roots. Instead of introducing new variables and new relations to saturate by the variable inverses, we propose a more efficient approach which works directly with the variables and their inverse. We show that the commutation relations and the inversion relations characterize toric border bases. We explicitly describe the first syzygy module associated to a toric border basis in terms of these relations. Finally, a new border basis algorithm for Laurent polynomials is described and a proof of its termination is given for zero-dimensional toric ideals.

preprint2013arXiv

Continuous Collision Detection for Composite Quadric Models

A composite quadric model (CQM) is an object modeled by piecewise linear or quadric patches. We study the continuous detection problem of a special type of CQM objects which are commonly used in CAD/CAM, that is, the boundary surfaces of such a CQM intersect only in straight line segments or conic curve segments. We present a framework for continuous collision detection (CCD) of this special type of CQM (which we also call CQM for brevity) in motion. We derive algebraic formulations and compute numerically the first contact time instants and the contact points of two moving CQMs in $\mathbb R^3$. Since it is difficult to process CCD of two CQMs in a direct manner because they are composed of semi-algebraic varieties, we break down the problem into subproblems of solving CCD of pairs of boundary elements of the CQMs. We present procedures to solve CCD of different types of boundary element pairs in different dimensions. Some CCD problems are reduced to their equivalents in a lower dimensional setting, where they can be solved more efficiently.

preprint2013arXiv

Superfast solution of Toeplitz systems based on syzygy reduction

We present a new superfast algorithm for solving Toeplitz systems. This algorithm is based on a relation between the solution of such problems and syzygies of polynomials or moving lines. We show an explicit connection between the generators of a Toeplitz matrix and the generators of the corresponding module of syzygies. We show that this module is generated by two elements and the solution of a Toeplitz system T u=g can be reinterpreted as the remainder of a vector depending on g, by these two generators. We obtain these generators and this remainder with computational complexity O(n log^2 n) for a Toeplitz matrix of size nxn.

preprint2013arXiv

Unconstraint global polynomial optimization via Gradient Ideal

In this paper, we describe a new method to compute the minimum of a real polynomial function and the ideal defining the points which minimize this polynomial function, assuming that the minimizer ideal is zero-dimensional. Our method is a generalization of Lasserre relaxation method and stops in a finite number of steps. The proposed algorithm combines Border Basis, Moment Matrices and Semidefinite Programming. In the case where the minimum is reached at a finite number of points, it provides a border basis of the minimizer ideal.

preprint2012arXiv

A comparison of different notions of ranks of symmetric tensors

We introduce various notions of rank for a symmetric tensor, namely: rank, border rank, catalecticant rank, generalized rank, scheme length, border scheme length, extension rank and smoothable rank. We analyze the stratification induced by these ranks. The mutual relations between these stratifications, allow us to describe the hierarchy among all the ranks. We show that strict inequalities are possible between rank, border rank, extension rank and catalecticant rank. Moreover we show that scheme length, generalized rank and extension rank coincide.

preprint2012arXiv

Homological techniques for the analysis of the dimension of triangular spline spaces

The spline space $C_k^r(Δ)$ attached to a subdivided domain $Δ$ of $\R^{d} $ is the vector space of functions of class $C^{r}$ which are polynomials of degree $\le k$ on each piece of this subdivision. Classical splines on planar rectangular grids play an important role in Computer Aided Geometric Design, and spline spaces over arbitrary subdivisions of planar domains are now considered for isogeometric analysis applications. We address the problem of determining the dimension of the space of bivariate splines $C_k^r(Δ)$ for a triangulated region $Δ$ in the plane. Using the homological introduced by Billera (1988), we number the vertices and establish a formula for an upper bound on the dimension. There is no restriction on the ordering and we obtain more accurate approximations to the dimension than previous methods and furthermore, in certain cases even an exact value can be found. The construction makes also possible to get a short proof for the dimension formula when $k\ge 4r+1$, and the same method we use in this proof yields the dimension straightaway for many other cases.

preprint2011arXiv

Deflation and Certified Isolation of Singular Zeros of Polynomial Systems

We develop a new symbolic-numeric algorithm for the certification of singular isolated points, using their associated local ring structure and certified numerical computations. An improvement of an existing method to compute inverse systems is presented, which avoids redundant computation and reduces the size of the intermediate linear systems to solve. We derive a one-step deflation technique, from the description of the multiplicity structure in terms of differentials. The deflated system can be used in Newton-based iterative schemes with quadratic convergence. Starting from a polynomial system and a small-enough neighborhood, we obtain a criterion for the existence and uniqueness of a singular root of a given multiplicity structure, applying a well-chosen symbolic perturbation. Standard verification methods, based eg. on interval arithmetic and a fixed point theorem, are employed to certify that there exists a unique perturbed system with a singular root in the domain. Applications to topological degree computation and to the analysis of real branches of an implicit curve illustrate the method.

preprint2011arXiv

General Tensor Decomposition, Moment Matrices and Applications

The tensor decomposition addressed in this paper may be seen as a generalisation of Singular Value Decomposition of matrices. We consider general multilinear and multihomogeneous tensors. We show how to reduce the problem to a truncated moment matrix problem and give a new criterion for flat extension of Quasi-Hankel matrices. We connect this criterion to the commutation characterisation of border bases. A new algorithm is described. It applies for general multihomogeneous tensors, extending the approach of J.J. Sylvester to binary forms. An example illustrates the algebraic operations involved in this approach and how the decomposition can be recovered from eigenvector computation.

preprint2011arXiv

Moment Matrices, Border Bases and Real Radical Computation

In this paper, we describe new methods to compute the radical (resp. real radical) of an ideal, assuming it complex (resp. real) variety is finite. The aim is to combine approaches for solving a system of polynomial equations with dual methods which involve moment matrices and semi-definite programming. While the border basis algorithms of [17] are efficient and numerically stable for computing complex roots, algorithms based on moment matrices [12] allow the incorporation of additional polynomials, e.g., to re- strict the computation to real roots or to eliminate multiple solutions. The proposed algorithm can be used to compute a border basis of the input ideal and, as opposed to other approaches, it can also compute the quotient structure of the (real) radical ideal directly, i.e., without prior algebraic techniques such as Gröbner bases. It thus combines the strength of existing algorithms and provides a unified treatment for the computation of border bases for the ideal, the radical ideal and the real radical ideal.

preprint2010arXiv

Continued Fraction Expansion of Real Roots of Polynomial Systems

We present a new algorithm for isolating the real roots of a system of multivariate polynomials, given in the monomial basis. It is inspired by existing subdivision methods in the Bernstein basis; it can be seen as generalization of the univariate continued fraction algorithm or alternatively as a fully analog of Bernstein subdivision in the monomial basis. The representation of the subdivided domains is done through homographies, which allows us to use only integer arithmetic and to treat efficiently unbounded regions. We use univariate bounding functions, projection and preconditionning techniques to reduce the domain of search. The resulting boxes have optimized rational coordinates, corresponding to the first terms of the continued fraction expansion of the real roots. An extension of Vincent's theorem to multivariate polynomials is proved and used for the termination of the algorithm. New complexity bounds are provided for a simplified version of the algorithm. Examples computed with a preliminary C++ implementation illustrate the approach.

preprint2010arXiv

The DMM bound: multivariate (aggregate) separation bounds

In this paper we derive aggregate separation bounds, named after Davenport-Mahler-Mignotte (\dmm), on the isolated roots of polynomial systems, specifically on the minimum distance between any two such roots. The bounds exploit the structure of the system and the height of the sparse (or toric) resultant by means of mixed volume, as well as recent advances on aggregate root bounds for univariate polynomials, and are applicable to arbitrary positive dimensional systems. We improve upon Canny's gap theorem \cite{c-crmp-87} by a factor of $\OO(d^{n-1})$, where $d$ bounds the degree of the polynomials, and $n$ is the number of variables. One application is to the bitsize of the eigenvalues and eigenvectors of an integer matrix, which also yields a new proof that the problem is polynomial. We also compare against recent lower bounds on the absolute value of the root coordinates by Brownawell and Yap \cite{by-issac-2009}, obtained under the hypothesis there is a 0-dimensional projection. Our bounds are in general comparable, but exploit sparseness; they are also tighter when bounding the value of a positive polynomial over the simplex. For this problem, we also improve upon the bounds in \cite{bsr-arxix-2009,jp-arxiv-2009}. Our analysis provides a precise asymptotic upper bound on the number of steps that subdivision-based algorithms perform in order to isolate all real roots of a polynomial system. This leads to the first complexity bound of Milne's algorithm \cite{Miln92} in 2D.

preprint2010arXiv

The Hilbert scheme of points and its link with border basis

In this paper, we give new explicit representations of the Hilbert scheme of $μ$ points in $\PP^{r}$ as a projective subvariety of a Grassmanniann variety. This new explicit description of the Hilbert scheme is simpler than the previous ones and global. It involves equations of degree $2$. We show how these equations are deduced from the commutation relations characterizing border bases. Next, we consider infinitesimal perturbations of an input system of equations on this Hilbert scheme and describe its tangent space. We propose an effective criterion to test if it is a flat deformation, that is if the perturbed system remains on the Hilbert scheme of the initial equations. This criterion involves in particular formal reduction with respect to border bases.

preprint2009arXiv

On the Computation of Matrices of Traces and Radicals of Ideals

Let $f_1,...,f_s \in \mathbb{K}[x_1,...,x_m]$ be a system of polynomials generating a zero-dimensional ideal $\I$, where $\mathbb{K}$ is an arbitrary algebraically closed field. We study the computation of "matrices of traces" for the factor algebra $\A := \CC[x_1, ..., x_m]/ \I$, i.e. matrices with entries which are trace functions of the roots of $\I$. Such matrices of traces in turn allow us to compute a system of multiplication matrices $\{M_{x_i}|i=1,...,m\}$ of the radical $\sqrt{\I}$. We first propose a method using Macaulay type resultant matrices of $f_1,...,f_s$ and a polynomial $J$ to compute moment matrices, and in particular matrices of traces for $\A$. Here $J$ is a polynomial generalizing the Jacobian. We prove bounds on the degrees needed for the Macaulay matrix in the case when $\I$ has finitely many projective roots in $\mathbb{P}^m_\CC$. We also extend previous results which work only for the case where $\A$ is Gorenstein to the non-Gorenstein case. The second proposed method uses Bezoutian matrices to compute matrices of traces of $\A$. Here we need the assumption that $s=m$ and $f_1,...,f_m$ define an affine complete intersection. This second method also works if we have higher dimensional components at infinity. A new explicit description of the generators of $\sqrt{\I}$ are given in terms of Bezoutians.

preprint2009arXiv

Symmetric tensor decomposition

We present an algorithm for decomposing a symmetric tensor, of dimension n and order d as a sum of rank-1 symmetric tensors, extending the algorithm of Sylvester devised in 1886 for binary forms. We recall the correspondence between the decomposition of a homogeneous polynomial in n variables of total degree d as a sum of powers of linear forms (Waring's problem), incidence properties on secant varieties of the Veronese Variety and the representation of linear forms as a linear combination of evaluations at distinct points. Then we reformulate Sylvester's approach from the dual point of view. Exploiting this duality, we propose necessary and sufficient conditions for the existence of such a decomposition of a given rank, using the properties of Hankel (and quasi-Hankel) matrices, derived from multivariate polynomials and normal form computations. This leads to the resolution of polynomial equations of small degree in non-generic cases. We propose a new algorithm for symmetric tensor decomposition, based on this characterization and on linear algebra computations with these Hankel matrices. The impact of this contribution is two-fold. First it permits an efficient computation of the decomposition of any tensor of sub-generic rank, as opposed to widely used iterative algorithms with unproved global convergence (e.g. Alternate Least Squares or gradient descents). Second, it gives tools for understanding uniqueness conditions, and for detecting the rank.

Bernard Mourrain

What is connected

Connect this record

See the researcher in context

Building this map preview

28 published item(s)

Tensor decomposition for learning Gaussian mixtures from moments

Univariate Rational Sums of Squares

Punctual Hilbert Schemes and Certified Approximate Singularities

Geometrically continuous splines for surfaces of arbitrary topology

On deflation and multiplicity structure

Tensor decomposition and homotopy continuation

Border Basis relaxation for polynomial optimization

Certifying isolated singular points and their multiplicity structure

On the construction of general cubature formula by flat extensions

On the dimension of spline spaces on planar T-meshes

Bounds on the dimension of trivariate spline spaces: A homological approach

Exact relaxation for polynomial optimization on semi-algebraic sets

Extensors and the Hilbert scheme

Flat extensions in *-algebras

Toric Border Bases

Continuous Collision Detection for Composite Quadric Models

Superfast solution of Toeplitz systems based on syzygy reduction

Unconstraint global polynomial optimization via Gradient Ideal

A comparison of different notions of ranks of symmetric tensors

Homological techniques for the analysis of the dimension of triangular spline spaces

Deflation and Certified Isolation of Singular Zeros of Polynomial Systems

General Tensor Decomposition, Moment Matrices and Applications

Moment Matrices, Border Bases and Real Radical Computation

Continued Fraction Expansion of Real Roots of Polynomial Systems

The DMM bound: multivariate (aggregate) separation bounds

The Hilbert scheme of points and its link with border basis

On the Computation of Matrices of Traces and Radicals of Ideals

Symmetric tensor decomposition