BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Peter Bürgisser

Peter Bürgisser appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCComputational Complexitymath.NAmath.AGquant-phData Structures and Algorithmsmath-phmath.MPmath.RTmath.COmath.GRmath.PR

Catalog footprint

What is connected

18works
12topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

18 published item(s)

preprint2020arXiv

Interior-point methods for unconstrained geometric programming and scaling problems

We provide a condition-based analysis of two interior-point methods for unconstrained geometric programs, a class of convex programs that arise naturally in applications including matrix scaling, matrix balancing, and entropy maximization. Our condition numbers are natural geometric quantities associated with the Newton polytope of the geometric program, and lead to diameter bounds on approximate minimizers. We also provide effective bounds on the condition numbers both in general and under combinatorial assumptions on the Newton polytope. In this way, we generalize the iteration complexity of recent interior-point methods for matrix scaling and matrix balancing. Recently, there has been much work on algorithms for certain optimization problems on Lie groups, known as capacity and scaling problems. For commutative groups, these problems reduce to unconstrained geometric programs, which serves as a particular source of motivation for our work.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Efficient algorithms for tensor scaling, quantum marginals and moment polytopes

We present a polynomial time algorithm to approximately scale tensors of any format to arbitrary prescribed marginals (whenever possible). This unifies and generalizes a sequence of past works on matrix, operator and tensor scaling. Our algorithm provides an efficient weak membership oracle for the associated moment polytopes, an important family of implicitly-defined convex polytopes with exponentially many facets and a wide range of applications. These include the entanglement polytopes from quantum information theory (in particular, we obtain an efficient solution to the notorious one-body quantum marginal problem) and the Kronecker polytopes from representation theory (which capture the asymptotic support of Kronecker coefficients). Our algorithm can be applied to succinct descriptions of the input tensor whenever the marginals can be efficiently computed, as in the important case of matrix product states or tensor-train decompositions, widely used in computational physics and numerical mathematics. We strengthen and generalize the alternating minimization approach of previous papers by introducing the theory of highest weight vectors from representation theory into the numerical optimization framework. We show that highest weight vectors are natural potential functions for scaling algorithms and prove new bounds on their evaluations to obtain polynomial-time convergence. Our techniques are general and we believe that they will be instrumental to obtain efficient algorithms for moment polytopes beyond the ones consider here, and more broadly, for other optimization problems possessing natural symmetries.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory

Alternating minimization heuristics seek to solve a (difficult) global optimization task through iteratively solving a sequence of (much easier) local optimization tasks on different parts (or blocks) of the input parameters. While popular and widely applicable, very few examples of this heuristic are rigorously shown to converge to optimality, and even fewer to do so efficiently. In this paper we present a general framework which is amenable to rigorous analysis, and expose its applicability. Its main feature is that the local optimization domains are each a group of invertible matrices, together naturally acting on tensors, and the optimization problem is minimizing the norm of an input tensor under this joint action. The solution of this optimization problem captures a basic problem in Invariant Theory, called the null-cone problem. This algebraic framework turns out to encompass natural computational problems in combinatorial optimization, algebra, analysis, quantum information theory, and geometric complexity theory. It includes and extends to high dimensions the recent advances on (2-dimensional) operator scaling. Our main result is a fully polynomial time approximation scheme for this general problem, which may be viewed as a multi-dimensional scaling algorithm. This directly leads to progress on some of the problems in the areas above, and a unified view of others. We explain how faster convergence of an algorithm for the same problem will allow resolving central open problems. Our main techniques come from Invariant Theory, and include its rich non-commutative duality theory, and new bounds on the bitsizes of coefficients of invariant polynomials. They enrich the algorithmic toolbox of this very computational field of mathematics, and are directly related to some challenges in geometric complexity theory (GCT).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Condition of intersecting a projective variety with a varying linear subspace

The numerical condition of the problem of intersecting a fixed $m$-dimensional irreducible complex projective variety $Z\subseteq\mathbb{P}^n$ with a varying linear subspace $L\subseteq\mathbb{P}^n$ of complementary dimension $s=n-m$ is studied. We define the intersection condition number $κ_Z(L,z)$ at a smooth intersection point $z\in Z\cap L$ as the norm of the derivative of the locally defined solution map $\mathbb{G}(s,\mathbb{P}^n)\to\mathbb{P}^n,\, L\mapsto z$. We show that $κ_Z(L,z) = 1/\sinα$, where $α$ is the minimum angle between the tangent spaces $T_zZ$ and $T_zL$. From this, we derive a condition number theorem that expresses $1/κ_Z(L,z)$ as the distance of $L$ to the local Schubert variety, which consists of the linear subspaces having an ill-posed intersection with $Z$ at $z$. A probabilistic analysis of the maximum condition number $κ_Z(L) := \max κ_Z(L,z_i)$, taken over all intersection points $z_i\in Z\cap L$, leads to the study of the volume of tubes around the Hurwitz hypersurface $Σ(Z)$. As a first step towards this, we express the volume of $Σ(Z)$ in terms of its degree.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Distribution of the eigenvalues of a random system of homogeneous polynomials

