Reconciling "priors" & "priors" without prejudice?

Rémi Gribonval, Pierre MachartNeurIPS 2013 · OpenReview

In the realms of signal processing and machine learning, researchers tackling linear inverse problems have historically walked one of two distinct paths. The goal is typically to recover a hidden signal $z$ from noisy observations $y = Az + b$. To do this, one might choose the Bayesian path, assuming a prior distribution for $z$ and calculating the Minimum Mean Squared Error (MMSE) estimator. This approach is mathematically optimal for minimizing squared error but is notoriously grueling to compute. Alternatively, one might choose the Regularization path, solving an optimization problem that balances data fit with a penalty function (such as the Lasso). This is computationally efficient but often lacks a rigorous statistical justification.

A common misconception—often termed the "MAP quid pro quo"—suggests that these two paths are merely two sides of the same coin, specifically that using a penalty is equivalent to Maximum A Posteriori (MAP) estimation. However, recent research has shown this equivalence breaks down even in simple denoising scenarios. This paper, authored by Rémi Gribonval and Pierre Machart, provides a mathematical bridge between these two traditionally separate worlds, generalizing the connection to complex, real-world linear systems with "colored" (correlated) noise.

Theoretical Framework

As a purely theoretical work, the paper relies on mathematical proofs rather than empirical dataset benchmarks to extend previous denoising results to the general linear case. The authors employ several key analytical techniques:

  • Noise Whitening: The authors utilize a transformation to convert complex, correlated Gaussian noise into simple "white" noise, rendering the problem mathematically tractable.
  • Singular Value Decomposition (SVD): To handle the design matrix $A$ (which may be tall, wide, or square), they decompose it to simplify the relationship between the observation space and the signal space.
  • Functional Analysis: Through rigorous analysis, they derive the exact form of a "penalty function" $\phi$ that, when plugged into a standard optimization framework, yields the exact same result as the Bayesian MMSE estimator.

Key Insights and Results

The paper effectively dismantles the "MAP myth," proving that the relationship between priors and penalties is far more nuanced than simply taking the negative log of the prior.

MMSE is Always an Optimization

The most significant breakthrough (formalized in the paper's Theorem 2) is the proof that for any prior distribution, there exists a corresponding penalty function that turns the MMSE estimate into the solution of a penalized least-squares problem. The authors successfully generalize this link to any full-rank design matrix $A$ and any non-degenerate Gaussian noise.

The Suboptimality of Sparsity

This reconciliation reveals a surprising truth about popular sparse regularizers. The authors demonstrate that the penalty function associated with an MMSE estimator is always $C^\infty$ (infinitely smooth). Because sparsity-inducing penalties like the $\ell_1$ norm (Lasso) or $\ell_p$ pseudo-norms are non-smooth at the origin, they can never be true MMSE estimators. In practical terms, if a practitioner's goal is to achieve the lowest possible mean squared error, relying on a simple sparse regularizer is technically suboptimal.

The Role of "Evidence"

The properties of the derived penalty function—such as whether it is convex or separable—are directly tied to the "evidence," which is the marginal probability distribution of the observations $y$.

  • If the evidence is log-concave, the resulting optimization problem is convex.
  • If the evidence is multiplicatively separable, the penalty function is additively separable, which allows for the use of faster coordinate-descent algorithms.

Limitations and Future Directions

While the paper establishes a robust theoretical bridge, it operates within specific mathematical boundaries. The current framework relies heavily on the assumption of Gaussian noise and a quadratic loss function (least squares). The authors acknowledge that this "peculiar connection" requires deeper investigation. Additionally, the main theorem assumes the matrix $A$ has full rank; while under-determined cases are discussed, a universal theory for rank-deficient matrices remains an open challenge.

Looking forward, the authors suggest exploring non-quadratic losses (such as hinge or logistic loss) and non-Gaussian noise models (like Poisson noise) to determine if similar reconciliations exist in broader domains. They also propose developing a metric to quantify the "cost" of using a convex relaxation instead of the true, potentially non-convex, MMSE-equivalent penalty.

Summary updated

Abstract

There are two major routes to address linear inverse problems. Whereas regularization-based approaches build estimators as solutions of penalized regression optimization problems, Bayesian estimators rely on the posterior distribution of the unknown, given some assumed family of priors. While these may seem radically different approaches, recent results have shown that, in the context of additive white Gaussian denoising, the Bayesian conditional mean estimator is always the solution of a penalized regression problem. The contribution of this paper is twofold. First, we extend the additive white Gaussian denoising results to general linear inverse problems with colored Gaussian noise. Second, we characterize conditions under which the penalty function associated to the conditional mean estimator can satisfy certain popular properties such as convexity, separability, and smoothness. This sheds light on some tradeoff between computational efficiency and estimation accuracy in sparse regularization, and draws some connections between Bayesian estimation and proximal optimization.
BibTeX
@inproceedings{gribonval2013reconciling,
  author = {Rémi Gribonval and Pierre Machart},
  title = {{Reconciling "priors" \& "priors" without prejudice?}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=S1bt0PbuWH},
}
Figure