Using Oriented Matroids to Bound the Monotone Rank of a Matrix

Abstract. Estimating the linear dimensionality of a data set in the presence of noise is a common problem. However, data may also be corrupted by monotone nonlinear distortion that preserves the ordering of matrix entries but causes linear methods for estimating rank to fail. In light of this, we consider the problem of computing the monotone rank, which is the lowest rank consistent with the ordering within columns. We show that each matrix of monotone rank [Formula: see text] corresponds to a point arrangement and a hyperplane arrangement in [Formula: see text], and that the ordering within columns of the matrix can be used to recover information about these arrangements. Using Radon’s theorem and the related concept of the VC-dimension, we can obtain lower bounds on the monotone rank of a matrix. However, we also show that the monotone rank of a matrix can exceed these bounds. In order to obtain better bounds on monotone rank, we develop the connection between monotone rank estimation and oriented matroid theory. Using this connection, we show that monotone rank is difficult to compute: the problem of deciding whether a matrix has monotone rank two is already NP-hard. However, we introduce an “oriented matroid completion” problem as a combinatorial relaxation of the monotone rank problem and show that checking whether a set of sign vectors has matroid completion rank two is easy.