Analysis of weighted $\ell_1$-minimization for model based compressed sensing

Model-based compressed sensing refers to compressed sensing with extra structure about the underlying sparse signal known a priori. Recent work has demonstrated that both for deterministic and probabilistic models imposed on the signal, this extra information can be successfully exploited to enhance recovery performance. In particular, weighted $\ell_1$-minimization with suitable choice of weights has been shown to improve performance at least for a simple class of probabilistic models. In this paper, we consider a more general and natural class of probabilistic models where the underlying probabilities associated with the indices of the sparse signal have a continuously varying nature. We prove that when the measurements are obtained using a matrix with i.i.d Gaussian entries, weighted $\ell_1$-minimization with weights that have a similar continuously varying nature successfully recovers the sparse signal from its measurements with overwhelming probability. It is known that standard $\ell_1$-minimization with uniform weights can recover sparse signals up to a known sparsity level, or expected sparsity level in case of a probabilistic signal model. With suitable choice of weights which are chosen based on our signal model, we show that weighted $\ell_1$-minimization can recover signals beyond the sparsity level achievable by standard $\ell_1$-minimization.