Completion of matrices with low description complexity

Authors

Erwin Riegler, Günther Koliander, David Stotz, and Helmut Bölcskei

Reference

Mathematical Statistics and Learning, Nov. 2023, submitted.

Abstract

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. Specifically, complexity of the sets of matrices encompassed by the theory is measured in terms of Hausdorff and upper 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. Concretely, we show that matrices taken from a set U such that U − U has Hausdorff dimension 𝑠 can be recovered from 𝑘 > 𝑠 measurements, and random matrices supported on a set U of Hausdorff dimension 𝑠 can be recovered with probability 1 from 𝑘 > 𝑠 measurements. What is more, we establish the existence of recovery mappings that are robust against additive perturbations or noise in the measurements. Concretely, we show that there are 𝛽-Hölder continuous mappings recovering matrices taken from a set of upper Minkowski dimension 𝑠 from 𝑘 > 2𝑠/(1 − 𝛽) measurements and, with arbitrarily small probability of error, random matrices supported on a set of upper Minkowski dimension 𝑠 from 𝑘 > 𝑠/(1 − 𝛽) measurements. The numerous concrete examples we consider include low-rank matrices, sparse matrices, QR decompositions with sparse R-components, and matrices of fractal nature.

Keywords

Matrix completion, compressed sensing, geometric measure theory, Hausdorff dimension, Minkowski dimension, rank-1 measurements

Download this document:

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.