  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 $\mathcal{U}$ such
that $\mathcal{U}-\mathcal{U}$ has Hausdorff dimension $s$ can be recovered
from $k>s$ measurements, and random matrices supported on a set $\mathcal{U}$
of Hausdorff dimension $s$ can be recovered with probability 1 from $k>s$
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 $\beta$-H\"older continuous mappings
recovering matrices taken from a set of upper Minkowski dimension $s$ from
$k>2s/(1-\beta)$ measurements and, with arbitrarily small probability of error,
random matrices supported on a set of upper Minkowski dimension $s$ from
$k>s/(1-\beta)$ measurements. The numerous concrete examples we consider
include low-rank matrices, sparse matrices, QR decompositions with sparse
R-components, and matrices of fractal nature.
