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 - vladimir.itskov@psu.edu
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).