PBPaul Breiding

Paul Breiding

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Paul Breiding has a total of 4 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Random spectrahedra

    by Paul Breiding, Khazhgali Kozhasov, Antonio Lerario

    Spectrahedra are affine-linear sections of the cone $\mathcal{P}_n$ of positive semidefinite symmetric $n\times n$-matrices. We consider random spectrahedra that are obtained by intersecting~$\mathcal{P}_n$ with the affine-linear space $\mathbf{1} + V$, where $\mathbf{1}$ is the identity matrix and $V$ is an $\ell$-dimensional linear space that is chosen from the unique orthogonally invariant probability measure on the Grassmanian of $\ell$-planes in the space of $n\times n$ real symmetric matrices (endowed with the Frobenius inner product). Motivated by applications, for $\ell=3$ we relate the average number $\mathbb{E} \sigma_n$ of singular points on the boundary of a three-dimensional spectrahedron to the volume of the set of symmetric matrices whose two smallest eigenvalues coincide. In the case of quartic spectrahedra ($n=4$) we show that $\mathbb{E} \sigma_4 = 6-\frac{4}{\sqrt{3}}$. Moreover, we prove that the average number $\mathbb{E} \rho_n$ of singular points on the real variety of singular matrices in $\mathbf{1} + V$ is $n(n-1)$. This quantity is related to the volume of the variety of real symmetric matrices with repeated eigenvalues. Furthermore, we compute the asymptotics of the volume and the volume of the boundary of a random spectrahedron.

  • On the average condition number of tensor rank decompositions

    by Paul Breiding, Nick Vannieuwenhoven

    We compute the expected value of powers of the geometric condition number of random tensor rank decompositions. It is shown in particular that the expected value of the condition number of $n_1\times n_2 \times 2$ tensors with a random rank-$r$ decomposition, given by factor matrices with independent and identically distributed standard normal entries, is infinite. This entails that it is expected and probable that such a rank-$r$ decomposition is sensitive to perturbations of the tensor. Moreover, it provides concrete further evidence that tensor decomposition can be a challenging problem, also from the numerical point of view. On the other hand, we provide strong theoretical and empirical evidence that tensors of size $n_1~\times ~n_2~\times ~n_3$ with all $n_1,n_2,n_3 \geqslant 3$ have a finite average condition number. This suggests that there exists a gap in the expected sensitivity of tensors between those of format $n_1\times n_2 \times 2$ and other order-3 tensors. To establish these results we show that a natural weighted distance from a tensor rank decomposition to the locus of ill-posed decompositions with an infinite geometric condition number is bounded from below by the inverse of this condition number. That is, we prove one inequality towards a so-called condition number theorem for the tensor rank decomposition.


  • Open Access

    How Many Eigenvalues of a Random Symmetric Tensor are Real?

    by Paul Breiding

    This article answers a question posed by Draisma and Horobet, who asked for a closed formula for the expected number of real eigenvalues of a random real symmetric tensor drawn from the Gaussian distribution relative to the Bombieri norm. This expected value is equal to the expected number of real critical points on the unit sphere of a Kostlan polynomial. We also derive an exact formula for the expected absolute value of the determinant of a matrix from the Gaussian Orthogonal Ensemble.

  • Open Access

    On the Geometry of the Set of Symmetric Matrices with Repeated Eigenvalues

    by Paul Breiding, Khazhgali Kozhasov, Antonio Lerario

    We investigate some geometric properties of the real algebraic variety $$\Delta $$ Δ of symmetric matrices with repeated eigenvalues. We explicitly compute the volume of its intersection with the sphere and prove a Eckart–Young–Mirsky-type theorem for the distance function from a generic matrix to points in $$\Delta $$ Δ . We exhibit connections of our study to real algebraic geometry (computing the Euclidean distance degree of $$\Delta $$ Δ ) and random matrix theory.


  • Open Access

    HomotopyContinuation.jl: A package for homotopy continuation in Julia

    by Paul Breiding, Sascha Timme

    We present the Julia package HomotopyContinuation.jl, which provides an algorithmic framework for solving polynomial systems by numerical homotopy continuation. We introduce the basic capabilities of the package and demonstrate the software on an illustrative example. We motivate our choice of Julia and how its features allow us to improve upon existing software packages with respect to usability, modularity and performance. Furthermore, we compare the performance of HomotopyContinuation.jl to the existing packages Bertini and PHCpack.


  • Open Access

    The condition number of join decompositions

    by Paul Breiding, Nick Vannieuwenhoven

    The join set of a finite collection of smooth embedded submanifolds of a mutual vector space is defined as their Minkowski sum. Join decompositions generalize some ubiquitous decompositions in multilinear algebra, namely tensor rank, Waring, partially symmetric rank and block term decompositions. This paper examines the numerical sensitivity of join decompositions to perturbations; specifically, we consider the condition number for general join decompositions. It is characterized as a distance to a set of ill-posed points in a supplementary product of Grassmannians. We prove that this condition number can be computed efficiently as the smallest singular value of an auxiliary matrix. For some special join sets, we characterized the behavior of sequences in the join set converging to the latter's boundary points. Finally, we specialize our discussion to the tensor rank and Waring decompositions and provide several numerical experiments confirming the key results.

  • Open Access

    An efficient randomized homotopy method to approximate eigenpairs of tensors

    by Paul Breiding

    Let $A \in (\mathbb{C}^{n})^{\otimes p}$ be a complex tensor of order $p$. The pair $(v,\eta)\in\mathbb{C}^n\times \mathbb{C}$ is called an h-eigenpair of $A$, if $v\neq0$ and it satisfies $Av^{p-1}=\eta^{p-2} v$, where $Av^{p-1}$ is the contraction of $A$ by $v$ in all but the first modes. We describe a randomized algorithm to compute approximations of h-eigenpairs of complex tensors. Assuming random input, the average number of arithmetic operations it performs is polynomially bounded in the input size.

  • Open Access

    Convergence analysis of Riemannian Gauss-Newton methods and its connection with the geometric condition number

    by Paul Breiding, Nick Vannieuwenhoven

    We obtain estimates of the multiplicative constants appearing in local convergence results of the Riemannian Gauss-Newton method for least squares problems on manifolds and relate them to the geometric condition number of [P. B\"urgisser and F. Cucker, Condition: The Geometry of Numerical Algorithms, 2013].