The classical Chow form encodes any projective variety by one equation. We here introduce the Chow-Lam form for subvarieties of a Grassmannian. By evaluating the Chow-Lam form at twistor coordinates, we obtain universal projection formulas. These were pioneered by Thomas Lam for positroid varieties in the study of amplituhedra, and we develop his approach further. Universal formulas for branch loci are obtained from Hurwitz-Lam forms. Our focus is on computations and applications in geometry.

Abstract We recover plane curves from their branch points under projection onto a line. Our focus lies on cubics and quartics. These have 6 and 12 branch points respectively. The plane Hurwitz numbers 40 and 120 count the orbits of solutions. We determine the numbers of real solutions, and we present exact algorithms for recovery. Our approach relies on 150 years of beautiful algebraic geometry, from Clebsch to Vakil and beyond.

The setting of this article is nonparametric algebraic statistics. We study moment varieties of conditionally independent mixture distributions on . These are the secant varieties of toric varieties that express independence in terms of univariate moments. Our results revolve around the dimensions and defining polynomials of these varieties.

We impose rank one constraints on marginalizations of a tensor, given by a simplicial complex. Following work of Kirkup and Sullivant, such marginal independence models can be made toric by a linear change of coordinates. We study their toric ideals, with emphasis on random graph models and independent set polytopes of matroids. We develop the numerical algebra of parameter estimation, using both Euclidean distance and maximum likelihood, and we present a comprehensive database of small models.

Abstract Smooth tropical cubic surfaces are parametrized by maximal cones in the unimodular secondary fan of the triple tetrahedron. There are $$344\, 843 \,867$$ 344 843 867 such cones, organized into a database of $$14\,373\,645$$ 14 373 645 symmetry classes. The Schläfli fan gives a further refinement of these cones. It reveals all possible patterns of lines on tropical cubic surfaces, thus serving as a combinatorial base space for the universal Fano variety. This article develops the relevant theory and offers a blueprint for the analysis of big data in tropical geometry.

The intersection of a quadric and a cubic surface in 3-space is a canonical curve of genus 4. It has 120 complex tritangent planes. We present algorithms for computing real tritangents, and we study the associated discriminants. We focus on space sextics that arise from del Pezzo surfaces of degree one. Their numbers of planes that are tangent at three real points vary widely; both 0 and 120 are attained. This solves a problem suggested by Arnold Emch in 1928.

We present a new insight into the systematic generation of minimal solvers in computer vision, which leads to smaller and faster solvers. Many minimal problem formulations are coupled sets of linear and polynomial equations where image measurements enter the linear equations only. We show that it is useful to solve such systems by first eliminating all the unknowns that do not appear in the linear equations and then extending solutions to the rest of unknowns. This can be generalized to fully non-linear systems by linearization via lifting. We demonstrate that this approach leads to more efficient solvers in three problems of partially calibrated relative camera pose computation with unknown focal length and/or radial distortion. Our approach also generates new interesting constraints on the fundamental matrices of partially calibrated cameras, which were not known before.

The rational camera model recently introduced in [18] provides a general methodology for studying abstract nonlinear imaging systems and their multi-view geometry. This paper builds on this framework to study physical realizations of rational cameras. More precisely, we give an explicit account of the mapping between between physical visual rays and image points (missing in the original description), which allows us to give simple analytical expressions for direct and inverse projections. We also consider primitive camera models, that are orbits under the action of various projective transformations, and lead to a general notion of intrinsic parameters. The methodology is general, but it is illustrated concretely by an in-depth study of two-slit cameras, that we model using pairs of linear projections. This simple analytical form allows us to describe models for the corresponding primitive cameras, to introduce intrinsic parameters with a clear geometric meaning, and to define an epipolar tensor characterizing two-view correspondences. In turn, this leads to new algorithms for structure from motion and self-calibration.

We study the geometry of metrics and convexity structures on the space of phylogenetic trees, which is here realized as the tropical linear space of all ultrametrics. The ${CAT}(0)$ metric of Billera--Holmes--Vogtman arises from the theory of orthant spaces. While its geodesics can be computed by the Owen--Provan algorithm, geodesic triangles are complicated. We show that the dimension of such a triangle can be arbitrarily high. Tropical convexity and the tropical metric exhibit properties that are desirable for geometric statistics, such as geodesics of small depth.