Let $f=(f_1,\ldots,f_n)$ be a system of $n$ complex homogeneous polynomials in $n$ variables of degree $d$. We call $λ\in\mathbb{C}$ an eigenvalue of $f$ if there exists $v\in\mathbb{C}^n\backslash\{0\}$ with $f(v)=λv$, generalizing the case of eigenvalues of matrices ($d=1$). We derive the distribution of $λ$ when the $f_i$ are independently chosen at random according to the unitary invariant Weyl distribution and determine the limit distribution for $n\to\infty$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Permanent versus determinant, obstructions, and Kronecker coefficients

We give an introduction to some of the recent ideas that go under the name "geometric complexity theory". We first sketch the proof of the known upper and lower bounds for the determinantal complexity of the permanent. We then introduce the concept of a representation theoretic obstruction, which has close links to algebraic combinatorics, and we explain some of the insights gained so far. In particular, we address very recent insights on the complexity of testing the positivity of Kronecker coefficients. We also briefly discuss the related asymptotic version of this question.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A stable, polynomial-time algorithm for the eigenpair problem

We describe algorithms for computing eigenpairs (eigenvalue-eigenvector pairs) of a complex $n\times n$ matrix $A$. These algorithms are numerically stable, strongly accurate, and theoretically efficient (i.e., polynomial-time). We do not believe they outperform in practice the algorithms currently used for this computational problem. The merit of our paper is to give a positive answer to a long-standing open problem in numerical linear algebra.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Condition length and complexity for the solution of polynomial systems

Smale's 17th problem asks for an algorithm which finds an approximate zero of polynomial systems in average polynomial time (see Smale 2000). The main progress on Smale's problem is Beltrán-Pardo (2011) and Bürgisser-Cucker (2010). In this paper we will improve on both approaches and we prove an important intermediate result. Our main results are Theorem 1 on the complexity of a randomized algorithm which improves the result of Beltrán-Pardo (2011), Theorem 2 on the average of the condition number of polynomial systems which improves the estimate found in Bürgisser-Cucker (2010), and Theorem 3 on the complexity of finding a single zero of polynomial systems. This last Theorem is the main result of Bürgisser-Cucker (2010). We give a proof of it relying only on homotopy methods, thus removing the need for the elimination theory methods used in Bürgisser-Cucker (2010). We build on methods developed in Armentano et al. (2015).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Fundamental invariants of orbit closures

For several objects of interest in geometric complexity theory, namely for the determinant, the permanent, the product of variables, the power sum, the unit tensor, and the matrix multiplication tensor, we introduce and study a fundamental SL-invariant function that relates the coordinate ring of the orbit with the coordinate ring of its closure. For the power sums we can write down this fundamental invariant explicitly in most cases. Our constructions generalize the two Aronhold invariants on ternary cubics. For the other objects we identify the invariant function conditional on intriguing combinatorial problems much like the well-known Alon-Tarsi conjecture on Latin squares. We provide computer calculations in small dimensions for these cases. As a main tool for our analysis, we determine the stabilizers, and we establish the polystability of all the mentioned forms and tensors (including the generic ones).

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A stable, polynomial-time algorithm for the eigenpair problem

We describe algorithms for computing eigenpairs (eigenvalue--eigenvector) of a complex $n\times n$ matrix $A$. These algorithms are numerically stable, strongly accurate, and theoretically efficient (i.e., polynomial-time). We do not believe they outperform in practice the algorithms currently used for this computational problem. The merit of our paper is to give a positive answer to a long-standing open problem in numerical linear algebra.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Deciding Positivity of Littlewood-Richardson Coefficients

Starting with Knutson and Tao's hive model (in J. Amer. Math. Soc., 1999) we characterize the Littlewood-Richardson coefficient $c_{λ,μ}^ν$ of given partitions $λ,μ,ν\in N^n$ as the number of capacity achieving hive flows on the honeycomb graph. Based on this, we design a polynomial time algorithm for deciding $c_{λ,μ}^ν>0$. This algorithm is easy to state and takes $O(n^3 \log ν_1)$ arithmetic operations and comparisons. We further show that the capacity achieving hive flows can be seen as the vertices of a connected graph, which leads to new structural insights into Littlewood-Richardson coefficients.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Explicit Lower Bounds via Geometric Complexity Theory

We prove the lower bound R(M_m) \geq 3/2 m^2 - 2 on the border rank of m x m matrix multiplication by exhibiting explicit representation theoretic (occurence) obstructions in the sense of the geometric complexity theory (GCT) program. While this bound is weaker than the one recently obtained by Landsberg and Ottaviani, these are the first significant lower bounds obtained within the GCT program. Behind the proof is the new combinatorial concept of obstruction designs, which encode highest weight vectors in Sym^d\otimes^3(C^n)^* and provide new insights into Kronecker coefficients.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Probabilistic analysis of the Grassmann condition number

