Session II.7 - Computational Harmonic Analysis and Data Science
Friday, June 16, 14:00 ~ 15:00
Completion of matrices with low description complexity
Helmut Bölcskei
ETH Zurich, Switzerland - This email address is being protected from spambots. You need JavaScript enabled to view it.
We propose a theory for matrix completion that goes beyond the low-rank structure commonly considered in the literature and applies to general matrices of low description complexity, including sparse matrices, matrices with sparse factorizations such as, e.g., sparse R-factors in their QR-decomposition, and algebraic combinations of matrices of low description complexity. The mathematical concept underlying this theory is that of rectifiability, a basic notion in geometric measure theory. Complexity of the sets of matrices encompassed by the theory is measured in terms of Hausdorff and Minkowski dimensions. Our goal is the characterization of the number of linear measurements, with an emphasis on rank-$1$ measurements, needed for the existence of an algorithm that yields reconstruction, either perfect, with probability $1$, or with arbitrarily small probability of error, depending on the setup. Specifically, we show that matrices taken from a set $U$ such that $U − U$ has Hausdorff dimension $s$ can be recovered from $k \gt s$ measurements, and random matrices supported on a set $U$ of Hausdorff dimension $s$ can be recovered with probability $1$ from $k \gt s$ measurements. What is more, we establish the existence of $\beta$-Hölder continuous decoders recovering matrices taken from a set of upper Minkowski dimension $s$ from $k \gt 2s/(1 − \beta)$ measurements and, with arbitrarily small probability of error, random matrices supported on a set of upper Minkowski dimension $s$ from $k \gt s/(1 − \beta)$ measurements.
Joint work with Erwin Riegler, ETH Zurich, Switzerland, Günther Koliander, Austrian Academy of Sciences, Austria and David Stotz, Kantonsschule Schaffhausen, Switzerland.