Maximum likelihood estimation is a fundamental computational task in statistics. We address this problem for manifolds of low rank matrices. These represent mixtures of independent distributions of two discrete random variables. This non-convex optimization problems lead to some beautiful geometry, topology, and combinatorics. We discuss methods for finding the global maximum of the likelihood function, we present a duality theorem due to Draisma and Rodriguez, and we share recent work with Kubkas and Robeva concerning nonnegative rank and the EM algorithm.

We find the capacity pre-log of a temporally correlated Rayleigh block-fading single-input multiple-output (SIMO) channel in the noncoherent setting. It is well known that for block-lengthLand rank of the channel covariance matrix equal toQ, the capacity pre-log in the single-input single-output (SISO) case is given by 1-Q/L. Here,Q/Lcan be interpreted as the pre-log penalty incurred by channel uncertainty. Our main result reveals that, by adding only one receive antenna, this penalty can be reduced to 1/Land can, hence, be made to vanish for the block-lengthL→∞, even ifQ/Lremains constant asL→∞. Intuitively, even though the SISO channels between the transmit antenna and the two receive antennas are statistically independent, the transmit signal induces enough statistical dependence between the corresponding receive signals for the second receive antenna to be able to resolve the uncertainty associated with the first receive antenna's channel and thereby make the overall system appear coherent. The proof of our main theorem is based on a deep result from algebraic geometry known as Hironaka's Theorem on the Resolution of Singularities.

We establish a lower bound on the noncoherent capacity pre-log of a temporally correlated Rayleigh block-fading single-input multiple-output (SIMO) channel. Our result holds for arbitrary rank Q of the channel correlation matrix, arbitrary block-length L >; Q, and arbitrary number of receive antennas R, and includes the result in Morgenshtern et al. (2010) as a special case. It is well known that the capacity pre-log for this channel in the single-input single-output (SISO) case is given by 1-Q/L, where Q/L is the penalty incurred by channel uncertainty. Our result reveals that this penalty can be reduced to 1/L by adding only one receive antenna, provided that L ≥ 2Q - 1 and the channel correlation matrix satisfies mild technical conditions. The main technical tool used to prove our result is Hironaka's celebrated theorem on resolution of singularities in algebraic geometry.

MOTIVATION: Developmental transcriptional networks in plants and animals operate in both space and time. To understand these transcriptional networks it is essential to obtain whole-genome expression data at high spatiotemporal resolution. Substantial amounts of spatial and temporal microarray expression data previously have been obtained for the Arabidopsis root; however, these two dimensions of data have not been integrated thoroughly. Complicating this integration is the fact that these data are heterogeneous and incomplete, with observed expression levels representing complex spatial or temporal mixtures. RESULTS: Given these partial observations, we present a novel method for reconstructing integrated high-resolution spatiotemporal data. Our method is based on a new iterative algorithm for finding approximate roots to systems of bilinear equations. AVAILABILITY: Source code for solving bilinear equations is available at http://math.berkeley.edu/ approximately dustin/bilinear/. Visualizations of reconstructed patterns on a schematic Arabidopsis root are available at http://www.arexdb.org/.

Convex rank tests are partitions of the symmetric group which have desirable geometric properties. The statistical tests defined by such partitions involve counting all permutations in the equivalence classes. Each class consists of the linear extensions of a partially ordered set specified by data. Our methods refine existing rank tests of nonparametric statistics, such as the sign test and the runs test, and are useful for exploratory analysis of ordinal data. We establish a bijection between convex rank tests and probabilistic conditional independence structures known as semigraphoids. The subclass of submodular rank tests is derived from faces of the cone of submodular functions or from Minkowski summands of the permutohedron. We enumerate all small instances of such rank tests. Of particular interest are graphical tests, which correspond to both graphical models and to graph associahedra.

