Completion of matrices with low description complexity
AuthorsErwin Riegler, Günther Koliander, David Stotz, and Helmut Bölcskei
ReferenceMathematical Statistics and Learning, Nov. 2023, submitted.
AbstractWe 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.
KeywordsMatrix completion, compressed sensing, geometric measure theory, Hausdorff dimension, Minkowski dimension, rank-1 measurements
Download this document:
Copyright Notice: © 2023 E. Riegler, G. Koliander, D. Stotz, and H. Bölcskei.
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.