Discrete Geometry and Combinatorics Seminar
Abstract: Determining the rank of a matrix derived from data is a fundamental problem in many fields of biology. However, it is often impossible to measure the true quantity of interest, and we must instead measure a proxy value which has a monotone relationship with the true value. This motivates the following definition: the underlying rank of a matrix $A$ is the minimum rank $d$ such that there is a rank $d$ matrix $B$ whose entries are in the same order as the entries of $A$. In this talk, we introduce a variety of strategies for estimating underlying rank. Using results about random polytopes, we give techniques for estimating the underlying ranks of random matrices which we use to estimate the dimensionality of neural activity in zebrafish. Next, we use Radon's theorem to derive a basic lower bound for underlying rank. We show that underlying rank can exceed this bound using examples derived from oriented matroids and allowable sequences. We show that for $d\geq 2$, determining whether a matrix has underlying rank at most d is complete for the existential theory of the reals, and therefore NP hard. However, for $d=2$, we can solve a combinatorial relaxation of this problem in polynomial time.