Instance-Optimal Compressed Sensing via Posterior Sampling

            Ajil Jalal 1 Sushrut Karmalkar 2 Alexandros G. Dimakis 1 Eric Price 2

            Abstract                 for a measurement matrix A ∈ Rm×n and noise vector
                                 ξ ∈ Rm . We will focus on the i.i.d. Gaussian setting, where
   We characterize the measurement complexity of              1           2
   compressed sensing of signals drawn from a         Aij  N (0, m ) and ξi  N (0, σm ), and one  ...