The classic algorithms of Needleman-Wunsch and Smith-Waterman find a maximum a posteriori probability alignment for a pair hidden Markov model (PHMM). To process large genomes that have undergone complex genome rearrangements, almost all existing whole genome alignment methods apply fast heuristics to divide genomes into small pieces that are suitable for Needleman-Wunsch alignment. In these alignment methods, it is standard practice to fix the parameters and to produce a single alignment for subsequent analysis by biologists. As the number of alignment programs applied on a whole genome scale continues to increase, so does the disagreement in their results. The alignments produced by different programs vary greatly, especially in non-coding regions of eukaryotic genomes where the biologically correct alignment is hard to find. Parametric alignment is one possible remedy. This methodology resolves the issue of robustness to changes in parameters by finding all optimal alignments for all possible parameters in a PHMM. Our main result is the construction of a whole genome parametric alignment of Drosophila melanogaster and Drosophila pseudoobscura. This alignment draws on existing heuristics for dividing whole genomes into small pieces for alignment, and it relies on advances we have made in computing convex polytopes that allow us to parametrically align non-coding regions using biologically realistic models. We demonstrate the utility of our parametric alignment for biological inference by showing that cis-regulatory elements are more conserved between Drosophila melanogaster and Drosophila pseudoobscura than previously thought. We also show how whole genome parametric alignment can be used to quantitatively assess the dependence of branch length estimates on alignment parameters.

This paper deals with a problem from computational convexity and its application to computer algebra. This paper determines the complexity of computing the Minkowski sum of k convex polytopes in $\mathbb{R}^d $, which are presented either in terms of vertices or in terms of facets. In particular, if the dimension d is fixed, the authors obtain a polynomial time algorithm for adding k polytopes with up to n vertices. The second part of this paper introduces dynamic versions of Buchberger’s Gröbner bases algorithm for polynomial ideals. Using the Minkowski addition of Newton polytopes, the authors show that the following problem can be solved in polynomial time for any finite set of polynomials $\mathcal{T} \subset K [ x_1 , \ldots ,x_d ]$, where d is fixed: Does there exist a term order $\tau $ such that $\mathcal{T}$ is a Gröbner basis for its ideal with respect to $\tau $? If not, find an optimal term order for $\mathcal{T}$ with respect to a natural Hilbert function criterion.

This article deals with algorithmic and structural aspects related to the computer-aided study of incidence configurations in plane projective geometry. We describe invariant-theoretic algorithms and complexity results for computing the realization space and deciding the coordinatizability of configurations. A practical procedure for automated theorem proving in projective geometry is obtained as a special case. We use the final polynomial technique of Bokowski and Whiteley for encoding the resulting proofs, and we apply Buch-berger's Gröbner basis method for computing minimum degree final polynomials and final syzygies, thus attaining the bounds in the recent effective versions of Hubert's Nullstellen-satz.

We prove that, after multiplication with a suitable monomial, every homogeneous bracket polynomial of rank r≥3 can be factored into a meet and join expression in the Cayley algebra. The main tool in our construction is an explicit algorithm for rewriting polynomial functions in terms of synthetic constructions in projective geometry. We also discuss applications of Cayley factorization to automated geometry theorem proving.

We give doubly exponential upper and lower bounds on the size of the smallest grid on which we can embed every planar configuration of n points in general position up to order type. The lower bound is achieved by the construction of a widely dispersed “rigid” configuration which is then modified to one in general position by recent techniques of Sturmfels and White, while the upper bound uses recent results of Grigor'ev and Vorobjou on the solution of simultaneous inequalities. This provides a sharp answer to a question first posed by Chazelle.

Affine Gale diagrams are of one dimension lower than the well-known Gale transforms, and thus k-polytopes with $k + 4$ vertices can be represented by planar point configurations. The underlying algebraic reduction is due to Bokowski [6], while similar geometric arguments were used before by Perles [12]. In this paper we consider affine Gale diagrams as a special case of oriented matroid duality, and we apply this technique to several convex geometrical problems. As the main result we establish a new negative Steinitz-type theorem in the spirit of [25]; the face lattices of simplicial k-polytopes with $k + 4$ vertices cannot be characterized locally. We answer two questions posed in [11] concerning Kleinschmidt’s 4-polytope Q with a facet of nonarbitrary shape [15], and we describe another such 4-polytope P with minimal number of facets. We characterize the affine Gale diagrams corresponding to a given simplicial complex, and we discuss as an example Möbius’ torus with 7 vertices. Finally, we prove a partial result on Perles’ problem whether all simplicial polytopes are quotients of neighborly polytopes.