We analyze the probability that a random m-dimensional linear subspace of R^n both intersects a regular closed convex cone C\subseteq R^n and lies within distance αof an m-dimensional subspace not intersecting C (except at the origin). The result is expressed in terms of the spherical intrinsic volumes of the cone C. This allows us to perform an average analysis of the Grassmann condition number \C(A) for the homogeneous convex feasibility problem \exists x\in C\setminus 0 : Ax=0. The Grassmann condition number is a geometric version of Renegar's condition number, that we have introduced recently in [SIOPT 22(3):1029-1041, 2012]. We thus give the first average analysis of convex programming that is not restricted to linear programming. In particular, we prove that if the entries of A\in R^{m\times n} are chosen i.i.d. standard normal, then for any regular cone C, we have E[ln\C(A)]<1.5 ln(n)+1.5. The proofs rely on various techniques from Riemannian geometry applied to Grassmann manifolds.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A coordinate-free condition number for convex programming

We introduce and analyze a natural geometric version of Renegar's condition number R for the homogeneous convex feasibility problem associated with a regular cone C subseteq R^n. Let Gr_{n,m} denote the Grassmann manifold of m-dimensional linear subspaces of R^n and consider the projection distance d_p(W_1,W_2) := ||Pi_{W_1} - Pi_{W_2}|| (spectral norm) between W_1 and W_2 in Gr_{n,m}, where Pi_{W_i} denotes the orthogonal projection onto W_i. We call C_G(W) := max {d_p(W,W')^{-1} | W' \in Sigma_m} the Grassmann condition number of W in Gr_{n,m}, where the set of ill-posed instances Sigma_m subset Gr_{n,m} is defined as the set of linear subspaces touching C. We show that if W = im(A^T) for a matrix A in R^{m\times n}, then C_G(W) \le R(A) \le C_G(W) kappa(A), where kappa(A) =||A|| ||A^\dagger|| denotes the matrix condition number. This extends work by Belloni and Freund in Math. Program. 119:95-107 (2009). Furthermore, we show that C_G(W) can as well be characterized in terms of the Riemannian distance metric on Gr_{n,m}. This differential geometric characterization of C_G(W) is the starting point of the sequel [arXiv:1112.2603] to this paper, where the first probabilistic analysis of Renegar's condition number for an arbitrary regular cone C is achieved.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Coverage processes on spheres and condition numbers for linear programming

This paper has two agendas. Firstly, we exhibit new results for coverage processes. Let $p(n,m,α)$ be the probability that $n$ spherical caps of angular radius $α$ in $S^m$ do not cover the whole sphere $S^m$. We give an exact formula for $p(n,m,α)$ in the case $α\in[π/2,π]$ and an upper bound for $p(n,m,α)$ in the case $α\in [0,π/2]$ which tends to $p(n,m,π/2)$ when $α\toπ/2$. In the case $α\in[0,π/2]$ this yields upper bounds for the expected number of spherical caps of radius $α$ that are needed to cover $S^m$. Secondly, we study the condition number ${\mathscr{C}}(A)$ of the linear programming feasibility problem $\exists x\in\mathbb{R}^{m+1}Ax\le0,x\ne0$ where $A\in\mathbb{R}^{n\times(m+1)}$ is randomly chosen according to the standard normal distribution. We exactly determine the distribution of ${\mathscr{C}}(A)$ conditioned to $A$ being feasible and provide an upper bound on the distribution function in the infeasible case. Using these results, we show that $\mathbf{E}(\ln{\mathscr{C}}(A))\le2\ln(m+1)+3.31$ for all $n>m$, the sharpest bound for this expectancy as of today. Both agendas are related through a result which translates between coverage and condition.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Even Partitions in Plethysms

We prove that for all natural numbers k,n,d with k <= d and every partition lambda of size kn with at most k parts there exists an irreducible GL(d, C)-representation of highest weight 2*lambda in the plethysm Sym^k(Sym^(2n) (C^d)). This gives an affirmative answer to a conjecture by Weintraub (J. Algebra, 129 (1):103-114, 1990). Our investigation is motivated by questions of geometric complexity theory and uses ideas from quantum information theory.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Robust Smoothed Analysis of a Condition Number for Linear Programming

We perform a smoothed analysis of the GCC-condition number C(A) of the linear programming feasibility problem \exists x\in\R^{m+1} Ax < 0. Suppose that \bar{A} is any matrix with rows \bar{a_i} of euclidean norm 1 and, independently for all i, let a_i be a random perturbation of \bar{a_i} following the uniform distribution in the spherical disk in S^m of angular radius \arcsinσand centered at \bar{a_i}. We prove that E(\ln C(A)) = O(mn / σ). A similar result was shown for Renegar's condition number and Gaussian perturbations by Dunagan, Spielman, and Teng [arXiv:cs.DS/0302011]. Our result is robust in the sense that it easily extends to radially symmetric probability distributions supported on a spherical disk of radius \arcsinσ, whose density may even have a singularity at the center of the perturbation. Our proofs combine ideas from a recent paper of Bürgisser, Cucker, and Lotz (Math. Comp. 77, No. 263, 2008) with techniques of Dunagan et al.

0 citations0 reviewsNo code linkedOpen access