Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing

Abstract

The replica method is a non-rigorous 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 n-dimensional vector "decouples" as n 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, 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.

22 pages; added details on the replica symmetry assumption

References in corpus (8)

• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
• Sharp thresholds for high-dimensional and noisy recovery of sparsity
• On-Off Random Access Channels: A Compressed Sensing Framework
• Generalized Approximate Message Passing for Estimation with Random Linear Mixing
• Estimation with Random Linear Mixing, Belief Propagation and Compressed Sensing
• Vector Precoding for Gaussian MIMO Broadcast Channels: Impact of Replica Symmetry Breaking

Cited by in corpus (71)

• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Universality in polytope phase transitions and message passing algorithms
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
• Super sub-Nyquist single-pixel imaging by means of cake-cutting Hadamard basis sort
• SPARCs for Unsourced Random Access
• Sparse Attack Construction and State Estimation in the Smart Grid: Centralized and Distributed Models
• Statistical estimation and testing via the sorted L1 norm
• Belief propagation for joint sparse recovery
• Analysis of Regularized LS Reconstruction and Random Matrix Ensembles in Compressed Sensing
• Joint Activity Detection and Channel Estimation in Cell-Free Massive MIMO Networks with Massive Connectivity
• Reconstruction of Signals Drawn from a Gaussian Mixture from Noisy Compressive Measurements
• Generalized Approximate Message Passing for Estimation with Random Linear Mixing
• Applications of Large Random Matrices in Communications Engineering
• Approximate Message Passing Algorithm with Universal Denoising and Gaussian Mixture Learning
• Multi-Layer Bilinear Generalized Approximate Message Passing
• Message Passing Algorithms for Compressed Sensing: I. Motivation and Construction
• Signal Estimation with Additive Error Metrics in Compressed Sensing
• Estimation with Random Linear Mixing, Belief Propagation and Compressed Sensing
• Ultrafast Radiographic Imaging and Tracking: An overview of instruments, methods, data, and applications
• Performance Analysis of Joint Active User Detection and Channel Estimation for Massive Connectivity
• Recovering Joint Probability of Discrete Random Variables from Pairwise Marginals
• Optimal incorporation of sparsity information by weighted ${\ell }_1$ optimization
• Compressed Sensing under Matrix Uncertainty: Optimum Thresholds and Robust Approximate Message Passing
• Statistical-mechanical analysis of compressed sensing for Hamiltonian estimation of Ising spin glass
• Approximate Message Passing with Consistent Parameter Estimation and Applications to Sparse Learning
• Unsourced Multiuser Sparse Regression Codes achieve the Symmetric MAC Capacity
• RSB Decoupling Property of MAP Estimators
• Optimal Phase Transitions in Compressed Sensing
• Statistical mechanical analysis of sparse linear regression as a variable selection problem
• Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising
• Inference in Deep Networks in High Dimensions
• Near-Optimal Coding for Many-user Multiple Access Channels
• The Noise-Sensitivity Phase Transition in Compressed Sensing
• The LASSO risk for gaussian matrices
• Online compressed sensing
• Ranked Sparse Signal Support Detection
• Support Recovery with Sparsely Sampled Free Random Matrices
• Multi-Processor Approximate Message Passing Using Lossy Compression
• Fixed Points of Generalized Approximate Message Passing with Arbitrary Matrices
• Two-Part Reconstruction with Noisy-Sudocodes
• Inference for Generalized Linear Models via Alternating Directions and Bethe Free Energy Minimization
• Approximate Sparsity Pattern Recovery: Information-Theoretic Lower Bounds
• Recursive Compressed Sensing
• Statistical Physics and Information Theory Perspectives on Linear Inverse Problems
• Fundamental Limits of PhaseMax for Phase Retrieval: A Replica Analysis
• On Sparse Vector Recovery Performance in Structurally Orthogonal Matrices via LASSO
• Nonlinear Precoders for Massive MIMO Systems with General Constraints
• Statistical Mechanics Approach to Sparse Noise Denoising
• Compressed sensing with l0-norm: statistical physics analysis and algorithms for signal recovery
• Optimum GSSK Transmission in Massive MIMO Systems Using the Box-LASSO Decoder
• Unitary Precoding and Basis Dependency of MMSE Performance for Gaussian Erasure Channels
• Optimal Trade-offs in Multi-Processor Approximate Message Passing
• A signal recovery algorithm for sparse matrix based compressed sensing
• Sparsity Pattern Recovery in Bernoulli-Gaussian Signal Model
• Performance Analysis of Cell-Free Massive MIMO Systems with Massive Connectivity
• Mismatched Estimation in Large Linear Systems
• Wiener Filters in Gaussian Mixture Signal Estimation with Infinity-Norm Error
• Sparse Representation of White Gaussian Noise with Application to L0-Norm Decoding in Noisy Compressed Sensing
• Fault Identification via Non-parametric Belief Propagation
• Analysis of Sparse Representations Using Bi-Orthogonal Dictionaries
• Minimum Complexity Pursuit for Universal Compressed Sensing
• Ising Model Selection Using ${\ell }_1$-Regularized Linear Regression: A Statistical Mechanics Analysis
• Signal reconstruction in linear mixing systems with different error metrics
• Mixture Gaussian Signal Estimation with L_infty Error Metric
• RLS Recovery with Asymmetric Penalty: Fundamental Limits and Algorithmic Approaches
• Design and Analysis of a Greedy Pursuit for Distributed Compressed Sensing
• The Sampling Rate-Distortion Tradeoff for Sparsity Pattern Recovery in Compressed Sensing
• Replica Analysis for Generalized Linear Regression with IID Row Prior
• From compression to compressed sensing
• Nonlinear Function Estimation with Empirical Bayes and Approximate Message Passing