Can I read Using Oriented Matroids to Find Low Rank Structure in Presence of Nonlinearity on EtoBox?

Using Oriented Matroids to Find Low Rank Structure in Presence of Nonlinearity by Lienkaemper, Caitlin is a scholarly article available to read on EtoBox.

What is Using Oriented Matroids to Find Low Rank Structure in Presence of Nonlinearity about?

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 \emph{underlying rank}, which is the lowest rank consistent with the ordering of matrix entries, and \emph{monotone rank}, which is the lowest rank consistent with the ordering within columns. We show that each matrix of monotone rank $d$ corresponds to a point arrangement and a hyperplane arrangement in $\mathbb R^{d}$, 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 deci

Author

Lienkaemper, Caitlin

Published

2023

Language

EN