Instance-optimality in probability with an \(\ell _1\)-minimization decoder (Q734324)

The purpose of the paper is to point out that a weaker geometric property of the studied already by A. Litvak et al. random matrices, when coupled with decoding by minimization will yield instance-optimality in probability for the large range of \(k\). The first sections of the paper concentrate on proving instance-optimality for Bernoulli matrices where the proofs are most transparent. In Section 3, a geometric mapping property of Bernoulli matrices is presented (Theorem 3.5). This property is used to prove in Section 4 that instance-optimality in probability holds for Bernoulli matrices. The arguments are organized to extract the essential properties of Bernoulli matrices that are needed for the proof. In Section 5, it is shown that these properties hold for quite general random families and thereby obtain a broad generalization of the Bernoulli case.