Asymptotic Analysis of MAP Estimation via the Replica Method and Compressed Sensing
The replica method is a non-rigorous but widely-used technique from statistical physics used in the asymptotic analysis of many large random nonlinear problems. This paper applies the replica method to non-Gaussian MAP estimation. It is shown that with large random linear measurements and Gaussian noise, the asymptotic behavior of the MAP estimate of an n-dimensional vector ``decouples as n scalar MAP estimators. The result is a counterpart to Guo and Verdus replica analysis on MMSE estimation. The replica MAP analysis can be readily applied to many estimators used in compressed sensing, including basis pursuit, lasso, linear estimation with thresholding and zero-norm estimation. In the case of lasso estimation, the scalar estimator reduces to a soft-thresholding operator and for zero-norm estimation it reduces to a hard-threshold. Among other benefits, the replica method provides a computationally tractable method for exactly computing various performance metrics including MSE and sparsity recovery.
Code (0)
등록된 구현이 없습니다.
Tasks
compressed sensingSimilar Papers 제목 키워드 기반
Noise Variance Estimation Using Asymptotic Residual in Compressed Sensing
In compressed sensing, measurements are typically contaminated by additive noise, and therefore, information about the noise variance is often needed to design algorithms. In this paper, we propose a method for estimatin…
compressed sensingAsymptotic Performance Prediction for ADMM-Based Compressed Sensing
In this paper, we propose a method to predict the asymptotic performance of the alternating direction method of multipliers (ADMM) for compressed sensing, where we reconstruct an unknown structured signal from its underd…
compressed sensingPredictionRecursive Compressed Sensing
We introduce a recursive algorithm for performing compressed sensing on streaming data. The approach consists of a) recursive encoding, where we sample the input stream via overlapping windowing and make use of the previ…
compressed sensingOn the Achievability of Cramér-Rao Bound In Noisy Compressed Sensing
Recently, it has been proved in Babadi et al. that in noisy compressed sensing, a joint typical estimator can asymptotically achieve the Cramer-Rao lower bound of the problem.To prove this result, this paper used a lemma…
compressed sensingLEMMAPrecise asymptotics for phase retrieval and compressed sensing with random generative priors
We consider the problem of compressed sensing and of (real-valued) phase retrieval with random measurement matrix. We analyse sharp asymptotics of the information-theoretically optimal performance and that of the best kn…
compressed sensingRetrieval