Conference abstracts

Session S01 - Computational Algebra and Applications of Algebra

July 29, 15:00 ~ 15:25

Dowker complex, convex codes, and detecting hidden matrix factorizations.

Vladimir Itskov

The Pennsylvania State University, US   -

Detecting low-rank structure is often key for understanding data. This task, however, is particularly challenging in the presence of an unknown nonlinearity — i.e., where one must detect the existence of a factorization $C_{il}=f(\sum_{a=1}^d A_{ia}B_{al})$ with small d, where $f(x)$ is an unknown monotone nonlinearity.

$\, $ It turns out that homological features of the Dowker complex associated to the matrix $C$ can be used to detect such a factorization, but the reason is somewhat mysterious. To understand why this works, we consider the relationship between the Dowker complex of $C$ and a convex code associated to the factors A and B. A convex code is a subset of $2^{[n]}$ that arises from intersection patterns of convex sets in some Euclidean space - in this case, the codewords correspond to selected chambers of a hyperplane arrangement. I will give a short introduction to the connection between Dowker complexes, convex codes, and matrix factorizations, reviewing our recent results and some open problems.

Joint work with Chad Giusti (University of Pennsylvania).

View abstract PDF