This paper considers the fundamental limit of compressed sensing for i.i.d. signal distributions and i.i.d. Gaussian measurement matrices. Its main contribution is a rigorous characterization of the asymptotic mutual information (MI) and minimum mean-square error (MMSE) in this setting. Under mild technical conditions, our results show that the limiting MI and MMSE are equal to the values predicted by the replica method from statistical physics. This resolves a well-known problem that has remained open for over a decade.
The replica method was developed originally to study mean-field approximations in spin glasses @cite_13 @cite_14 . It was first applied to linear estimation problems in the context of CDMA wireless communication @cite_45 @cite_23 @cite_28 , with subsequent work focusing on the compressed sensing directly @cite_26 @cite_38 @cite_11 @cite_43 @cite_25 @cite_39 .
@cite_38 @cite_14 @cite_26 @cite_28 @cite_39 @cite_43 @cite_45 @cite_23 @cite_13 @cite_25 @cite_11
2116394223 2090842051 2942471690 2114351639
We present a theory, based on statistical mechanics, to evaluate analytically the performance of uncoded, fully synchronous, randomly spread code-division multiple-access (CDMA) multiuser detectors with additive white Gaussian noise (AWGN) channel, under perfect power control, and in the large-system limit. Application of the replica method, a tool developed in the literature of statistical mechanics, allows us to derive analytical expressions for the bit-error rate, as well as the multiuser efficiency, of the individually optimum (IO) and jointly optimum (JO) multiuser detectors over the whole range of noise levels. The information-theoretic capacity of the randomly spread CDMA channel and the performance of decorrelating and linear minimum mean-square error (MMSE) detectors are also derived in the same replica formulation, thereby demonstrating validity of the statistical-mechanical approach. The replica method is a nonrigorous but well-known technique from statistical physics used in the asymptotic analysis of large, random, nonlinear problems. This paper applies the replica method, under the assumption of replica symmetry, to study estimators that are maximum a posteriori (MAP) under a postulated prior distribution. It is shown that with random linear measurements and Gaussian noise, the replica-symmetric prediction of the asymptotic behavior of the postulated MAP estimate of an -dimensional vector “decouples” as scalar postulated MAP estimators. The result is based on applying a hardening argument to the replica analysis of postulated posterior mean estimators of Tanaka and of Guo and Verdu. The replica-symmetric postulated MAP analysis can be readily applied to many estimators used in compressed sensing, including basis pursuit, least absolute shrinkage and selection operator (LASSO), linear estimation with thresholding, and zero norm-regularized estimation. In the case of LASSO estimation, the scalar estimator reduces to a soft-thresholding operator, and for zero norm-regularized estimation, it reduces to a hard threshold. Among other benefits, the replica method provides a computationally tractable method for precisely predicting various performance metrics including mean-squared error and sparsity pattern recovery probability. We introduce a method to infer a variational approximation to the posterior distribution of solutions in computational imaging inverse problems. Machine learning methods applied to computational imaging have proven very successful, but have so far largely focused on retrieving a single optimal solution for a given task. Such retrieval is arguably an incomplete description of the solution space, as in ill-posed inverse problems there may be many similarly likely reconstructions. We minimise an upper bound on the divergence between our approximate distribution and the true intractable posterior, thereby obtaining a probabilistic description of the solution space in imaging inverse problems with empirical prior. We demonstrate the advantage of our technique in quantitative simulations with the CelebA dataset and common image reconstruction tasks. We then apply our method to two of the currently most challenging problems in experimental optics: imaging through highly scattering media and imaging through multi-modal optical fibres. In both settings we report state of the art reconstructions, while providing new capabilities, such as estimation of error-bars and visualisation of multiple likely reconstructions. In this paper we generalize to the case of diluted spin models and random combinatorial optimization problems a technique recently introduced by Guerra (cond-mat 0205123) to prove that the replica method generates variational bounds for disordered systems. We analyze a family of models that includes the Viana–Bray model, the diluted p-spin model or random XOR-SAT problem, and the random K-SAT problem, showing that the replica cavity method, at the various levels of approximation, provides systematic schemes to obtain lower bounds of the free-energy at all temperatures and of the ground state energy. In the case of K-SAT and XOR-SAT it thus gives upper bounds of the satisfiability threshold. Our analysis underlines deep connections with the cavity method which are not evident in the long range case.