Stability of low-rank matrix recovery and its connections to Banach space geometry

There are well-known relationships between compressed sensing and the geometry of the finite-dimensional ℓ_p spaces. A result of Kashin and Temlyakov [20] can be described as a characterization of the stability of the recovery of sparse vectors via ℓ₁-minimization in terms of the Gelfand widths of certain identity mappings between finite-dimensional ℓ₁ and ℓ₂ spaces, whereas a more recent result of Foucart, Pajor, Rauhut and Ullrich [16] proves an analogous relationship even for ℓ_p spaces with p<1. In this paper we prove what we call matrix or noncommutative versions of these results: we characterize the stability of low-rank matrix recovery via Schatten p-(quasi-)norm minimization in terms of the Gelfand widths of certain identity mappings between finite-dimensional Schatten p-spaces.