  When recovering an unknown signal from noisy measurements, the computational
difficulty of performing optimal Bayesian MMSE (minimum mean squared error)
inference often necessitates the use of maximum a posteriori (MAP) inference, a
special case of regularized M-estimation, as a surrogate. However, MAP is
suboptimal in high dimensions, when the number of unknown signal components is
similar to the number of measurements. In this work we demonstrate, when the
signal distribution and the likelihood function associated with the noise are
both log-concave, that optimal MMSE performance is asymptotically achievable
via another M-estimation procedure. This procedure involves minimizing convex
loss and regularizer functions that are nonlinearly smoothed versions of the
widely applied MAP optimization problem. Our findings provide a new heuristic
derivation and interpretation for recent optimal M-estimators found in the
setting of linear measurements and additive noise, and further extend these
results to nonlinear measurements with non-additive noise. We numerically
demonstrate superior performance of our optimal M-estimators relative to MAP.
Overall, at the heart of our work is the revelation of a remarkable equivalence
between two seemingly very different computational problems: namely that of
high dimensional Bayesian integration underlying MMSE inference, and high
dimensional convex optimization underlying M-estimation. In essence we show
that the former difficult integral may be computed by solving the latter,
simpler optimization problem.
