To average or not to average: Trade-off in compressed sensing with noisy measurements

We consider the situation where the total number of measurements is limited in compressed sensing of sparse vectors with noisy measurements. In this situation there is a trade-off between acquiring as many independent observations as possible and performing averaging over several identical measurements in order to improve signal-to-noise ratio. With the help of the approximate message passing algorithm to solve LASSO problems, we have proved, via state evolution, that in order to minimize estimation errors one should perform as many independent linear measurements as possible rather than performing averaging to improve signal-to-noise ratio of the observations. Furthermore, we have confirmed via numerical experiments that the same holds in the case where the measurement matrix is constructed by randomly subsampling rows of a discrete Fourier matrix.