Paul Breiding
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
Research Subjects
Paul Breiding has a total of 4 co-authors. Here are the top co-authors by number of shared publications:
- Nick Vannieuwenhoven
Department of Computer Science, KU Leuven, Leuven, Belgium
4 shared publications - Antonio Lerario
SISSA, Trieste, Italy
2 shared publications - Khazhgali Kozhasov
SISSA
2 shared publications - Sascha Timme
Technische Universität Berlin, Berlin, Germany
2 shared publications
Latest Publications
- Open Access
Random spectrahedra
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.Open AccessRandom spectrahedra
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. - 20 June 2019
- Published by Oxford University Press (OUP) in IMA Journal of Numerical Analysis
- Vol. 40 (3) , 1908-1936
On the average condition number of tensor rank decompositions
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.- 20 June 2019
- Published by Oxford University Press (OUP) in IMA Journal of Numerical Analysis
- Vol. 40 (3) , 1908-1936
On the average condition number of tensor rank decompositions
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?
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 AccessHow Many Eigenvalues of a Random Symmetric Tensor are Real?
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
- 19 December 2018
- Published by Association for Mathematical Research in Arnold Mathematical Journal
- Vol. 4 (3-4) , 423-443
On the Geometry of the Set of Symmetric Matrices with Repeated Eigenvalues
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.- 19 December 2018
- Published by Association for Mathematical Research in Arnold Mathematical Journal
- Vol. 4 (3-4) , 423-443
Open AccessOn the Geometry of the Set of Symmetric Matrices with Repeated Eigenvalues
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. - 14 July 2018
- Published by Springer Nature
- p. 458-465
HomotopyContinuation.jl: A Package for Homotopy Continuation in Julia
- 14 July 2018
- Published by Springer Nature
- p. 458-465
HomotopyContinuation.jl: A Package for Homotopy Continuation in Julia
- Open Access
HomotopyContinuation.jl: A package for homotopy continuation in Julia
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 AccessHomotopyContinuation.jl: A package for homotopy continuation in Julia
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
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 AccessThe condition number of join decompositions
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.
- 1 April 2018
- Published by Elsevier in Applied Mathematics Letters
- Vol. 78, 42-50
Convergence analysis of Riemannian Gauss–Newton methods and its connection with the geometric condition number
- 1 April 2018
- Published by Elsevier in Applied Mathematics Letters
- Vol. 78, 42-50
Convergence analysis of Riemannian Gauss–Newton methods and its connection with the geometric condition number
- Open Access
An efficient randomized homotopy method to approximate eigenpairs of tensors
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 AccessAn efficient randomized homotopy method to approximate eigenpairs of tensors
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
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].
Open AccessConvergence analysis of Riemannian Gauss-Newton methods and its connection with the geometric condition number
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].