Phase diagram for the performance of (from left to right) mean field, mean field with noise learning, and Bethe in the \(\alpha–\rho\) plane using Gaussian noise with \(\Delta_0 = 10^{−8}\), \(N = 1024\), \(\alpha = M/N\), and \(\rho = K/N\). The measurements y are generated using matrix F with iid Gaussian elements of zero mean and unit variance. These numerical results were obtained using the function `fmin_l_bfgs_b` of the Scipy package to minimize the free energy (10) (left and center) and (24) (right). The lines denote (from bottom to top) the optimal threshold for noiseless compressed sensing (straight dashed line, e.g. [12]), the Bayesian AMP phase transition for a Gauss-Bernoulli signal (reached in the right panel, see [3]) and the Donoho-Tanner transition for convex l1 reconstruction [13]. Left: In the pure mean field case, reconstruction is always mediocre. Center: With noise learning, the performance greatly improves and, in particular, outperforms convex optimization. Right: The best results are obtained by the minimization of the Bethe free energy which gives the same results as the AMP algorithm.
Astract
We consider the variational free energy approach for compressed sensing. We first show that the naïve mean field approach performs remarkably well when coupled with a noise learning procedure. We also notice that it leads to the same equations as those used for iterative thresholding. We then discuss the Bethe free energy and how it corresponds to the fixed points of the approximate message passing algorithm. In both cases, we test numerically the direct optimization of the free energies as a converging sparse-estimation algorithm.
BibTeX
inproceedings{kmt2014,
Address = {Honolulu, HI},
Author = {Florent Krzakala and Andre Manoel and Eric W. Tramel and Lenka Zdeborov\'{a}},
Booktitle = {Proc. {IEEE} Int. Symp. on Information Theory (ISIT)},
Month = {July},
Pages = {1499--1503},
Title = {Variational Free Energies for Compressed Sensing},
Year = {2014}}
