In this work, we investigate the possibility of compressing a quantum system to one of smaller dimension in a way that preserves the measurement statistics of a given set of observables. In this process, we allow for an arbitrary amount of classical side information. We find that the latter can be bounded, which implies that the minimal compression dimension is stable in the sense that it cannot be decreased by allowing for small errors. Various bounds on the minimal compression dimension are proven, and an SDP-based algorithm for its computation is provided. The results are based on two independent approaches: an operator algebraic method using a fixed-point result by Arveson and an algebro-geometric method that relies on irreducible polynomials and Bézout’s theorem. The latter approach allows lifting the results from the single-copy level to the case of multiple copies and from completely positive to merely positive maps.