We study the behavior of the Wasserstein-$2$ distance between discrete measures $\mu$ and $\nu$ in $\mathbb{R}^d$ when both measures are smoothed by small amounts of Gaussian noise. This procedure, known as Gaussian-smoothed optimal transport, has recently attracted attention as a statistically attractive alternative to the unregularized Wasserstein distance. We give precise bounds on the approximation properties of this proposal in the small noise regime, and establish the existence of a phase transition: we show that, if the optimal transport plan from $\mu$ to $\nu$ is unique and a perfect matching, there exists a critical threshold such that the difference between $W_2(\mu, \nu)$ and the Gaussian-smoothed OT distance $W_2(\mu \ast \mathcal{N}_\sigma, \nu\ast \mathcal{N}_\sigma)$ scales like $\exp(-c /\sigma^2)$ for $\sigma$ below the threshold, and scales like $\sigma$ above it. These results establish that for $\sigma$ sufficiently small, the smoothed Wasserstein distance approximates the unregularized distance exponentially well.

In compressed sensing, the restricted isometry property (RIP) on$M \times N$sensing matrices (where$M < N$) guarantees efficient reconstruction of sparse vectors. A matrix has the$(s,\delta)$-$\mathsf {RIP}$property if behaves as a$\delta $-approximate isometry on$s$-sparse vectors. It is well known that an$M\times N$matrix with i.i.d.$\mathcal {N}(0,1/M)$entries is$(s,\delta)$-$\mathsf {RIP}$with high probability as long as$s\lesssim \delta ^{2}~M/\log N$. On the other hand, most prior works aiming to deterministically construct$(s,\delta)$-$\mathsf {RIP}$matrices have failed when$s \gg \sqrt {M}$. An alternative way to find an RIP matrix could be to draw a random gaussian matrix and certify that it is indeed RIP. However, there is evidence that this certification task is computationally hard when$s \gg \sqrt {M}$, both in the worst case and the average case. In this paper, we investigate the exact average-case time complexity of certifying the RIP property for$M\times N$matrices with i.i.d.$\mathcal {N}(0,1/M)$entries, in the “possible but hard” regime$\sqrt {M} \ll s\lesssim M/\log N$. Based on analysis of the low-degree likelihood ratio, we give rigorous evidence that subexponential runtime$N^{\tilde \Omega (s^{2}/M)}$is required, demonstrating a smooth tradeoff between the maximum tolerated sparsity and the required computational power. This lower bound is essentially tight, matching the runtime of an existing algorithm due to Koiran and Zouzias. Our hardness result allows$\delta $to take any constant value in (0, 1), which captures the relevant regime for compressed sensing. This improves upon the existing average-case hardness result of Wanget al., which is limited to$\delta = o(1)$.