Phase transition in compressed sensing with horseshoe prior

In Bayesian statistics, horseshoe prior has attracted increasing attention as an approach to compressed sensing. By considering compressed sensing as a randomly correlated many-body problem, statistical mechanics methods can be used to analyze the problem. In this paper, the estimation accuracy of compressed sensing with the horseshoe prior is evaluated by the statistical mechanical methods of random systems. It is found that there exists a phase transition in signal recoverability in the plane of the number of observations and the number of nonzero signals, and that the recoverable phase is more extended than that using the well-known $l_1$ norm regularization.

Figure 1

Score function of $l_1$ norm regularization with $a=1$ (L1) and HS regularization with $\tau =1$ (HS). In both cases, the output is zero for small inputs. For the HS prior, the score function asymptotically approaches $y=x$ for sufficiently large inputs, whereas for $l_1$ norm regularization it is always $y\ne x$.

Figure 2

Phase boundaries of signal recoverability in CS for $l_1$ norm regularization (L1) and HS prior (HS). Complete recovery is possible in the region above the phase boundary.

Figure 3

False positive ratio (FPR) as a function of $\alpha$ in the signal recovery phase at $\rho =0.1$ for the $l_1$ norm regularization (L1) and HS prior (HS). Two vertical dotted lines represent the signal recovery bound for L1 and HS, respectively.

Figure 4

Mean-square error (MSE) as a function of the observed number density $\alpha$ for CS with $N=500,1000,2000$ and $\rho =0.1$ near the phase-transition point. For each $\alpha$, the median MSE for ${10}^3$ independent instances is plotted. The bars represent the quartile ranges of ${10}^3$ instances. The vertical dotted line represents the transition point obtained using the replica theory, ${\alpha }_c\left(0.1\right)=0.272\left(8\right)$.

Figure 5

Left: fraction of recovered instances as a function of $\alpha$ of CS with several sizes and $\rho =0.1$. Right: finite-size scaling plot of the fraction of recovered instances of CS with a scaling exponent $\mu =2.0$ in Eq. (36). The scaling analysis assumes the expected transition point ${\alpha }_c\left(0.1\right)=0.272\left(8\right)$ from the RS solution.