Finding hidden low dimensional structure in data distorted by monotone transformations

Abstract: Measurements of biological data are often distorted by unknown monotone transformations. While these nonlinear distortions make detecting low-dimensional structure using traditional matrix analysis impossible, we can recover some of this hidden structure using combinatorial and topological techniques. In this talk, we explore the underlying rank of a matrix A, which we define as the smallest value of such that there is a rank r matrix B and monotone function f such that A_ij = f(B_ij). We give several methods for estimating underlying rank. To derive these bounds, we decompose matrices as pairs of point configurations and use the order of matrix entries to extract geometric information about these point configurations. In particular, motivated by results from the theory of random polytopes, we define the minimal nodes of a matrix and show that it is possible to estimate the underlying rank of a random matrix by counting minimal nodes. We also derive lower bounds on monotone rank via Radon’s theorem, and show that it is possible for the underlying rank of a matrix to exceed these bounds using ideas from oriented matroid theory.

Back to Search Research Symposium Abstracts