Algebra and geometry of matroids

Matroids are one of the basic structures in combinatorics, like graphs and partially ordered sets. As such they appear throughout combinatorics and associated areas, including optimization, operations research, coding and information theory, computer science, algebraic geometry, and have connections to biology, physics, and statistics. A matroid is built on a set of objects, and picks out certain smaller collections of those objects as being somehow compatible in a way that represents _independence_. (For example, if the objects are vectors and two of them sum to a third, the three together are not independent.)

In roughly the last decade, much progress has been made on old questions pertaining to the structure of matroids by new methods drawn from the techniques of algebra and geometry: instead of just considering the structure of a matroid from scratch, start by associating it to a collection of polynomial equations; or instead of just remembering the independence relations as above, perhaps, make a richer structure that remembers more algebra of the original set of objects. My projects consist of attempts to systematise, unify, and extend these approaches, and in so doing build on the aforementioned progress.

I have detailed academic beneficiaries of my research above.
Besides these, my research has significant potential to impact society.
At this stage I have not yet embarked on any concrete
collaborations with non-academic beneficiaries,
but I am aware of a number of directions in which these impacts may be found.
In this section I discuss some examples.

Combinatorial algebraic geometry has very wide applicability, for instance in situations like the following.
It is common to encounter systems
whose state may be modelled by a list of numerical values.
These values may not be able to vary freely; there may be
relationships among them that hold in any state,
and sometimes these turn out to involve only polynomial equations.
When this happens, the collection of all states of the
system is (essentially) an _algebraic variety_,
the object of study of algebraic geometry.
Now, measurements or design considerations
often provide coarse or partial information about
the system or the constraints on it, the sort of information
that can be characterised as _combinatorial_, so that
combinatorial algebraic geometry is exactly the tool needed to
understand its implications.
This approach has succeeded, for instance, in questions including the following:
* If several cameras are recording the same scene, what are the possible
sets of positions at which a single object may appear in the various cameras?
* In a system containing several inter-reacting chemicals,
what are the possible concentrations of each chemical in stable states?
* In a mechanical system, such as a robot, given the lengths and angles
of its joints, what position might its hand or platform (say) be in, or vice versa?

As for matroids, the other element of my scientific proposal,
they can be expected to figure whenever the relationships between the values
are linear, or (via algebraic matroids) even when this is
not the case. Here are two particular examples where my proposed research may be of use.

One is in machine learning and data processing, both fields in which the problem arises of filling in entries in an incomplete matrix so the result has low rank. In machine learning this arises for instance in ``missing feature imputation'' problems when one tries to fit data with a factor model involving a small number of factors; in signal reconstruction, it allows more efficient sampling when one has a large array of antennae tracking a small number of targets to be detected.
Existing theory regarding this problem typically assumes the positions of missing matrix entries are randomly sampled, but in practice they are often nonrandom and have exploitable combinatorics.
Whether a matrix is reconstructible
is encapsulated by a certain algebraic matroid, which is one for which the approach of my proposed research on algebraic matroids may be especially convenient, possibly leading to better
guarantees for reconstruction algorithms where the known data is structured.

A second is in hierarchical clustering, especially in phylogenetics. Here one faces the problem of grouping a collection of data points into clusters in a hierarchical fashion: these might be species (or languages, vel sim), where the clusters indicate which groups had a common ancestor.
In practical clustering problems the measurements which are practical to make
are often measurements of difference or similarity between two individual taxa, or a small number more than two. If one beings with a phylogenetic tree, the lists of distance measures that can be so obtained are in fact coordinates of a tropical linear space, and this fact underlies one class of clustering algorithm currently used in practice. My proposed research might therefore open the way to better clustering algorithms.