How many measurements are enough? Bayesian recovery in inverse problems with general distributions
Authors: Ben Adcock
Nick Huang
Venue: NeurIPS 2025 spotlight ()
Keywords: inverse problems
Bayesian recovery
generative priors
posterior sampling
compressed sensing
Primary area: deep_learning
TL;DR: We determine the sample complexity of Bayesian recovery for solving inverse problems with general prior, forward operator and noise distributions.

Abstract: We study the sample complexity of Bayesian recovery for solving inverse problems with general prior, forward operator and noise distributions. We consider posterior sampling according to an approximate prior $\mathcal{P}$, and establish sufficient conditions for stable and accurate recovery with high probability. Our main result is a non-asymptotic bound that shows that the sample complexity depends on (i) the intrinsic complexity of $\mathcal{P}$, quantified by its *approximate covering number*, and (ii) concentration bounds for the forward operator and noise distributions. As a key application, we specialize to generative priors, where $\mathcal{P}$ is the pushforward of a latent distribution via a Deep Neural Network (DNN). We show that the sample complexity scales log-linearly with the latent dimension $k$, thus establishing the efficacy of DNN-based priors. Generalizing existing results on deterministic (i.e., non-Bayesian) recovery for the important problem of random sampling with an orthogonal matrix $U$, we show how the sample complexity is determined by the *coherence* of $U$ with respect to the support of $\mathcal{P}$. Hence, we establish that coherence plays a fundamental role in Bayesian recovery as well. Overall, our framework unifies and extends prior work, providing rigorous guarantees for the sample complexity of solving Bayesian inverse problems with arbitrary distributions.

How many measurements are enough? Bayesian recovery in inverse problems with general distributions
Ben Adcock Department of Mathematics
Nick Huang Department of Mathematics
Simon Fraser University Canada
Simon Fraser University Canada
Abstract
We study the sample complexity of Bayesian recovery for solving inverse prob- lems with general prior, forward operator and noise distributions. We consider posterior sampling according to an approximate prior P. and establish sufficient conditions for stable and accurate recovery with high probability. Our main result is non-asymptotic bound that shows that the sample complexity depends (i) the intrinsic complexity P. quantified by its upproximate covering number, and (ii) concentration bounds for the forward operator and noise distributions. As key application, we specialize to generative priors, where P is the pushforward of a latent distribution via Deep Neural Network (DNN). We show that the sample complexity scales log-linearly with the latent dimension ke, thus establishing the efficacy of DNN-based priors. Generalizing existing results deterministic (i.e., non- con-Bayesian) recovery for the important problem of random sampling with an orthogonal matrix U, show how the sample complexity is determined by the herence of with respect to the support of P. Hence, we establish that coherence plays fundamental role in Bayesian recovery well. Overall, unifies and extends prior work, providing rigorous guarantees for the sample complexity of solving Bayesian inverse problems with arbitrary distributions.
framework
Introduction
Inverse problems are fundamental importance in science, engineering and industry. In a standard setting, the aim is to recover unknown vector (e.g., an signal image) x² E IR from measurements
Axx + e E R"
(1.1)
Here e E Thm is measurement noise and A E Rmxx, often termed the measurement matrix, represents the forwards operator. While simple, the discrete, linear problem [I.] is sufficient to model many important applications [5 64 68). It is common to solve [I.] using a Bayesian approach (see, e.g.. 30 7I),, where one assumes that x" drawn from some prior distribution R. However, in practice, R is never known exactly. Especially in modern settings that employ Deep Learning (DL) 33 is typical learn an approximate prior P and then recover x" from y by approximate posterior sampling, i.e., sampling å from the posterior PP-ly, A). An increasingly popular approach involves using generative models to learn (see, e.g., (1221 21 33 68 (0) and references therein).
major concern in many inverse problems is that the number of measurements m is highly limited, due physical constraints such time (e.g., in Magnetic Resonance Imaging (MRT), power (e.g., in portable sensors), money (e.g., seismic imaging), radiation exposure (c.g.. X-Ray CT), or other factors 5 64 68). Hence, one aims to recover well while keeping the number of measurements m as small as possible. With this in mind, in this work we address the following broad question: How many measurements suffice for stable and accurate recovery of R via approximate posterior
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

sampling â ~ P(-ly,A) A), and what are conditions on R. P and the distributions A and & of the measurement matrix A and noise e, respectively, that ensure this recovery?
1.1 Overview
In this work, we strive to answer to this question in the broadest possible terms, with a theoretical framework that allows for very general types of distributions. We now describe the corresponding conditions needed and present simplified versions of our main results.
(i) Closeness of the real and approximate distributions. We assume that Wp WR,R, P) is small for some 1 S p S oc, where Wp denotes the Wassertstein p-metric.
(ii) Low-complexity of P. Since m < n in many applications, to have any prospect for accurate recovery we need to impose that P (or equivalently R. in view of the previous assumption) has an inherent low complexity. Following [49). we quantify this in terms of its appraximate covering number , This is equal the minimum number of balls of radius 1) required to cover region of R" having P-measure at least 1 - ö. See Definition 2. for the full definition.
(iii) Concentration of A. We consider constants (t) = Clow (4; A, D) N 0 and Cupp(t) Cupp (1; A, D) 2 (see Definition 2.3 for the full definition) such that
PA~Alll |x S t||æ=|] S Clow(t),
PA~AlI/Ar|| 2 [||= S Cupp(t)
for all E D == Supp(P) supp(P) and > O. Here, and throughout this paper, we write S S- = {21 Z2. #1, 22 E 5} S R" for the difference set associated with a set S C R". We also write supp(P) for the support of the measure P (see | for the definition). Furthermore, write ||-I] for the -o-norm and I| for the -o-moom. If A is isotropic, i.e., EA~A
||x|
Vr E R", as is often the case in practice, these constants measure how fast ||az| 2 concentrates around its mean. Notice that this condition is imposed only D sPpp(P) supp(P), rather than the whole space R", As we see later, this is crucial in obtaining meaningful recovery guarantees.
Finally, in order to present a simplified result in this section, we now make several simplifying assumptions. Both of these will relaxed in our full result, Theorem
(iv) Gaussian noise. Specifically, we assume that & = =N, e I) for some o > 0.
(v) Bounded forwards operators. We assume that |A]] S 0 a.s. for A ~ A and some 0 > 0. Theorem 1.1 (Simplified main result). Let 1 S p S co, 0 < 8 < 1/4, e, > 0 and suppose that conditions (i)-(v) hold with W, (R, P) < <2mm)) and 2 2/61/v. Suppose that x² R, A ~ A,
e ~ E independently and ~ P(-y,, A), where y = Ax + e. Then, for any d 2 2,
PP [||x" - a|| Z (8d2 2)(11 + a z 5 Cov,, (P) (ion(1/d) + Cupp (d) + - m/ m/16
(1.2)
Note that in this and all subsequent results, the term on the left-hand side of (I.2 is the probability with respect to all variables, i.e., x" ~ R, A ~ A, e ~ E and à ~ P( A). Theorem 1.] is extremely general, in that it allows for essentially arbitrary (real and approximate) signal distributions R. and 'P and an essentially arbitrary distribution A for the forwards operator. In broad terms, bounds the probability that the error ||=- =|| of posterior sampling exceeds a constant times the noise level a plus an arbitrary parameter 77. It does so in terms of the approximate covering number (P)) which measures the complexity of the approximate distribution P, the concentration bounds Cjon and Cupp for A, which measure how much A elongates or shrinks a fixed vector, and an seponentially-decaying term e-m/16 which stems from the (Gaussian) noise. In particular, by analyzing these terms for different classes of distributions P and A, we can derive concrete bounds for various exemplar problems. We next describe two such problems.
1.2 Examples
We first consider A to be distribution of subgaussian random matrices. Here A ~ A if its entries are i..dd. subgaussian random variables with mean zero and variance 1/m (see Definition 3.4. Theorem 1.2 (Subgaussian measurement matrices, simplified). Consider the setup of Theorem 1.1 where At is a distribution of subgaussian random matrices. Then there a constant e 0 (depending on the subgaussian parameters B, x > 0; see Definition 3.4g such that
P ||| =11 2 34(n + o) S 6, whenever 2 [log(Cov,,, (P)) + log( 1/5)].
2

---

This theorem shows the efficacy of Bayesian recovery with subgaussian random matrices: namely, the sample complexity scales linearly in the distribution complexity, i.e. the log of the approximate we slightly refine and generalize this result.
covering number. Later in Theorem 3.5
Gaussian random matrices are very commonly studied, due to their amenability to analysis and tight theoretical bounds [5] 49) with Theorem 1.2 being a case in point. However, they are largely irrelevant to practical inverse problems, where physical constraints impose certain structures on the forwards operator distribution A 5 64 68).8). For instance, in MRI physical constraints mean that the measurements are samples of the Fourier transform of the image. This has motivated researchers to consider much more practically-relevar
distributions, in particular, so-called subsampled orthogonal x transforms (see, e.g., (5). Here U I=**" is a fixed orthogonal matrix for example, the matrix of the Discrete Fourier Transform (DFT) in the case of MRI and the distribution A is defined by randomly selecting m rows of U. See Definition 3.7 for the formal definition.
Theorem 1.3 (Subsampled orthogonal transforms, simplified). Consider the setup of Theorem 1.1 where A is a distribution of subsampled orthogonal matrices based on a matrix U. Then there is such that
universal constant
P 1||+=
=|| 2 34(n+ + o)] 6, whenever m 2 c- :-U; [log(Cov,,, (P)) + log(118)),
where D supp(P) supp(P) and p(U: D) is the coherence of relative to D, defined as
p(U: = nsup | || x x D. DDD x00
This result shows that similar stable and accurate recovery the Gaussian case can be achieved using subsampled orthogonal matrices, provided the number of measurements scales linearly with the coherence. We discuss this term further in $3.2 where we also present the full result, Theorem 3.9
In general. Theorems 1.2 and establish a key condition for successful Bayesian recovery in inverse problems, in each case relating the number of measurements m the intrinsic complexity log( Cov,,s(P) of P. It is therefore informative to see how this complexity behaves for cases of interest. As noted, it common to use a generative model learn P. This means that p Gt7, where G R + R" is Deep Neural Network (DNN) and y is some fixed probability measure on the latent space R Typically, 7 (). If G is L-Lipschitz, we show in Proposition 4.1 that
log(Cov,, (P)) O log (v + log((/8))/nn).
(1.3)
This scales log-linearly in the latent space dimension k; confirming the intrinsic low low-complexity of P. Combining (1.3) with Theorems 1.2 1.3 we see that posterior sampling achieves stable and accurate recovery, provided the number of measurements scales near-optimally with k, i.e., as O log(k) (k))...
Further, order to compare with deterministic settings such as classical compressed sensing, which concerns the recovery of s-sparse vectors, we also consider distributions P = Pa of s-sparse vectors. In this case, we show in Proposition 4.3 that
log(Cov.,, (P)) (og(/))) + logi (vs log(1/6))/n))
(1.4)
Hence measurements, up to log terms, are sufficient for recovery of approximately sparse vectors. This extends a classical result for deterministic compressed sensing to the Bayesian setting,
1.3 Significance
The significance of this work is as follows. See T.4 for additional discussion.
1. We provide the first results for Bayesian recovery with arbitrary real and approximate prior distributions R. P and forwards operator and noise distributions A. E.
2. Unlike much of the theory of Bayesian inverse problems, which is asymptotic in nature [12 30 71]. results non-asympooiic. They hold for arbitrary values of the various parameters within given ranges (e.g., the failure probability 6, the noise level a, the number of measurements m, and so forth).
3. For priors defined by Lipschitz generative DNNs, we establish the first result demonstrating that the sample complexity of Bayesian recovery depends log-linearly on the latent dimension & and logarithmically the Lipschitz constant.
3

---

4. For the important class of subsampled orthogonal transforms, we show that the sample complexity of Bayesian recovery depends on the coherence, thus resolving several key open problems in the literature (see next).
5. It is increasingly well-known that DL-bbaeed methods for inverse problems are susceptible to hallucinations and other undesirable effects [1T 18 25 29 40 47 60 66 79). This is major issue that may limit the uptake of these methods in safety-critical domains such as medical imaging [25 55 57 61 74 76 77). Our results provide theoretical guarantees for stable and accurate, and therefore show conditions under which hallucinations provably cannot occur. This is not only theoretically interesting, but it also has practical consequences in the development of robust DL
methods for inverse problems topic we intend to explore in future work.
1.4 Related work
Bayesian methods for inverse problems have become increasingly popular over the last several decades (T) J. and many state-of-the-art DL methods for inverse problems now follow a Bayesian
approach (see
12 21 46 46,56 64) and references therein). Learned priors, such as those stemming
from generative models, are now also increasingly used in applications
[ 22 28 33 38 46 48
51 53 54
64
68 70
80).
This work motivated in part by the (non-Bayesian) theory of generative models for solving inverse problems (see [2]33 43 44]444 68 80) and references therein). This was first developed in [22]. where compressed sensing techniques were used to show recovery guarantees for a Gaussian random matrix A when computing approximate solution to I.1) in the range Σ == ran(G) of a Lipschitz map G : I + R", typically assumed to be generative DNN. This is a deterministic approach. Besides the random forward operator and (potentially) random noise, it recovers fixed (i.e., nonrandom) underlying signal x² in a deterministic fashion with point estimator & that is obtained as a minimizer of the empirical (o-loss min.gr: ||Az yll². In particular, no information about the latent space distribution y is used. In this work, following, e.g., . [1] 21 ( 70) and others, we consider a Bayesian setting, where x² ~ R. is random and where we quantify the number of measurements that suffice for accurate and stable recovery via posterior sampling á ~ P(-l,,
Our work is a generalization of [49] which considered Bayesian recovery with Gaussian random matrices and standard Gaussian noise. We significantly extend [49] to allow for arbitrary distributions A and E for the forward operator and noise, respectively. A key technical step in doing this is the introduction of the concentration bounds Clow and Cupp- particular, these bounds are imposed only over the subset D supp(P) - supp(P)). This is unnecessary in the Gaussian case considered in Theorem 1.2. but crucial to obtain meaningful bounds in, for instance, the case of subsampled orthogonal transforms considered in Theorem 1.3 (see Remarks(3.] | and 3.10 for further discussion). As noted, this case is very relevant to applications. In particular, when is taken as a DFT matrix our work addresses open problems posed in [8]] $3] and (68] $ILFF) on recovery guarantees with Fourier measurements. We also derive bounds for the approximate covering number of distributions given by Lipschitz generative DNNs (see (.3) and Proposition 4. and distributions of sparse vectors (see (1.4) and Proposition 4.3 addressing an open problem posed in [49 $6). In particular, we demonstrate stable and accurate recovery in Bayesian sense with number of measurements that scales linearly in the model complexity, i.e., A in the former case and s in the latter case.
Recently (16 generalized the results of [22) in the non-Bayesian setting from Gaussian random matrices to subsampled orthogonal transforms. Theorem 1.3 provides a Bayesian analogue of this work, as discussed above, where we consider posterior sampling rather than a deterministic point estimator. We also extend the setup of [7]
I by allowing for general mcasurement distributions A and priors P. In particular, in 16 17 the quantity Σ, which is the deterministic analogue of the prior distribution P in our work, was assumed to be the range of a ReLU generative DNN, Like in [16), However, our proof techniques are
we make use of the concept of coherence (see Theorem completely different to those of 17].
Classical compressed sensing considers the recovery of approximately s-sparse vectors from [.1) However, has been extended to consider much more general types of low-complexity signal models, such as joint or block sparse vectors, tree sparse vectors, cosparse vectors and many others 4 13 13 23 36 73). However, most recovery guarantees for general model classes consider only Gaussian measurement matrices (see e.g., [13] 34)). Recently, 3 introduced a general

---

framework for compressed sensing that allows for general complexxt models Σ S R" contained within a finite union of inite-dimensional subspaces and arbitrary (random) measurement matrices. Our work is Bayesian analogue of this deterministic setting. Similar to [3]. key feature of our work that we consider arbitrary real and approximate signal distributions P, R. (analogous to arbitrary low-complexity models Σ) and arbitrary distributions A for the forwards operator. Unsurprisingly, number of the conditions in our main result, Theorem 1.1 namely, the low-complexity condition (ii) and concentration condition (iii) share similarities to those that ensure stable and accurate recovery in non- Bayesian compressed sensing. See Remarks 2.2 and 3.3 for further discussion. However, the proof techniques used in this work once more entirely different.
Finally, while the focus of this work is to establish guarantees for posterior sampling, we mention in passing related work on information caautioonthhortticalll theoretically optimal recovery methods. Methods such as Approximate Message Passing (AMP) [4] are well studied, and asymptotic information-thert
bounds for Gaussian random matrices are known [52]. AMP methods are fast point estimation algorithms, whereas we focus on campling-based methods and do not consider computational implementations (see for some further discussion). Note that information-theorrtie lower bounds
for posterior sampling have also been shown for the Gaussian case in [49].
Preliminaries
2.1 Notation
We now introduce some further notation. We let (x) {2 E R" ||2 - xll r and, when r we write B, := (0). Given set X C R", we write X = R"iX" for its complement. We also
write (X) = Uzex (x) for the r-neighbourhood of X.
Let (X,F, (b) be Borel probability space. We write supp(u) for its support, i.e., the smallest closed set A S X for which p(A) = Given probability spaces (X, F1, (2.F2,1)) 1/,, we write I = I Fp for the set of couplings, i.c., probability measures the product space (X x Y, (F @ F2)) whose marginals are and v, respectively. Given a cost function e: x - [0, oo) and S < co, the Wasserstein-p metric is defined
7EL ( Uxxy
cxz (x,.))d7(z,))) 1/P
W Wp(u,v) inf
If 0o, then (H,,,,)) = (esssupes y)). In this paper, unless stated otherwise, X Y R" and the cost function e the Euclidean distance.
2.2 Approximate covering numbers
As a measure of complexity of measures, we use the concept of approximate covering numbers as introduced in [49].
Definition 2.1 (Approximate covering number). Let (XFFP) be a probability space and 6, 2 0. The n, d-approximate covering number of is defined
A
Cov), = min & KEN: 3(rr)t C Supp(PP, P (Ü 2 1 21-5 -
This quantity measures how many balls of radius are required to cover at least 1 - 5 of the P- mass of IR.. See (49) for further discussion. Note that [49] does not require the centres x; of the approximate cover belong to supp(P). However, this is useful in our more general setting and presents no substantial restriction. At worst, this requirement changes 7) by a factor of 1/2.
Remark 2.2 (Relation to non-Bayesian compressed sensing) Note that when 5 = 0, the approxi- mate covering number Cov Cov,, (sv,,(()p((()) is just the classical covering number of the set supp(PP), i.e., the minimal number of balls of radius that cover supp(P). Classical covering numbers play a key role in (non-Bayesian) compressed sensing theory. Namely, the covering number of (the unit ball of) the model class Σ C IR" directly determines the number of measurements that suffice for stable and accurate recovery. See, e.g., (3]34). In the Bayesian setting, the approximate covering number plays the same role; see Theorem
5

---

2.3 Bounds for A and 3
Since our objective is to establish results that hold for arbitrary measurement and noise distributions A and E, we require several key definitions. These are variety of (concentration) bounds.
Definition 2.3 (Concentration bounds for A). Let A be a distribution on IR'xx,, 2 0 and D C IR..
Then lower concentration bound for any constant Claw Clow (t: A, D) 2 0 such that
PA~A Axll S |||>||]) - (to D): 4/2: D.
Similarly, upper concentration bound for A is any constant Cupp (t) Cupp A, 2 0 such that
FAmAill 2 +||=|} s Cupp A, A),, Vr D. Finally, given s (upper) absolute concentration bound for A any constant (s; such that
PA~A([IAr]) > 1) S (s, Vx E D, S..
Notice that if A is isotropic, i.e., B|| = ||=|| Va E R", then Clow and Cupp determine 2 for any fixed I D. To obtain desirable sample complexity estimates (e.g., Theorems 1.2 and 1.3) we need concentration bounds that decay exponentially in m. A crucial component of this analysis is considering concentration bounds some subset D (related to the support of PP), as, in general, one cannot expect fast concentration over the whole of R" See Remarks 3.2 and 3.10
how well ||Ax|] concentrates around its mean |
Definition 2.4 (Concentration bound for E). Let & be distribution in Ih and / > 0. Then (upper) concentration bound for & is any constant (tpp(1) = Dupo (t; )) 2 such that
{BB) ([eell 2 t) S (t:
Notice that this bound just measures the probability that the noise large. We also need the following concept, which estimates how much the density of & changes in r-neighbourhood of the origin when perturbed by an amount E.
Definition 2.5 (Density shift bounds for E). Let & be distribution in R.T with density Pe and E, 2 O. Then a density shift bound for is any constant Danitee, T) = Dahin +00) such that
2 (possibly (s, Ds,
Pε(u)= Desin((,,T;;)ppee Vu,UER ||]|| S T, |/u ol| Se.
3 Main results
We now present our main results. The first, an extension of Theorem 1.1 is general result that holds for arbitrary distributions R, P, and
Theorem 3.1. Let I p S co, 0 < 6 1/4, e,n,t 0, e, d > 1 and a 2 e/8l/v Let & be a distribution on m and R, P be distributions on IK" satisfying (R, < and
min(log Cov, n,8 (R), log Cov, (P)) <
(3.1)
for some l E N. Suppose that x² R, A A. E independently and à ~ P(-yy, A), where y = Ax ee, Then = P|l|2* +l z (c - () + o)] satisfies
p < 28 Cabsse/88// 1 A, D1) + (upp(do;E)
2V
Vc A.
VVoo
+ 2D (t= / EJe Clow
Ve i. + Cupp
2Dupp
2v
22
where
D1 = Be/ai (supp(P) (supp(R) - supp(P)
(3.2)
and
supp(P) - supp P
if attains the minimum in 3.1
D2 supp(P) supp(R) R)
(3.3)
otherwise

---

This theorem bounds the probability of unstable or inaccurate recovery in terms of the various parameters using the constants introduced in the previous section and the approximate covering numbers of R.33 P. This result is powerful in its generality, but as a consequence, rather opaque. In particular, since it considers arbitrary measurement and noise distributions, the number of measure- ments does not explicitly enter the bound. For typical distributions, dependence on is found in the concentration bounds Clow: Cupp: Dupp. as well as the terms Dshitt and Cabs. For instance, the former decay exponentially-fann in for the examples introduced in $1.2, and therefore compensate for the exponentially-lare scaling in in the main bound (see | for precise estimates, as well as the discussion in [3.1 3.2). Note that Theorem 3.1 also considers general noise distributions E. While Gaussian noise is arguably the most important example- and will be used in all our subsequent examples this additional generality comes at little cost in terms of the technicality of the proofs.
Remark 3.2 (The concentration bounds in Theorem 3.1 A particularly important facet of this
result, for the reasons discussed above, is that the various concentration bounds Cata. Clow and Cupp are taken over sets D1, D2 given by (3.2) and (3.3), respectively, and related to the support of P and R rather than the whole space R". We exploit this fact crucially later in Theorem 3.9
Remark 3.3 (Relation to non-Bayesian compressed sensing) The constants Claw and Cupp are similar, albeit not identical to similar conditions such as the Restricted Isometry Property (RIP) (see, e.g.: Chpt. 5)) Restricted Eigenvalue Condition (REC) [19 22 that appear in non-Bayesian compressed sensing. There, one considers a fixed model class Σ R such as the set Σ, of 8-sparse vectors or, as in [22]. the range ran(G) of a generative DNN. Conditions such as the RIP or REC impose that |Ar]] is concentrated around || for all x belonging to the difference set Σ - Σ. In Theorem 3.1 assuming attains the minimum in (3.1) D. there is a similar condition with Σ replaced by supp (P). Indeed, (2v2 Vc; A, D2) measures how small || A is in relation ||>||| and (Voo///(22/)) A, D2) measures how large ||x]|| is in relation to |>]||
3.1 Example: Subgaussian random matrices with Gaussian noise
We now apply this thcorem the first example introduced in 1T.2 Recall that random variable X on is subgaussian with parumeters B, x if [[ 2 I) S -et
-tt for all / 0.
Definition 3.4 (Subgaussian random matrix). A random matrix A E R is subgaussian with parameters B, K > 0 if = Vm A, where the entries of À are independent mean-zero sugaussian random variables with variance and the same subgaussian parameters B, k.
Note that 1//m is scaling factor that ensures that A is isotropic, i.e., B||Ad||- = ||0|| Vo R
Theorem 3.5. Let 1 S p xc. 0 < 1/4, E, > 0 and a 2 e/8V/, Let NO0 o² I) and A be distribution of subgaussian random matrices with parameters 3, > 0. Let R. be distributions on R and suppose that x² R, A.
mr
E independently and & P(-ly, A), where y = Ax" + e. Then there is constant c(33, x) > 0 depending on B, K only such that
FIlx" - a|| 34(n + 55
provided W, WR(RP,) Se/c(B, x) and
m M c(3, k) [min(log so Cov,, (P)) + log(1/6)).
(3.4)
This theorem is derived from Theorem 3.1 by showing that the various concentration bounds are exponentially small in for subgaussian random matrices (see $B). It is direct generalization of [49], which considered the Gaussian case only. It shows that subgaussian random matrices are near-optimal for Bayesian recovery, in the sense that scales linearly with the log of the approximate covering number (.4). We estimate these covering numbers for several key cases in $4
It is worth at this stage discussing how 3.4) behaves with respect to the various parameters. First, suppose that 7) decreases so that the emror bound becomes smaller. Then Cov,,,(.)) increases, meaning, as expected, that more measurements are required to meet (3.4). Second, suppose that 8 decreases, so that the failure probability shrinks. Then Cov,,6(-) and log(1/5) both increase, meaning, once again, that more measurements needed for (3.4) to hold. Both behaviours are expected.
7

---

Remark 3.6 (Relation to Johnson-Lindeestraaus Suppose that P = R is sum of d Diracs located X "GI....,Zzl. C R Since the matrix Rm*= is a linear dimensioonalit-rrduuen map, the Johnsoon-Lindensreann m = ((logd)). In this setting, preserving the distances X is equivalent identify the mode from which signal is drawn when observing its measurements. In agreement with this argument, Theorem 3.5 also predicts recovery from roughly m = (llg((d) measurements.
Lemma states that distances in X are preserved under A if and only
being able to stably
3.2 Example: Randomly-suusamplee orthogonal transforms with Gaussian noise
As discussed, subgaussian random matrices are largely impractical. We now consider the more practical case of subsampled orthogonal transforms.
Definition 3.7
orthogonal transform). Let U E R be orthogonal (i.e., U U- UUT I) and write Wi...., un Rn for its rows. Let Xi...., X, wi.id. Ber(m/n) be independent Bernoulli random variables with I(X; = 1) = m/n n and P(X, = 0) = 1 - m//n. /n. Then
1-m/nn.
define distribution A as follows. We say that A ~ A if
T2
A
where (i1,...,,y)
3 S (1. (I.......) n is the set of indices for which X; 1.
The factor v /n/m ensures that E(AT A) = Note that the number of measurements in this model
itself random variable, with B(g) m. However, q concentrates exponentially around its mean.
Definition 3.8. Let U E R=** and D C R The coherence of U relative to D
MUU D) n sup {IV00]
D, x + 0).
Coherence is well-known concept in classical compressed sensing with sparse vectors. Definition 3.8 a generalization that allows for arbitrary model classes D. This definition is similar that of [6]. which considered non -on-aaasiann compressed sensing with generative models. It is also related to the more general concept variation introduced in (3].
Theorem 3.9. Let & p xc, 0 < 6 I 1/4, E. n > O and o 2/ Let E = N0, a²
m I) and orthogonal matrices based a matrix U. Let R,
A be distribution of be distributions on R" and suppose that x² ~ R. A ~ A, E E independently and ~ Al),, where y Ax" Then there is universal constant <> 0 such that
PP "1|x=* - +l| 2 34(1 + a)] & 6,
provided W, WP(R, P) S (/(2///2) mm) and m 2 ((U D)- [log( Cov sov,,,(()) + log(116)) where D = supp(P) - suppp(P). (3.5)
This theorem is a Bayesian analogue of the deterministic results shown in 16) In 3 16 the measurement conditions scale linearly with μiU; D), where D) = Σ Σ and Σ R" Is the low- complexity model class. Similarly, the number of measurements (3.) scales linearly with respect to the coherence relative to D sPpp(P) supp(P),, which, as discussed in Remark 3.3 plays the role of the low-complexity model class in the Bayesian setting. Note that the measurement condition 3.5) involves the approximate distribution P only. This is relevant, since the quantities y(U; D) and Cov (P) can be estimated either numerically or analytically various cases, such as when P is given by generative model. Indeed, we estimate Cov,,a(P) analytically for Lipschitz generative models in Proposition 4.1 below. The coherence D) was estimated analytically in [16] for ReLU DNNs with random weights (see Remark beloww.. It can also be estimated numerically for more general types of generative models [2 16). Overall, by estimating these quantities, one can use to gauge how well one can recover with given P. Note that this may not be possible if (35 involved R as well, since this distribution is typically unknown.
3.5
In classical compressed sensing, coherence determines the sample complexity of recovering sparse (26). similar argument can be made in n. However, we are particularly interested in cases where U(U;; D) & n, in which case (35) may be significantly smaller than the ambient dimension n. We discuss this in the context of several examples in the next section.
vectors from andooll-ssubsanpledd orthogonal transforms
the Bayesian setting. Notice that μ(U; D) < p(U;
8

---

Remark 3.10 (Concentration over subsets) Theorem 3.9 illustrates why it is important that Theo- rem B.J involves concentration bounds over subsets of R To derive Theorem 3.9 from Theorem B.] m/ R",, then, since (u; ] = n, this would have lead to an undesirable measurement condition of the form m (n) scaling linearly in the ambient dimension n.
(see S we show exponentially-fas concentration in m/ (U; D). Had we considered the whole of
4
Covering number and sample complexity estimates
We conclude by applying our results to two different types of approximate prior distributions.
4.1 Generative DNNs
Proposition 4.1 (Approximate covering number for a Lipschitz pushforward of a Gaussian measure). Let G IR + R= be Lipschitz with constant L 2 i.., [[G(()) G(z)ll S L|| 2/I. Vz, 2 IR., and define p Git, where 7 = (0, T) is the standard normal distribution on RR.. Then
(og(Cov,,6(P)) S k log 1 2VRL
11- V
log (1/))
(4.1)
"
This result shows that P has low complexity, since log(Cov,,, n (P)) scales log-linearly in k. Combined with Theorem 3.5 it shows that accurate and stable Bayesian recovery with such a prior with a sample complexity that near-optimal in the latent dimension k. i.e. O(k log(k)).
Notice that L only appears logarithmically in (4.1). While it is not the main focus of this work, we
note that Lipschitz constants of DNNs have been studied quite extensively [37 (77 72 75). Moreover,
is also possible to design and train DNNs with small Lipschitz. constants 59
Remark 4.2 (Quadratic bottleneck and high coherence) In Theorem 3.9 the measurement con- dition 3.5) also depends on the coherence. This quantity has been considered in (16) for the case of ReLU DNNs. In particular, a ReLU DNN G IRA + IR" has random weights drawn from a standard normal distribution, then its coherence UU; D) scales like (kk) up to log factors [16) Thm. 3]. Combining this with Theorem 3.9 and Proposition 4.1 we see that the overall sample complexity for Bayesian recovery scales like O log(k)) in this case. This is worse than the subgaussian case, where there is no coherence factor and the sample complexity, as noted above, O log():). Such quadratic bottleneck also arises in the non- Bayesian setting [16]. Its removal is an open problem (see $ Note that the coherence is also not guaranteed to be small for general (in particular, trained) DNNs. However. [16] also discuss strategies for training generative models to have small coherence. Numerically, they show that generative models with smaller coherence achieve better recovery from the same number of measurements than those with larger coherence.
4.2 Distributions of sparse vectors
Let E [I,....n] n). We define a distribution P Ps of s-sparse vectors in R² as follows. To draw P, we first choose a support set S C (1.....1) |S| uniformly at random amongst all possible (*) such subsets. We then define x; = 0, i & S, and for each i E S we draw randomly and independently from (0, 1). Note that there are other ways to define distributions of sparse vectors, which can be analyzed similarly. However, for brevity only consider the above setup.
Proposition 4.3 (Approximate covering number for distributions of sparse vectors). Let P = Pa be distribution of s-sparse vectors in R=.. Then
Log(Cov,,, (Cov.,,, S log
en
+ log
1+
2/8 "
1 [
2 log (1/8)
(4.2)
As in the previous case, we deduce Bayesian recovery from O(s log(n/ (m/s)] subgaussian measurements, i... optima, log-linear sample complexity. In the case of randomly Soummll-uubamplle orthogonal matrices, we also need to consider the coherence. For = P, as above, one can easily show that
(UU; (ssuup(PP.) - supp(P.)) S (U),
where μa (U) = n max |u,51
(4.3)

---

The term (U) is often referred to as the coherence of U (see, e.g., Defn. 5.8] or (26)) Notice that (U) 1 for DFT matrices, which is one reason why subsampled Fourier transforms are particularly effective in (non-Baye Ban-Bayysiin) compressed sensing. Our work implies as similar conclusion the Bayesian setting: indeed, substituting (4.2) and (4.3) into (3.5) we immediately deduce that the measurement condition for Bayesian recovery with Pa behaves like = Oss²) up to log terms.
Remark 4.4 (Quadratic bottleneck) Once more we witness a quadratic bottleneck. In the non- Bayesian setting, one can show stable and accurate recovery of sparse vectors from (s) measure- ments, up to log terms (see, e.g., [5] Cor. 13.15]). However, this requires specialized theoretical techniques that heavily leverage the structure of the set of sparse vectors. In the setting this paper, the bottleneck arises from the generality of the approach considered in this work: specifically, the fact that our main results hold for arbitrary probability distributions P.
Limitations and future work
We end by discussing number of limitations and avenues for future work. First, although our main result Theorem 3.1 is very general, we have only applied it to a number of different cases, such Lipschitz pushforward measures and Gaussian random matrices or subsampled orthogonal transforms. We believe many other important problems can be studied as corollaries of our main results. This includes sampling with heavy-tailed vectors [50), sampling with random convolutions [67]. multi-sensor acquisition problems (27), generative models augmented with sparse deviations B2]. block sampling 33 20 with applications practical MRI acquisition, sparse tomography (8) deconvolution and inverse source problems (9]. We believe our framework can also be applied to various types of Gaussann noise, as well as problems involving gparsely-corrupted measurements [50]. We are actively investigating applying our framework to these problems.
Second, noted in Remarks 4.2 and 4.4 there is quadratic bottleneck when considering subsampled orthogonal transforms. In the non-Bayesian case, this can be overcome in the case of (structured) sparse models using more technical arguments (3]. We believe similar ideas could also be exploited in the Bayesian setting. On a related note, both [16 22 consider ReLU generative models in the non-Bayesian setting, and derive measurement conditions that do not involve the Lipschitz constant L of the DNN. It is unclear whether analogous results can be established in the Bayesian setting.
Third, our main result involves the density shift bound (Definition 2.5 In particular, the noise distribution should have a density. This rather unpleasant technical assumption stems from Lemma C.6 which is a key step in proving the main result, Theorem 3.1 This lemma allows one to replace the 'real' distribution R. in the probability term in Theorem 3.1 by the approximate distribution P. This is done in order to align the prior and the posterior, which necessary for the subsequent steps of the proof of Theorem 3.1 It would be interesting to see if this assumption on the noise could be removed through a refined analysis.
Fourth, as noted in (16), the coherence u(U;; D) arising in Theorem 3.9 may be high. In the non- Bayesian setting, this has been addressed in 23 17 by using nonuniform probability distribution for drawing rows of U, with probabilities given in terms of so-called local coherences of U with relative to D. As shown therein, this can lead to significant performance gains over sampling uniformly at random. We believe a similar approach can be considered in the Bayesian setting as a consequence of our general framework. We intend explore this in future work.
Finally, our results in this paper are theoretical, and strive to study the sample complexity of Bayesian recovery. We do not address the practical problem of sampling from the posterior. This is a key computational challenge in Bayesian inverse problems [2). However, efficient techniques for doing this are emerging. See, e.g.. [48 54 70 and references therein. We believe an advantage of our results their independence from the choice of posterior sampling algorithm, whose analysis can therefore be performed separately. This is an interesting problem intend to examine in the future. In future work we also intend present numerical experiments for various practical settings that further support the theory developed in this paper.
10

---

Acknowledgments and Disclosure of Funding
BA acknowledges the support of the Natural Sciences and Engineering Research Council of Canada of Canada (NSERC) through grant KGPPN-20221611665 NH acknowledges support from an NSERC Canada Graduate Scholarship. Both authors would like thank Paul Tupper and Weiran Sun for helpful comments and feedback.
References
[1] A. Aali, M. Arvinte. S. Kumar, and Tamir. Solving inverse problems with score-based generative priors learned from noisy data. In 2023 57th Asilomar Conference on Signals, Systems, and Computers, pages 837-843, 2023.
[2] B. Adcock, J. M. Cardenas, and N. Dexter. CS4ML: A general framework for active learning with arbitrary data based on Christoffel functions. In A. Oh, Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 19990-20037, 2023.
[3] B. Adeock, J. M. Cardenas, and Dexter. A unified framework for learning with nonlinear model classes from arbitrary linear samples. In International Conference on Machine Learning. 2024.
[4] B. Adcock, A. Gelb, G. Song, and Y. Sui. Joint sparse recovery based on variances. SIAM J. Sci. Comput., A1(1):A246-A28,, 2019.
[5] B. Adcock and A. C. Hansen. Compressive Imaging: Structure, Sampling, Learning. Cambridge University Press, Cambridge, UK, 2021.
[6] B. Adcock, A. C. Hansen, C. Poon. and B. Roman. Breaking the coherence barrier: new theory for compressed sensing. Forum Math. Sigma, 5:e4, 2017.
[7] Adler and O. Öktem. Deep Bayesian inversion. In Data-Driven Models in Inverse Problems, pages 359-412. De Gruyter, Berlin, Boston, 2025.
[8] G. S. Alberti, A. Felisi, M. Santacesaria, and S. I. Trapasso. Compressed sensing for inverse problems and the sample complexity of the sparse Radon transform. J. Eur. Math. Soc. (in press), 2025.
[9] G. Alberti, A. Felisi, M. Santacesaria, and S. I. Trapasso. Compressed sensing for inverse problems ii: applications to deconvolution, source recovery, and MRI. arXiv:2501.0121 .,.50,,,199, 2025.
[10] L. Ambrosio, E. Brué, and D. Semola. Lectures on Optimal Transport. UNITEXT. Springer, Cham, Switzerland, 2nd edition, 2024.
[11] V. Antun, F. Renna, C. Poon, B. Adcock, and A. C. Hansen. On instabilities of deep learning in image reconstruction and the potential costs Al. Proc. Natl, Acad. Sci. USA, 117(48)300088- 30095, 2020.
[12] S. Arridge, P. Maass, O. Öktem, and C.-B. Schönlieh. Solving inverse problems using data- driven models. Acta Numer, 28:1-174, 2019.
[13] R. G. Baraniuk, V. Cevher, M. F. Duarte, and C. Hedge. Model-based compressive sensing. IEEE Trans. Inform. Theory, 56(4): 2010.
[14] M. Bayati and A. Montanari. The dynamics of message passing dense graphs, with applica- tions to compressed sensing. IEEE Trans. Inform. Theory, 57(2):764-785, 2011.
[15] C. Belthangady and L. A. Royer. Applications, promises, and pitfalls of deep learning for fluorescence image reconstruction. Nature methods, 16(12):1215-12)
2019.
[16] A. Berk, S. Brugiapaglia, B. Joshi, Y. Plan, M. Scott, and O. Yilmaz. A coherence parameter characterizing generative compressed sensing with fourier measurements. IEEE J. Sel. Areas Inf. Theory, 333:5002-51, 2022.
[17] A. Berk, S. Brugiapaglia, Y. Plan, M. Scott, X. Sheng, and O. Yilmaz. Model-adapted Fourier sampling for generative compressed sensing. In NewrlPS 2023 Workshop on Deep Learning and Inverse Problems, 2023.
[18] Bhadra, V. A. Kelkar, J. Brooks, and M. A. Anastasio. On hallucinations in tomographic image reconstruction. IEEE Trans. Med. Imaging, 40(11):3249-33 32660 2021.
11

---

[19] P. J. Bickel, Y. Ritov, and A. B. Tsybakov. Simultaneous analysis of Lasso and Dantzig selector. Ann. Statist., 37(4):775--1732 2009.
[20] J. Bigot, C. Boyer, and P. Weiss. An analysis of block sampling strategies in compressed sensing. IEEE Trans. Inform. Theory, 62(4):2125-2139) 2016.
[21] P. Bohra, Pham, T.-A. Dong, and M. Unser. Bayesian inversion for nonlinear imaging models using deep generative priors. IEEE Trans. Compul. Imag., 1377-1124,, 2023.
[22] A. Bora, A. Jalal, E. Price, and A. G. Dimakis. Compressed sensing using generative models. In International Conference on Machine Learning, pages 537-546, 2017.
[23] A. Bourrier, M. E. Davies, T. Peleg, P. Pérez, and R. Gribonval. Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems. IEEE Trans. Inform. Theory, 60(12):7928-77) 7946,99666222 2014.
[24] C. Boyer, J. Bigot, and P. Weiss. Compressed sensing with structured sparsity and structured acquisition. Appl. Comput. Harmon. Anal., 46(2):122-350, 2019.
[25] M. Burger and T. Roith. Learning in image reconstruction: cautionary tale. SIAM News, 57(08), Oct 2024.
[26] E. J. Candès and Y. Plan. A probabilistic and RIPless theory of compressed sensing. IEEE Trans. Inform. Theory, 57(11):7235-72) 12544,347725, 2011.
[27] I.-Y. Chun and B. Adcock. Compressed sensing and parallel acquisition. IEEE Trans. Inform. Theory, 63(8):4860- 48820 2017.
[28] H. Chung and J. C. Ye. Score-based diffusion models for accelerated mri. Medical Image Analysis, 80: 10240, 2022.
[29] M. Colbrook, V. Antun, and A. C. Hansen. The difficulty of computing stable and accurate neural networks: On the barriers of deep learning and smale's 18th problem. Proc. Natl. Acad. Sci. USA, 119 (1(1))221771111 19, 2022.
[30] M. Dashti and A. M. Stuart. The bayesian approach inverse problems. In R. Ghanem et al., editor, Handbook of Uncertainty Quantification. Springer, 2017.
[31] M. A. Davenport, M. F. Duarte, Y. C. Eldar, and G. Kutyniok. Introduction to compressed sensing. In Y. C. Eldar and G. Kutyniok, editors. Compressed Sensing: Theory and Applications, pages 1-64. Cambridge University Press, Cambridge, UK, 2012.
[32] M. Dhar, A. Grover, and S. Ermon. Modeling sparse deviations for compressed sensing using generative models. In International Conference on Machine Learning, pages 1214-1223. PMIR, 2018
[33] A. G. Dimakis. Deep generative models and inverse problems. In P. Grohs and G. Kutyniok, ed- itors, Mathematical Aspects of Deep Learning, chapter 9, pages 400-421, Cambridge University Press, Cambridge, UK, 2022.
[34] S. Dirksen. Dimensionality reduction with subgaussian matrices: unified theory. Found. Comput. Math., 16: 1667-1133, 2016.
[35] D. L. Donoho, Maleki, and A. Montanari. Pesssag-ppassing algorithms for compressed sensing. Proc. Natl. Acad. Sci. USA, (86445): 2009.
[36] M. F. Duarte and Y. C. Eldar. Structured compressed sensing: from theory to applications. IEEE Trans. Signal Process., 5909):053-44085 201
[37] M. Fazlyab, A. Robey, H. Hassani, M. Morari, and G. Pappas. Efficient and accurate estimation of Lipschitz constants for deep neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 33. Curran Associates, Inc., 2019.
[38] B. T. Feng. J. Smith, M. Rubinstein, H. Chang, K. L. Bouman, and W. T. Freeman. Score-based diffusion models as principled priors for inverse imaging. In 2023 IEEE/CVF International Conference on Computer Vision (ICCV), pages 10486-10497, 2023.
[39] S. Foucart and H. Rauhut. Mathematical Introduction Compressive Sensing. Appl. Numer. Harmon. Anal. Birkhäuser, New York, NY, 2013.
[40] M. Genzel, Macdonald, and M. Marz. Solving inverse problems with deep neural networks robustness included? IEEE Trans. Pattern Anal. Mach. Intell., 4199):1119-1134 2023.
12

---

[41] C. R. Givens and R. M. Shortt. A class of Wasserstein metrics for probability distributions. Michigan Math. J. 31(2):331-240, 1984.
[42] N. M. Gottschlingg V. Antun, A. C. Hansen, and Adcock. The troublesome kernel on hallucinations, no free lunches and the accuracy-stabile trade-off in inverse problems. SIAM Rev., 67(1):33-104, 2025.
[43] Hand, O. Leong, and V. Voroninski. Phase retrieval under a generative prior. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[44] Hand and V. Voroninski. Global guarantces for enforeing deep generative priors by empirical risk. In S. Bubeck, V. Perchet, and P. Rigollet, editors, Proceedings of the Thirty-First Confer- ence on Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 970-978, PMLR, 2018.
[45] D. P. Hoffman, I. Slavitt, and C. A. Fitzpatrick. The promise and peril of deep learning in microscopy. Nature Methods, 18(2):131-1322 2021.
[46] M. Holden, M. Pereyra, and K. Zygalakis. Bayesian imaging with data-driven priors encoded by neural networks. SIAM J. Imaging Sci., 15(2):892-922 2022.
[47] Y. Huang, T. Würfl, K. Breininger, L. Liu, G. Lauritsch, and A. Maier. Some investigations on robustness of deep learning limited angle tomography. In International Conference on Medical Image Computing and Computer-Assister Intervention, pages 145-153, 2018.
[48] A. Jalal, M. Arvinte, G. Daras, E. Price, A. G. Dimakis, and J. Tamir. Robust compressed sensing mri with deep generative priors. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 14938-14954 Curran Associates, Inc., 2021.
[49] A. Jalal, S. Karmalkar, A. Dimakis, and E. Price. Instance-optimal compressed sensing via posterior sampling. In 38th International Conference on Machine Learning, pages 4709-4720, 2021.
[50] A. Jalal, L. Liu, G. Dimakis, and C. Caramanis. Robust compressed sensing using generative models. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 713-727. Curran Associates, Inc., 2020.
[51] Z. Kadkhodaie and E. Simoncelli. Stochastic solutions for linear inverse problems using the prior implicit in a denoiser. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neurul Information Processing Systems, volume 34, pages 13242-13254. Curran Associates, Inc., 2021.
[52] A. Karan, K. Shah, S. Chen, and Y. C. Eldar. Unrolled denoising networks provably learn to perform optimal Bayesian inference. In A. Globerson, I. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 135264-135298. Curran Associates, Inc., 2024.
[53] B. Kawar, M. Flad, S. Ermon, and J. Song. Denoising diffusion restoration models. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 23593-23606. Curran Associates, Inc., 2022.
[54] B. Kawar, G. Vaksman, and M. Elad, SNIPS: solving noisy inverse problems stochastically. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 21757-21769. Curran Associates, Inc., 2021.
[55] R. F. Laine, I. Arganda-Carreraa R. Henriques, and G. Jacquemet. Avoiding replication crisis deep-learning-bant based bioimage analysis. Nature Methods, 18(10):116-11 2021.
[56] R. Laumont, V. D. Bortoli, A. Almansa, Delon, A. Durmus, and M. Pereyra. Bayesian imaging using plug & play priors: When langevin meets tweedie. SIAM J. Imaging Sci., 15(2):701-737, 2022.
[57] X. Liu, B. Glocker, M. M. McCradden, M. Ghassemi, A. K. Denniston, and L. Oakden-Rayner. The medical algorithmic audit. The Lancet Digital Health, 4(5):c384-3377 2022.
13

---

[58] G. Luo, M. Blumenthal, M. Heide, and M. Uecker. Bayesian MRI reconstruction with joint uncertainty estimation using diffusion models. Magn. Reson. Med., 90(1):295-311, 202,
[59] T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida. Spectral normalization for generative adversarial networks. In International Conference on Learning Representations, 2018.
[60] N. Morshuis, S. Gatidis, M. Hein, and C. F. Baumgartner. Adversarial robustness of MR image reconstruction under realistic perturbations. arXiv:2208, 00222000,3111.. 161, 2022.
[61] Matthew J Muckley, Bruno Riemenschneider, Alireza Radmanesh, Sunwoo Kim, Geunu Jeong. Jingyu Ko. Yohan Jun, Hyungseob Shin, Dosik Hwang, Mahmoud Mostapha, et al. Results of the 2020 fastMRI challenge for machine learning MR image reconstruction. IEEE Trans, Med. Imaging, 2021.
[62] M. Neyra-Nesterenko and B. Adcock. NESTANe1S: stable, accurate and efficient neural networks for analysis-sparse inverse problems. Sampl. Theory Signal Process. Data Anal., 21:4, 2023.
[63] C. R. Noordman, D. Yakar, J. Bosma, F. F. J. Simonis, and H. Huisman. Complexities of deep learning-based undersampled MR image reconstruction. Eur. Radiol. Exp., 7:58, 2023.
[64] G. Ongie, A. Jalal, C. A. Metzler, R. G. Baraniuk, A. G. Dimakis, and R. Willett. Deep learning techniques for inverse problems in imaging. IEEE J. Sel. Areas Inf. Theory, 1(1):39 56, 2020.
[65] A. Raj. Y. Bresler, and B. Li. Improving robustness of deep-learning-based image reconstruction. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 7932-7942. PMLR, 13-18 Jul 2020.
[66] A. J. Reader and B. Pan. AI for PET image reconstruction. Brit. J. Radiol., 96(1150)22020022, 2023.
[67] Romberg. Compressive sensing by random convolution. SIAM J. Imaging Sci., 204):1098-
1 128, 2009.
[68] Scarlett, R. Heckel, M. R. D. Rodrigues, P. Hand, and Y. C. Eldar. Theoretical perspectives on deep learning methods in inverse problems. IEEE J. Sel. Areas Inf. Theory, 3(3):333 453, 2022.
[69] V. Shah and C. Hegde. Solving linear inverse problems using GAN priors: An algorithm with provable guarantees. In 2018 IEEE international conference on Acoustics, Speech and Signal Processing (ICASSP) conference on acoustics, speech and signal processing (ICASSP), pages 4609 4613. IEEE, 2018
[70] Y. Song, L. Shen, L. Xing, and S. Ermon. Solving inverse problems in medical imaging with score-based generative models. In International Conference on Learning Representations, 2022.
[71] A. M. Stuart. Inverse problems: Bayesian perspective. Acta Numer., 19:451-559, 2010.
[72] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, J. Ian Goodfellow, and R. Fergus. Intriguing properties of neural networks. In Proceedings of the International Conference on Learning Representationss 2014.
[73] Y. Traonmilin and R. Gribonval. Stable recovery of low-dimensional cones in Hilbert spaces: one RIP to rule them all. Appl. Comput. Harmon. Anal., 45(1):170-205,, 2018.
[74] G. Varoquaux and V. Cheplygina. Machine learning for medical imaging: methodological failures and recommendations for the future. NPJ digital medicine, 5(1):1-8, 2022.
[75] A. Vimmaux and K. Scaman. Lipschitz regularity of deep neural networks: amalysis and efficient estimation. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- DesaaBiaachh,, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[76] E. Wu, K. Wu, R. Daneshjou, D. Ouyang, D. E. Ho, and J. Zou. How medical AI devices are evaluated: limitations and recommendations from an analysis of FDA approvals. Nature Medicine, 27(4):582-584, 2021.
[77] T. Yu, T. Hilbert, G. G. Piredda, A. Joseph, G. Bonanno, S. Zenkhri, P. Omoumi, M. B. Cuadra, Kober, et al. Validation and generalizability of sele-super image reconstruction methods for undersampled MRI. 220.:22201.2235,, 2022.
E. J. Canales-Rodrígure
[78] M. Zach, F. Knoll, and T. Pock. Stable deep MRI reconstructions using generative priors. IEEE Trans. Med. Imag. 42111)3887733811 2023.
14

---

[79] C. Zhang, J. Jia, B. Yaman, S. Moeller, S. Liu, M. Hong, and M. Akçakaya. Instabilities in conventional multi-coil MRI reconstruction with small adversarial perturbations. In 2021 55th Asilomar Conference on Signals, Systems, and Computers, pages 895-899, 2021.
[80] Z. Zhao, J. C. Ye, and Y. Bresler. Generative models for inverse imaging problems: from mathematical foundations to physics-driven applications. IEEE Signal Process. Mag., 40(1):148-
163, 2023.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We thoroughly discuss the main claims made in the abstract and introduction and the necessary assumptions show them. Our main theoretical contributions directly address these claims. We also have several further remarks after these results to provide additional context for work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss limitations the end of the paper in $
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
16

---

Answer: [Yes]
Justification: We have detailed discussion of the assumptions needed to show our theoreti- cal results in 2 We provide further discussion and present the results themselves in $ We provide full proofs of our results in the supplemental material.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: There experiments in the paper.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
17

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
There are no experiments in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release code and data, we understand that this might not be possible, No is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/
/ ssionPolccy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: There are no experiments in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
There are no experiments in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
18

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
There are no experiments in the paper.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http::///aarrrp...cppopol//hhaaa
Answer: [Yes]
Justification: manuscript.
We have complied with the NeurIPS Code of Ethics in the preparation of this
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is primarily foundational, and the examples considered do not directly impact society.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
19

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper is theoretical, and does not involve any data or models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper is theoretical, and does not any existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
20

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper is theoretical, and does not introduce any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No experiments were conducted in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No experiments were conducted in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
21

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this paper does not involve LLMs as an important, original, or non-standard component.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
22

---

A Covering number estimates and the proofs of Propositions 4.1 and 4.3
The proof of Proposition relies on the following two lemmas.
Lemma A.1 (Approximate covering number under a Lipschitz pushforward map). Let G: R$ R be Lipschitz with constant L 2 0, i.e.,
[[G(*) - G(=)ll S L|| - =||, Vx, 2 IR.
and define P Giy, where "y is any probability distribution on R Then
Covn,(P)) I Covn:/L,(7), vo, 2 0.
Proof. Let (ai);=1 S supp(?) and define 2; =G(z;) E supp(G2y) for i 1....,k. k. Let E G(Bo/L(at)) and write 2 = G(x) for some I E Ba/L (zi). Then
|| - 2,11 = [G(x) - G(z))ll - L|| x:ll Sn. Hence B,y(2)). Since was arbitrary, deduce that G(Bm/L (2:)) (2))) It follows that
(x;) S G (B.( Now suppose that y [ (x/ 1-66 Then, by definition of the pushforward measure
k 27 (UNZ((s))) (B(ta)))))))
U By(zs) Liml
2 Limi
Giy
21-5.
This gives the result.
Lemma A.2 (Approximate covering number of normal distribution). Let == on R... Then its approximate covering number (Definition 2.7 satisfies
(P) - (1
2//oot " where
2 V
log(1/0).
11
Proof. Observe that, for t 2 0,
P(B (oot)) P(X 2 nl2) (0)))(22))) (1e2--t-y112
where X ~ X2 a chi-squared random variable, and the inequality follows from a standard Chernoff bound, Now 1 S 2 gives that
P(B (oar) I (1-111)))
Now set = 1 / 1 log(1/6) so that P(B Vnoi) S Hence, we have shown that
Cov, (P) < (ov,(BBnart) where Cov,, is the classical covering number of a set, i.c.,
(Av, min { k 3ai S CAAC
U Boyans)
i=1
Using standard properties of covering numbers (see, e.g., 5 Lem. 13.22), we get as required.
Cov,,(B,,arr) = Cov n/ (Bi) 1+ 2/noot
Proof of Proposition 4.1
By Lemma A.1
Cov (P) Covn D))
The result now follows from Lemmal
A.2
23

---

To prove Proposition 4.3 we first require the following lemma.
Lemma A.3 (Approximate covering number of a mixture), Let
Let P = Ei=1 P:P: be a mixture of
probability distributions P, on IR", where ps 2 0, Vi, and Ei=1 = Then
(o)) -
Proof. For each I bur. r, let {2j
(0)
C RR, and, in particular, 3x, supp(P:), be such that Jj=1
U j=1
Pi
2 21-6.
Then
ki
P
U f=1==1
B,
BB(l
= Σ PiP;
1=1
i=1==1
Ki
2 Σ PiP:
U Be(os()))
i=1
Σ p:(1 8) = 5.
Notice that supp(P:) C sPpp(P). therefore, Ty (
supp(P). The result follows.
Proof of Proposition mixture
Let : n), s}. Then we can write P, as the
18
P.
Ps.
where Ps defined as follows: I ~~ Ps i; for í & and, for E S, x, is drawn independently from the standard normal distribution R. Notice that Ps Gty, where (N, is the standard, multivariate normal distribution on IR and G: R + R" is zero-padding map. The map Gs Lipschitz with constant L = 1. Hence, by Lemmas A. and A.2
Cov (Ps) < 1 2/st)
1=
log( 1/8)
We now apply Lemma A.3 and the fact that
|S|
71
em
the latter being standard bound, obtain
Cov (P.) < en
(5))
(1 2tst
t= 1 1
2
log(1 (1()))).
17
Taking logarithms gives the result.
24

---

B Concentration inequalities and the proofs of Theorems 3.5 and 3.9
We now aim to prove Theorems 3.5 and 3.9 To do this, we first derive concentration inequalities for subsgaussian random matrices and subsampled orthogonal transforms.
B.1 Gaussian concentration and density shift bounds
Lemma B.1 (Concentration and density shift bounds for Gaussian noise). Let & = NO, d² T). Then the upper concentration bound Dupp (t: E) (Definition 2.4 can be taken as
12
m/2
Dupp (upp(1;8) (1;E)= =
Vl a.
02
and the density shift bound Dshift (E, T; (Definition 2.5 can be taken
m(2 + E) e)))
(e, T; exp
Ve, T 0.
20
Proof. Write E as 7m n. where NO, 1). Then
P([ell P[]n]]] (m///) F(X Pm/o²),
where X = ||r]|2 X2n is chi-squared random variable with m degrees of freedom. Using standard Chernoff bound once more, we have
P(X 2 2m) < (zet
for any > Setting or, have
12 1- 02
m/2
P([ee] 20)
which gives the first result. For the second result, we recall that & has density
(e(e)= (2TT0² /mm) m/2 exp (- m
20 [1el1²)
Therefore
Pe exp
m 20
(||=) (/ (111)1 + [lull))
Pe (v)
Now suppose that ||u]|| S and
|uu u||
S c. Then
Pe (u(
(m(2 +&)
S exp
pe (v)
20
Hence
mm(2 + 8) e)
(s s exp
20
which gives the second result.
B.2 Subgaussian concentration inequalities
Lemma B.2 (Lower and upper concentration bounds for subgaussian random matrices). Let A be distribution of subgaussian random matrices with parameters 3, k. > 0 (Definition 3.4 Then the lower ad upper concentration bounds for A (Definition 2.3) can be taken as
Cupp (t; A, Clow (1 1/t: A, R") 2 exp(-c(t,,,
for any t > 1, where ett, K) depends on B, K only.
25

---

Proof. Let æ E R" and observe that
||=1| 2 (12 1)|(x|1²) P(| 2 t ||==]) - P (11 ||x|| 2 - t {|(l))
P(| 2 +||=]] -
(B.1)
We now use (39 Lem. 9.8]. Note that this result only considers bound of the form Ax]]
||>|||| > -||=| for (0, 1). But the proof straightforwardly extends to >> 0.
B.3
Concentration inequalities for randonly-subsampled orthogonal transforms
Lemma B.3 (Concentration bounds for auddoll--uubsample orthogonal transforms). Let S
Rnt and A be distribution of handoml-ssubsampee orthognal transforms based on matrix U
(Definition 3.7p. Then the lower and upper concentration bounds for A (Definition 2.3
can be taken
as
(-
me(l)
Cupp (t; A, D)
Clow (1/t;A, exxp
(mp(U:))
for any t >> 1, where p(UD)) D) is a in Definition 3.8 and c(t) > 0 depend on t only.
Proof. Due B.1 it suffices bound
( A1111 -|x=| <||==1²))
for s > O. The result uses Bernstein's inequality for bounded random variables (see, e-g.. [5] Thm. 12.18]). Let E D. By definition of A and the fact that U is orthogonal, we can write
N
|| |x - ||
n1 Ix,=1 1) (((, m
Zz-
Notice that the random variables Z, are independent, with E(Z,) = 0. We also have
((U;D)
Z <
(ui 2)
| =: K
and
3 2 n (2e 1
nlkus, 2)12 m
E(I
5 K
K|| =: o².
m2
Therefore, by Bernstein's inequality,
2 |0:|| /2
(-
ms² /2 P(U; D) D)U +
P([| Ax||2 || =||=11? S 2 2exp
-2exp
02 + Ks Ks 1//))
for any 8 > 0 and x E D. The result now follows.
Lemma B.4 (Absolute concentration bounds for subsampled orthogonal transforms). Let D C R and A be distribution of rundomly-subsamplee orthogonal transforms based on a matrix U (Definition 3.7). Then |||] < vn/m m a.s. for A ~ A, and consequently the absolute concentration
bound for A (Definition 2.3 can be taken Cabs (s, A, D) O for any and 2 s nn/m
Proof. Recall that A consists of rows of an orthogonal matrix U multiplied by the scalar / n//m Hence ||||| Σ /n/m|[l]] = /n/m. Now let E with ||>||| < s. Then || < ||||||ж
<
||||ss. Therefore | l Vn/ms meaning that PP [[]] > t) 0. This gives the result. 0
26

---

B.4 Proofs of Theorems 3.5 and 3.9
Proof of Theorem 3.5
Letp 1||=* a|| 2 34(1) + o)). We use Theorem 3.1 with c c2 c'
== and replaced by E/d, where 2 is constant that will be chosen later. Let E' E/(d6//))
Then Theorem 3.1 gives
p S + CabslE', 2,',A, + Dupo (20:
+ shiffe (2E', 20; E)et [Clow (1/2; A, R") + Cupp (2: R") + 2D (2or; E)]
Consider Cabs 2,,;;;,4 A, R.). If E TR with |||||| S 8, then
P(I|ao] > t) P |r (t/s)][æ|]).
Hence, in this case, may take
Cabs(E', A, ) Cupp (2; A, A.))
(B.2)
Now by Lemma B.2 we have that
Craw A, IR* Cupp (2; A, RTth exp( (c((0, k)m),
where k) depends on B, only. Also, by Lemma B.1 we have
E) (2e 12 m/ exp(-cm),
for universal constant and
mm(4 + +2E)
6m
Dahife (26'; (2: exp
25'
S exp
20²
where we used the facts that 2 8/61/0 = de' and d2 1. We deduce that
pS 5 + exp(( + 6m/d c(3,, x)m)
for a possibly different constant c(3,k) > 0. We now choose = d(3,k) = 12/c(B,n). n.). Up to
another possible change in c(B, k), the condition (3.4] on and 3.1 give that p x 6, as required.
=1| 2 34(n o)]. In this case, the forwards operator A satisfies ||||| S Vn/m (Lemma B.4). Hence we may apply Theorem 1.1 with /n/m and d = 2 to obtain
Proof of Theorem
3.9
Let = P| -
x + Cov (P) [Clow A, + Cupp (2; A, D) + exp( cm]]
for some universal constant where supp (P) supp (P). Lemma B.3 now gives that
PS S 8 Cov
exp
U(U D)
exp(-cm)
for possibly different constant c 0. The result follows from the condition 3.5 on m.
27

---

C Proofs of Theorems 1.1 and 3.1
We finally consider the proofs of the two general results, Theorems 1.1 and 3.1 Our main effort will be in establishing the latter, from which the former will follow after a short argument.
To prove Theorem 3.1 we first require some additional background couplings, along with several lemmas. This given in $ We then establish a series of key technical lemmas, presented in C2.2
which are used in the main proof. Having shown these, the proof of Theorem p.teeemm..Ippeeeee.. in via a series of step. We now briefly describe these steps, and by doing so explain how the sets Di, D2 defined in (3.2
arise.
(i) First, using Lemma C.7 we decompose P, R. into distributions P', R' that are supported in balls of given radius, plus remainder terms. The distributions P R' are close (in Wx) to a discrete distribution Q supported at the centres of the balls that give the approximate cover satisfying (3.1).
(ii)
Next, we replace x² ~ R. in the definition of the probability p in Theorem 3.1 by x" P' The is done to align the prior with the posterior (l A). which needed later in the proof. We do this using Lemma C.6 Here we have to consider the action of A on vectors of the form z - 2, where z E supp(R') and & E supp(P"). After determining the supports of R', Pl, we that r
D1, where D1 is the set defined in B.2).
(iii)
We now decompose P' into a mixture over the balls mentioned in (i). After series of arguments, we reduce the task that of considering the probability that the conditional distribution is drawn from one ball when the prior is drawn from another. Lemmas C.4jand hhndde this. They involve estimating the action of on vectors x 2, where the centre of one of the balls and x comes from another ball. Since the balls are supported in supp(P) we have x supp(P), and since the centres come from the approximate covering number bound (3.1. we have that E supp(P) if P attains the minimum and E supp(R) otherwise. Hence x 2 E D2, with D2 as in 3.3
C.1 Background on couplings
For a number of our results, we require some background on couplings. We first recall some notation. Given probability spaces (1,4), (Y, F2, probability measures on the product space (X Y, @ F2)) whose marginals are and v, respectively. For convenience, we write कं X Y (1, and likewise T2 y) y. In particular, for any coupling we have mito μ and T22h = v, where & denotes the pushforward operation. As an immediate consequence, we observe that for any measurable function &p
we write I TH for the set of couplings, i.e.,
and π X + Y for the projections
TR,
J p(xx) du(x)= / p(x) (()))))(())-)))))))))))))))))))) f
JxxY ((z)) v)-
(C.1)
Given cost function e: X + [0, oo). the Wasserstein-p metric is defined
W,(,vv) = inf TET (/ v)p d( v)
1/v
for 1 S p 00 and
7er W v) = inf (csssup,c(I, c(),
We say that y E I' a optimal coupling of p and if
Unry c(.,))) (o)))d((s.))))))))))))))) W2(
1/8
for 1 < < 00 or
((sup,,cI,y)) W),
when p= xo. Note that such coupling exists whenever X, Y are Polish spaces, and when the cost function is lower semicontinuous [4T]. In our case, we generally work with Fuclidean spaces with the cost function being the Euclidean norm, hence both conditions satisfied.
28

---

For convenience, if ys is probability measure on the product space (X x X ( FF))), we will often write ?Ei, E2) instead of (E, x E2) for E, E F. i 1,2. Moreover, if x E X a singleton, we write (1x F2) for ((xx} x F2) and likewise for (F1.
We now need several lemmas couplings.
Lemma C.I. Suppose that (X, M)) (2, are Borel probability spuces, and let y be a coupling of p. v on the space (X x (Fi 2 F2)). Then supp(7) S supp(n) x supp(y).
Proof. Let (x, y) E supp(?). Then (Uz,g) > 0 for every open set Uz.9 S X x Y that contains (x. Now, to show that (z. v) E supp(u) x supp(v), we show that supp(u) and E supp(v).
Let UP S X be open with r E Un. By definition, vuU²,) Tl2 x R²). Since Un R is open and contains (z, y). it follows that >U,, x R") > O. Since UR was arbitrary, we deduce that x E supp(μ). The argument that y E supp(v) is identical.
Lemma C.2. Let X be a Polish space with complete metric d. Let μ. be Borel probability measures on X. Let du be the Hausdorff metric with respect to d and W Wo be the Wasserstein-co metric with cost function d. Then
dh (supp((u) supp(v)) S Wo)...). In particular, supp(u) S (s((sup((v) for any 1) 2 (1,
Proof. Since
du (ssupp(u), = max sup =Esupp(v)
d(z, supp(())), sup d(y, supp(v)
yEsupp(e)
may, without loss of generality. assume that the maximum is achieved by sup= =empp((v d(z, supp(μ)) =: D. Take a sequence {IxInEN S supp(y) such that Dn == d(zn, supp(u)) - D. Since I, E supp(v), for any E > 0. we have v(B.(zn)) )) > 0. Note that B (xx)) is measurable as we assume X is Borel. For each n E N, define En = D. We show
that for all Be, (zn). y E supp(u), d(pp v) > Dn (1 4). By triangle incquality, we have d(x, v) 2 d(En,w) d(r,, x) 2 Dn - Dv.nn = Dm - 1/n).
Notice also that D,, - 11) < D and converges D - 0o. This implies that
A = [(x', d(x', > Dr. 1/n)3 2 Be., (I..)) x supp(n)). Now consider any coupling 7 I p. We have
(A) 2 (Be,, (..) x supр())) = BBB,, (Ix) x X)= = 1 (Be,, (Inn) > 0.
Therefore ess sup.. d(xr, y) > D, (1 11-11) 1/n). Now since D₂, 1) D we have ess sup, d(x.y) v) 2 D. This is holds for any coupling, therefore the result follows.
When working with coupling between imitely-supporterr distribution and continuous distribution, the following lemma is often useful.
Lemma C.3. Let (X, p), (Y, be probabiilit spaces, such that v is finitely supported on set S S. Letr y be a coupling of p. v and C X Y be meaasuabbl. Write E, = (a: : (z. y) E E)
for the slice of E at y E Y. Then
(E)=
Σ
HE, x {s)).
(E)
Proof. Write
(E)= = Σ 7(E x {s} + (É),
(E
where E. F,, (IES. (Fg x (8)). ). It suffices to show that 7(F) O. Since F S -x (T2 F))
for any set F, we have
- ( S ((T (TZ(E)) (É)) = = (((=
But
E= ((x y) E E y $ 5}
and therefore 72 (2) S 0. The result now follows.
29

---

C.2
Technical lemmas
C.2.1 Separation lemma
The lemma considers a scenario where two random variables are drawn for mixture of & probability distributions. The second random variable is conditioned on the draw of the first. It then considers the probability that the two random variables are drawn from different distributions in the mixture, bounding this in terms of their Total Variation (TV) distance. It generalizes [49 Lem. 3.1].
Lemma C.4 (Separation lemma). Let Hi,...... Ha be Borel probability measures and consider the mixture H. Σi=ı a,Hiz Let y² ~ H and Σx=1 Ply (H(y")) where P(y Haly") are the posterior weights. Then Ply" H4, Ū~ H, 1 TV(H; H()).
To clarify, in this lemma and elsewhere we use the notation y² Hi (and similar) to mean the event that y" is drawn from the ith distribution H4.
Proof. Note that if the Hi have densities h2 with respect to some measure, these weights are given by
aphi(y")
IPy"" ~ Holy") = -
(C.2)
We now write
p: p:=Ppyy Hss 9 H1,(11=)] = IP(y" H. H1,(11")1 )1y Hlp
= Ply" ~ HP) ~ Hy(-110) "10" ~ H.l
a.E(P( ~ (y((11)) )) 1y" H.].
Since Byy"ly" ~ Hep ~ Hi. we have
p E ~ H,,(,v))) D> ~ Hi] = / P(ù ~ H, )) (v")
Now, because of the mixture property, Hi < H and therefore its Radon-Nikodym derivative dHL exists. This means we may write
h4 AH
p p= a,
P(ğ ~ (1((11)))),(0 d'H(y").
By definition, we have P(ğ H- = F(y" ~ (1)) and using C.2 we deduce that
p / aaa (hs)"" (v²) d7((y")
Σ (v))
We now write
a,hi(1)) + (zghh(""))) + Expr (1)) d7((y")
(h,,("") )a, dF((y")
a,ha(1") + a (zgh((""))
dH((y)
(athi(v))) aagh((""))
a,h,(y") (h,(""") dH((") (d(((())))))
a,h;(y") + az,)(1"") a,h,(y") (mx(aath.(0"),,,,),, dH(())
min(a.4.
dH(("")
1
2 (h.(ww) + k1(2')) )) min(ash.(u a,yhh) dH((")
/ } (hn((")) -ha") (H((y)
2
TVHH, H,,),
30

---

as required.
C.2.2 Disjoinly-suppooree measures induce well-separated measurement distributions
The following lemma pertains the pushforwards of measures supported in R" via the forward operator A and noise Specifically, it states that if two distributions Pint and Pext are disjointly supported then their corresponding pushforwards Hint.A and Hext. are, on average with respect to A ~ A, well-separated, in the sense of their TV-diitance. It is generalization of (49) Lem. 3.2] that allows for arbitrary distributions A the forward operators, as opposed to just distributions of Gaussian random matrices.
Lemma C.5 DDisjoinly-suppooreee measures induce well-separated measurement distributions). Let f E R 2 0, nj 2 0, 1, Pext be distribution supported in the set
Sa,ext = {i E ER" ||
21| 2 c(n + o0}
and Pint be distribution supported in the sel
Sa = f | 1 17)
Given A E Rmxn, let A be the distribution of y Ax + e where x' ~ Pint and E independently, and define Hext, in similar way. Then
EA-A (V (HHin,,, Hext, 2 Clow (oo: A Dent
Veo Ve A Dint 2upp
Cupp
;
where Dext for - I supp(Pex)) Dint Ir Claw (::AA) and E)) are as in Definitions 2.3 and 2.4 respectively.
E : E supp(Pimt) and Cuppl A),
Notice that the average TV-distance is bounded below by the concentration bounds Clow and Cupp for A (Definition 2.3) and the concentration bound Dupp for & (Definition 2.44). This is unsurprising. The pushforward measures are expected to be well-separated if, firstly, the action of A approximately preserves the lengths of vectors (which explains the appearance of Claw and Cupp) and, secondly, adding noise by & does not, with high probability, cause well-separated vectors to become close to each other (which explains the appearance of Dupp). Also as expected, as e increases, i.e., the distributions Pint and Pext become further separated, the average TV-distance increases.
Proof. Given A E Rmxx
BA EMTR Jly A&Il S Veln + +)).
We claim that
2 Vci iA Dene + (ovp(ov/(:E),
EA SiHHest,(BBA) (Ba)] Clow
(C.3)
Cupp (ve A Dint + Dupp
Ve
EA A
2 )5:8
(C.4)
Notice that these claims immediately imply the result, since
EA-A TV TV Hint,a) EA~A ( - EA-A MaaAAlHeetAA (
Therefore, the rest of the proof is devoted to showing (C.3) and (C.4) For the former, we write
[/ [Ar ee)
EAwA (BA)) BANA
/ /
EAnA
LB, 1e. c))
(C.5)
EANA EanP,n 18(BA- - -xx]]]
ExwPen [AA [((Ba Az)]]
where BA - Ar (b- Ar bb BA). now bound EzuP,,, [EA -B Given x e R"
let C2 = (A: | A&ll < 2/c(n++ C I xm and write
1 Ex-PP E Ar)lo.l, l2 =
EA Az)log]
31

---

so that
EA Az)l] 11 + 1.2.
(C.6)
We will bound I1 la separately, For I1, we first write
Ba oz AM [{ - Ax)1c.]l
< Pa-Pa A [c,]]
Po [P A~ (1lAr Aãil < <2ve(11 - o])}
where the inequality follows from the fact that E(BA - Ax) S 1. Now since I ~ Pexts we have
Sj,ext and therefore || ø| 2 c(1 + σ). Hence
Be (A - A < 2/c(m r)] s EewPes PANa ||Ax [1A0- ATll < fe -
Since the outer expectation term has x ~ Pext we have that a E supp(Pex) with probability one. Using Definition 2.3 deduce that
( Ve"
2
h S Clow
A, Dext
(C.7)
We now bound Iz. Let x E St,ext and E C i.e. 1y - Ar 2 vc(n r)}. Suppose that y a, ie..
||(x - 2)ll > 2/d(n + o). We now show
that A C BA where BA, {y E R
lyy - Aßll S ve(n o). We have
lyy
Ax
11y A# A# Ar|
2 ||A(3 x) - 11 - Ail
> 2/e(1 + +0) - vcln +0)
= Vc(n+
and therefore y E BA required. Using this, we have
E(BA - Ar) = E(A, - Az), AA E C.,, x. E Sz
and therefore
12 = Eew (EAAAEEBBB - Acy1 S (Esn
Ar)1o;].
But we notice that BA. Ax = Be Be(nto) Now since 17 2 0, we have Be Jo(nnt) Baye Hence
E(BAr Ar) = EBB ((()+to) S EEBB - Dupp(ov(c
and therefore 12 uupp (a E). Combining this with C.5
C.6 and
deduce that
E EA (Ba) < Bewp,, (AaAAE(BB (-ABBAAA))) Az)]] = I
Clow (2/vc, A, D Dest Cup
which shows
We will now establish C.4p. With similar reasoning to C.55 we have
E EA-alHime, (Ba) EzxP EA [8 [EA Ar)]]
Proceeding before, let D2 {A A - A < Az) Dg], and Ig = EEWA, [E A
Ve
(1 + ,)), I = E Ba EAnAI(BB
Ax)]
1 D.I so that
EA-A E (B2) Ey-p,. [E A~ (E(B) Au)]] 11 Iz.
(C.8)
The terms J, T2 are similar to those considered in the previous case. We bound them similarly. For I, we have, by dropping the inner probability terms,
P PAAA(I - -x)1 2 Vc (n (n +0o) 2
I < E En- EAM D: = En
Since x E Sp.int we have || Tl|
S 1) S n a which gives
Ve
ve (n +))) < Ex-Pa P (AmA(IAA(I - -) 2 Vc
E Eg [PAAA[ - -i]] >
|1 -=1)
2
2
32

---

and therefore
Vc AA, Dint
h S Cupp
(C.9)
2
We now bound 1g. Let Sniint and suppose that A E DRs i..,, || ž S and ||A(z i) <
2 (17 + r). Define BA.. = fv E R : lly Axll <
v
(n7 + o)}. We will show BA. S BA in this
2
case. Let y BA Then
Vc (n +0) vdnn+ by A S ly Azll + | AFll < vc n7 + 0) +
2
required.
This implies that BA B% Hence
E(BA Ax) S E(B Ax) = E(B = (yto)
S E(B
which implies that 12 < uupp Li o; 8). Combining with (C.8) and
C.9 get
Ve AA A. Dint
+ Dupp VVe
(4
EA A &
((BA Cupp
which implies
C.4 This completes the proof.
C.2.3 Replacing the real distribution with the approximate distribution
We next establish a result that allows one to upper bound the failure probability based on draws from the real distribution with the failure probability based on draws from the approximate distribution P. This lemma is a key technical step that aligns the prior distribution with the posterior. The specific bound is given in terms of the Wasserstein distance between R and and several of the concentration bounds defined in This is significant generalization of (49 Lem. 3.3] that allows for arbitrary distributions A,& E for the forwards operator and noise.
Lemma C.6 (Replacing the real distribution with the approximate distribution), Let Let G, d, t 2 2 I, E be distribution on R. and R, P be distributions on IR" such that (R, P) S E. Let II be an W oottomtimal coupling of and and define the set D (x* 2" (x", ,²) E (IT))
Let
p P A. te, 111a**
+1| 2 d +
and
P. te 211 2 d).
Then
p CabslE, te; D) + Dupp (co E) Dshift (te, co; E)g, where (E, tE; D), Dupp(cor E) and Dohin co, E) are as in Definitions 2.3 2.4 and 2.5 respectively.
As expected, this lemma involves trade-off. The constant (e, Le; A, D) is made smaller (for fixed E) by making the constant larger. However, this increases Dahite (le, ca; E), which compensated by making smaller. However, this in turn increases the constant Dupp (co; E).
Proof. Define the events
B1, fx= || -1| d d+ B2 = (=" :112" 211 d}
so that
D P PR'
BI,a]
(C.10)
P P Am
[2" E B2.=l
Observe that
p E R BAN A.t- BeP
ll +a
33

---

and similarly
q
Lz.
+e, +e..D(3NE(()AAA(A)PPPP
Therefore, obtain the result, it suffices to replace samples from the real distribution R with samples from the approximate distribution P and to replace the indicator function of B1, by the indicator function over 22 s. For the first task, we use couplings. Since Wo (R, P) S there exists a coupling between R, P with [[[] - 211 S E) = 1. By (C.I). we can write
p p= -
18 (x ('P(.IAx* +e, (((G))
Define E ((x,,²) ) || --" SS e) and observe that IT(E) 1. Then, for fixed A, e, we have f 1B (1t) + +,, (=) [0/ 1 (1 (e)))(() + A)())dT(x"""" te, A))dddla, ,²*) =2))== [
/
+e,
We now show 1 B (x*) S B2.a (=*) for (x",²") E. Let =*) E E and suppose that x' B1 Then ||00 - a|| 2 + E and, since || - z" S E, we also have that ||" ----) =|| 2 d and therefore 2" E B2,a, as required. Hence
[ (dP()''' + e, A)( S / 1 (=a) + + +,, ()
for (x", E E. Now, since indicator functions are non-negative, Fubini's theorem immediately implies that
p |S|| / L (PP)) + t A) dAAA)
[
+ A) ((())
Having introduced the coupling IT and replaced 1 B,s by 1 B to establish the result it remains to replace the conditional distribution P(. Arx" + e, A) A) by P(- + e, A). With similar technique to that used in the proof of Lemma C.5
we define Cx., {A: AA(x* =*) ts} and
1 = / (C......))
(A) J 1,, (s')dd(())) + ()) (E (A((4) (lT("" 2*)
/ / Ics... (A) (4) f [ 182, (="))(""))P))))) (z")dP(1AAz" + () (E (()) (T
I
so that
+e, LBgs (
de(e) dA(A) dII([", 11 Iz. (C.11)
We first bound I1. before, we write
1 1= /=///o. lo (A) 5 J |1)2 + +e, (E() (I2",,
$ / /c.... (A) dAA)) dII(x",2")
Recalling the definition of the set E above, we get
[ (A)))(A) dII(=" x²) S / PAaulllA((" - -2a) > tz) dIl((",))))
Using the definition of Co. E and D, we deduce that
I CabslE, A D).
(C.12)
34

---

Now we bound 1z. We further split the integral 12 as follows:
1a 12. 12
(C.13)
where
1n, = 11oo.... (A)) LBs (e) (2') +e,
,²*)
122 = -//11.... (1) / |Bm /
+ a d
Let us first find upper bound for 12.. We have
/ 10 / |Bgg (e) 110011181
11B.. (=) +e, (()G))(()))A(())TT)) (TT)")
2,,
/ ʃ 1o:... lo:...(A) / LBg,
(L (c) dE(e) dA(A) dII(x",,"))
f (e)dEe)..
and therefore, by Definition 2.4
12 = E(BEo S Dupp E).
(C.14)
We now find a bound for 12g- We first use Definition 2.5 to write
(A) f (e. / 1820 (="))((')AAr" + () dII("", ,x",,")) =²)).
I2, =
Now define the new variable e' e A(x 2²). Since, in the integrand. ||e| S co (due to the indicator function (e)) and ||A(x - -I")-l to (due to the indicator function lcs, (A)), Definition 2.5 yields the bound
12, S (te / 1105.. (A) / IB A(x - =p)se(()
x f
+ +e, de' dIIxx,)I(=
We now drop the first two indicator functions and relabel the variables e' and and é, respectively, to obtain
[ 1B,, (PPP)() + de) dA(() dII("", x²").
12, S
This gives
T2 S (léift(le, ea;; E)g,
where is as in C.100. Combining this with (C.3), we deduce that
I2 S (cp 2) + Dshife ca;; E)
To complete the proof, we combine this with [C.II and (C.12). and then recall (C.10) once more.
C.2.4 Decomposing distributions
The following lemma is in large part similar 49 Lem. A.1]. However, we streamline and rewrite its proof for clarity and completeness, fix number of small issues and make an addition to the statement (see item (v) below) that is important for proving our main result.
Lemma C.7 (Decomposing distributions). Let R, P be arbitrary distributions IR 1 and m. p, If WR,, < and is such that
minglog Cov,,,(P), log Cov (R) < k,
(C.15)
then there exist distributions R',R", PP, P", a constant 8' S and a discrete distribution Q with supp () S satisfying
35

---

(1) min Q), (R' 2) S
(ii) Wx (R),'' 3179.
(ii) P 11-28 P'') + (2 and R (1-28 21' (28'
(iv) |8| See
(v) and S C (P) ifP attains the minimum in CC.5 with S S Supp(R) otherwise.
This lemma states that two distributions that close in Wasserstein p-distance, and for which least one has small approximate covering number (C.15). can be decomposed into mixtures (iii) of distributions, where the following holds. One of the distributions, say P', close (i) in Wasserstein-co distance to discrete distribution Q with the cardinality of its support (iv) bounded by the approximate covering number. The other R' is close in Wasserstein-c0 distance to P'. Moreover, both mixtures (iii) are dominated by these distributions: the 'remainder' terms p" and R" are associated with small constant 8' 6, meaning they are sampled with probability I 8 when drawing from either P or R. Note that if p < oc then the Wasserstein-os distance between R' and Pp' may get larger as 5 shrinks, i.e., as the remainder gets smaller. However, this does not occur when p oc, as (ii) independent of 5 in this case.
Proof. Without loss of generality, we assume that log Cov,,o(P) I k. Then Cov,,o(P) ct and hence there a set S {u, V S supp(P) with I et, where the u, are the centres of the balls used to cover at least 1 - of the measure of P. That is.
p U B(u, m) = PAND
x x U B(u,, 1=1
=: =
We now define f: RR" + R so that f(x) = 0 if x lies outside these balls, and otherwise, f(x) (t) is the equal to the reciprocal of the number of balls which x is contained. Namely,
if x E U'_n B(u;, ((us,))
f(x) = E on
otherwise
We divide the remainder of the proof into series of steps.
Construction of Q'. We will now define a finite measure Q'. The point of Q' is to, concentrate the mass of the measure P into the centres of the balls uy If the sets ((u,, .1) are disjoint, then this is straightforward. However, to ensure that Q' is indeed a probability measure, we need to normalize and account for any non-trivial intersections. This is done via the function f. Pick some arbitrary & (ui...., 4 and define
--=(( (J ((x) 8m, + c
Q e'=E 1=1
Observe that
Σ/ dP))) +c' = (U + = -1- =1.
B(an.))
and therefore Q' is probability distribution supported on the finite set S (ū).
Coupling O', P. Now that we have associated all the mass P with the points us we can define a coupling between L' and P that associates the mass of P and u, with single measure. Moreover, this measure will keep points within 77 distance of each other with high probability. We define II as follows for measurable sets E, C I::
Σ (r((s) / B(a
F U B(..:))
IT F)
To see that this a coupling, we first observe that
1F(u.) / J
IIRR" Th F)
36

---

which gives the result for the first marginal. For the other, we have
TE,R")
(x))
+
F U
B(uin))
A(uL.))E
i=1
By definition of f, this is precisely
ITE R*) = P En FAn B(u. +P
F U B(us, m) = P(E).
1=1
which gives the result for the second marginal. Note that II was only defined for product sets, but, since Q' finitely supported, it follows directly from Lemma C.3 that it extends to arbitrary measurable sets in the product sigma-algebra. We now show that Li[l - I2ll > ri] S c* S 6. That is, show that most points drawn from are within 7) distance of each other. By law of total probability we have
M[[ x2ll > 11)
[[[ x2l n/ u: [T) = u.)
1=1
[[[ - x21l > n/ = ()) ú)
IIUU, u.) (u,)) nθ Qi),
where U; = (x: || uill > n and = fo: || - úl| > n) Notice that U3 n Bu;, n) = 0 and therefore
II(U,, us) = (0:1)a--0112)))0000 - fdP =0
Hence
Σ I(U,, ((C ()) I((
and, since Q'(û) c", have ITŪ (() < c' < 6. This gives
[[ T2 7 S 6,
(C.16)
as required.
3. Coupling P, R. The next step is to introduce R. With the assumption that W, WR P) < p. by definition there exists coupling between P and R such that Er || x2 12 S pa. Markov's inequality then gives that
Er Er 22121
T [|21 - x2ll
<
(C.17)
51/p
4. Coupling P, Q', R. We next couple P, Q' and R. Before doing so, first discuss the goal of our final coupling. Recall that we have the distribution P. the distribution that couples P, Q' closely except for up mass of P. and I which keeps P, R close again except for up to d of the mass of Т. We want to decompose P into the portions that are rj close to Q', and points that are not. These will become P' and P" respectively. At the same time, we want to decompose R to points that 377 close to P', and points that are not. Naturally this will become R' and R". To achieve this, we couple P, O' and R in this step and then use this to construct the final decomposition in the next step.
e
We have measures P. Q' and R and couplings II of P, Q' and I of P. R. We will in a sense, couple 11, r. Since 33 is a Polish space, by [10 Lem. 8.4]. there exists a coupling with
Ti #1 11, T
where (1,2 23) (x), x2) and likewise for T1,3. One should intuitively think of the component as samples from P. the 22 component as samples from Q, and the 33 component as samples from R. With the base measure defined, still want to ensure that I T3 sampled
37

---

closely, and 22,42 are as well. Consider the event such that 21, 23 are 8f/p close and T1, 22 are close: namely, = {( x2, 23): : || - =zsl S p/8 and |2] x2ll S n7)
Split up the negation of the two events of ||=1 - 23|| - p/8 and || - x2ll S 1) into the events
E = {11, xz) : || x2l > 17,2 E R,
Eg =
25) || -zl > p/8 R"),
so that E E1 U2. We will now show ( < 6. Write E1 = Ej x IR" where E = ((11,
| 22 > n) satisfies (EE) 8' by (C.66) Then
/ LEy (2) dr 21,
8' 2 ((E))
/ Ey
23)) x2,
/ LEy (2), x2, 13) d 22, 22, 03)
={)),,,
as required. Using (C.17) we also have the analogous result for Eg. Hence ?(E = S2(E) U E2)) <
((E,)) + (EE,) =: 20 < 28', and consequently,
Q(E)= 28' 2 1 1-20 26,
(C.18)
where E = a2, vz): : || xall S p/8 and || x2ll S nn
Decomposing P,R. R. Finally, we define p', p", RR and ES, as follows:
R" and Q by conditioning on the events E
P'(A) = 2 RD F)),),
R'(A) D(R", R AEE).
P"(A) (2(ARR" R", R*(
R"(A) S2(R", RR" A(F))
Q(4) = " A,.
This gives
= S2,, R") = ((E))((A R" RT + ((EE)((EEAAAEE) R","""
= -1- PP' (A) + (A)
and similarly
R(A) = Q(R "ARR",,,RR, A,R") (EE)R(" A, (2 A.)
= =(1 211-2)))R(A) 25'
We now claim that these distributions satisfy (i)-(v) in the statement of the lemma. We have already shown that (iii) holds. To show (i), we define a coupling y of Pt, Q by y(B) (2 R= E) for any B C (2=) Observe that Y(A, = 2(A, "K",, R" E) = P'(A) and >(R" A) =
Q A, Rd E) = ((4). Hence this is indeed a coupling of P', Q. Therefore it suffices to show that (B) = O. where B is the event {1|2] x2l > 7). We have (B) = Q(B, R EE)
Recall that for (x1, F2, 23) E E, we have |m]] - x2ll S 17. Hence Q(B, R E) 0. Therefore,
(P' Q) S 7, which gives (i).
Similarly, for (ii) we define coupling 7' of R', P' by (B) F) where B = 22, (1120)) E 2: R. With similar reasoning the previous case, 7 is coupling of R', P' and, for (x (2,, v3) E E we have ||=] Iall S p/81/r, /v, so letting B be the event {||2 rall p/5l/r).
we conclude that W (R', P') & p/8L/p. This gives (ii).
Finally we verify (iv) and (v). First recall that both properties hold for Q' by construction. The results now follow from the fact that ('(+) 2(R", Rn) and Q(-) Q(R EE).
D
38

---

C.3 Proof of Theorem 3.1
We now prove Theorem 3.1 This follows a similar approach to that of (49 Thm. 3.4], but with series of significant modifications to account for the substantially more general setup considered in this work. We also streamline the proof and clarify number of key steps.
Proof of Theorem 3.7 By Lemma C.7 we can decompose P. R into measures P', and construct finite distribution supported on finite set S such that
P" and RR,
(i) m 2), Wo 2) S n
(i) Wo (R'' P') S e' := डीलक
(iii) p (1 28')P + (28'P" and R = (1 -220)R' + (28"RR" for some 0 S 8 S 6,
(iv) |S| S set
(v) and S C (P P attains the minimum in (C.15) with S C supp(R) otherwise.
helpful to briefly recall the construction of these Beginning with 6, ry as parameters for the approximate covering numbers, the distribution Q concentrates 1 1 of the mass of P into the centres of the 17-radius balls used. Then the distributions Pa, R' are the measures P, R within the balls. We now write
p =
211 2 (c+ 2)m + (c+ 2)o]
< <R (n - a1| 2 (c 2)n (c+ + +''l
(C.19)
$ 28' + -1- 26' (1-26') P A w,)))|l=** - all ž (c+ 1)(1 + +))
=: 28' + +(1 +1-188) 28')g.
Here, in the first inequality we used the fact that a > e', and in the second, we used the decomposition R = (1 - 28') + 28'R"" and the fact that o' < ō. We now bound by using Lemma C.6 to replace the distribution R' by the distribution P', Writing
A=* + e, this lemma and (ii) give that
SCabsl :al'',,t'''' At' D) + Dupp(c'or E) + Dsint c'a;'',''';))
(C.20)
where PA* AAAA,EE (u,,a) - $|| 2 (c 1)(7+
and D f-+ (x* (Ipp(III) for II being the Wo optimal coupling of R', p guaranteed by (ii). Lemma C.I implics that supp S supp(R') x supp(P") and therefore
D C supp(R') supp(P').
Now (iii) implies that sPpp(P') S supp(P). Similarly, (iii) implies that supp(R') S supp(R). But Lemma C.2 and (ii) imply that supp(R') C (supp((())) Therefore
D S (supp((()) (u) supp(P) D1,
where Dj as in 3.2
We now bound Observe first that
(P 2) sn/:=t=
Indeed, from (i) either (P' Q) < n (R', Q) < 7. In the former case, the inequality trivially holds. the latter case, we can use the triangle inequality and (ii) to obtain the desired bound. This implies that there is coupling I of P', Q with esssupr || yll < 1/. Fix E E S and, for any Borel set E RR",, define
T(F,
(E)
((3)
Then it is readily checked that [-).) defines probability measure. Note also that T3 is supported on a ball of radius r/' around E, since esssupr ([|=  y < r// Recall that a coupling between P and Q Let E C IR" be Borel set. Then Lemma gives that
P'(E) = I(E,
Σ L(EE,
Σ I(E
Σ Tz(E)Q(2).
39

---

Therefore, we can express P' as the mixture
P'(+) Σ (z)))
Define the event F: [||=* 2|1 (c+ 1) + C IR x R that the probability defined in (C.20 can be expressed as
r= WP' A
Using the above expression for P' we write
= LE(2", | ())
Σ [ (x*)
EES
2E)) ( (1
EES
where the last line holds as 2(3) a constant. Hence
Σ P Q.A
(C.21)
EES
Now we bound each term in this sum. We do this by decomposing P into a mixture of three probability measures depending on S. To do this, let 0 c(1 σ) and observe that, for any Borel set E C RR,
P(E)= = P(E B²( + P(En BB())
P(E n (²( + P(En
+1 (1-)))))((()))0 (1- (()r
(11)))))))
=PEE n - ( Bo(E)
+ PPE (1 -1--1(1)))))))))
B3))))
(1-=2))Q(2IIx(E))
Now define the constants
Ca,mid = (²)) - (1 (1- (
Cz,ext
(1 (1-)))))0000))))
and let
Pgiine (F) = =F=(F))
Pa,iid (e)
(P(En Bg(z)) - (1- (L=28))(2)))((En B₂(
Ca
Pz
(P(En (5 - -
(5(2"))
C2,ext
Then P can be expressed as the mixture
P= (1- 28') (2 Ca. Pa. + C2 Ca,ext2z,en 2,ext
(C.22)
To ensure this is a well-defined mixture, we need to show that Pa,mid and Pz,ex are probability measures. However, by (iii we have, for any Borel set E C I2"
P(E) 2 (1- 28')
28') Σ
EES
Therefore, Pi,mid and Pa. Pi,ext well-defined, provided the constants Cg.int, C2 0. However, if one of these constants is zero, then we can simply exclude this term from the mixture C.22 For the rest of the theorem, we will assume that, least, Cs O.
now useful to note that
supp(Pa,mia) (a) and supp(Pz.ex) S (2),),
40

---

which follows immediately from their definitions, and also that
supp(Pa,int) By (2) 3) _ Bo(²). where in the second inclusion used the fact that n/ = 1) + e/6 Into cn σ) = =0, as
e/02/v and 2
We now return to the sum (C.21) Consider an arbitrary term. First, observe that, for =" ~ P. we
have P(=* ~ P3) ( 20') by (C.22) Hence
P(z* Ts)
rel
1 28'
P( ~ r2))
(1 28)) P( [2) / (
Recall that 2t ~ Tg is supported in BBy Therefore, for the event E to occur, i.e., || - El1
(c+ 1)(n + o), it must be that & E (2), which means that & ~ Pz,ext (-|A, u). Hence
/
1 dP(x") (z*) dP u)
28'
1 28' P(z" ~ Pi,iue, & (-
Now fix A Rmxn, Let A be the distribution of A=* for 2" ~ Pziine and e E independently, and define Hg,eat similarly. Then, by Fubini's theorem, we have
A. [1g] 1 - 28' E EAwACnePly ~ Hg,int, D Hz A.
Now let Hs. be the distribution of y = Az + e for ~ P and e ~ & independently. Then Lemma C.4 (with H. H., H.1 An,int.A. H2 mid H3 Hg,ext.A and aj -1- 20)) 42 = Ca,mid, = c2,ext) gives
1
[El Finally, summing over all 8 we deduce that
EANA TV(Hs,itt.A Hs,ext,a))
28'
Σ Q(2) QU ES
1
Σ BES
EAwAlL TV Hs,ext, A)].
28'
(C.23)
Now recall that Heii A is the pushforward of measure Ps.i supported in (2), where of' + e' & + + a and Hx,,xt is the pushforward of measure Pi.est supported in BB( where
= c(n +o) 2 5(n' + O)). Therefore, Lemma C.5
(with e replaced by c/2) gives that
2v2
Ve
E TV(Hs.im. Hs.ex.,)) S Clow
A. Dz,ext
Cupp
A, Dzjint
Ve
2v2
Veo
+ 2Dupp
2/2
where Di,emt (a- -;: ; supp(P:,ea) and Dz {x 3::0 supp(Ps.im)) It follows immediately from (C.22) that
(upp(Pa.in)) supp.(P.) C sP.
Moreover, E S and therefore
Dz.ea Dz.int S D2,
where D2 is as in 3.3
Using this, the previous bound and C.23 we deduce that
|s|
2V2 A. ...
Vc
VVoa
r 5 To complete the proof, now substitute this into (C.99 and (C.20) to obtain
Clow
Cupp
A, D:
+Duupp
(222()
1 28'
Vo
2
p = 28' + te': + (upp(d
2V2 A, D2 + Cupp
Vc Ve. A, D22 A,
Vea + +2Dupp
+ 2D (ts', E): Clow
2 :
Ve
2/55/
The result now follows after recalling (iv), i.c., |S| s t and the fact that 8' 5 < 1/4.
41

---

C.4
Proof of Theorem 1.1
Finally, we now show how Theorem 3.1 implies the simplified result, Theorem 1.1
Proof of Theorem 1.1 Let p- PP || ill 2 (8d2 2)(7 + o)]. We use Theorem 3.1 with
replaced by e/ (2m00) Let 8d2 d' 2, = 0 and e' =/((22//mm)) Then Theorem gives that
p z + CabalE', Ai) + Dupp(2o;E)) E)
+ shift (0=', 20; Ele² [Clow [1/d;A, D2) + Cupp (d; D2) + uDppp(do E)]
where
D1 B (supp((()) Suupp(R) - supp(P) S (suppp((P)) (P) supp(P)),
D2 = D = (P) supp(P) (P) and ls = [log c Now since || < |||||||=|| - 0||
Yr E I2, we make take Cabs(E', 0'; A, D1) O. Moreover, by Lemma B.1 we have
m(4o + 0E¹) 052) = exp
(Oe' 20;;) I exp
21
20²
@L/PO
852/Po2m
where we used the facts that m and 2 2//6/P Hence
p P et |C_ (1/d;A, D2) C+ (d; D2) C(do;
Finally, Lemma B.1 implies that
Dupp E) S (do--a)m/2 m2/ exp(-m/16))
where in the final step used the fact that d 2 2. This gives the result.
42


Reviews:
[{"review_id": "EvpzEYPlvx", "reviewer": "Reviewer_aqBr", "summary": "The authors establish rigorous recovery guarantees for compressed sensing when signals are drawn from a known prior and both the measurement operator and noise follow arbitrary distributions. Their main result (Theorem 1) bounds the probability that the reconstruction error of a posterior sample exceeds a fixed constant plus a noise-dependent term. They then instantiate this general bound to obtain explicit recovery guarantees for two important forward operators subgaussian matrices and subsampled orthonormal transforms which respectively extend the results of [3,14] and [46]. Finally, they show that the same framework applies to two practically relevant approximate priors: Lipschitz-continuous generative models and sparse vectors.", "questions": "1. **Could the authors please outline their technical contributions that enabled them to generalize the arguments in \\[3, 14, 46]?**\n\n2. **Could the authors explain the technical difficulty of assuming a distribution over the noise term instead of specifying a density, as mentioned in the “Future Work” section?**", "limitations": "Na", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. The work is dense, but easy to follow because it is well written and tells a coherent story.\n2. It generalizes impactful results from previous work \\[3,14,46], as shown in Section 3.\n3. It provides explicit sample complexity bounds for Lipschitz generative neural network priors.\n\n**Weaknesses**\n\n1. The main weakness is that the authors do not explain any novel proof techniques they used to develop these generalization methods; the manuscript’s tone suggests they are simply leveraging arguments from prior work.\n2. There is no remark, justification, or explanation for why the noise distribution is left unrestricted in Definition 2.5.", "was_revised": true, "final_justification": "The authors have alleviated my concerns and demonstrated the technical strength to make this paper a strong contribution to the community. It generalizes the theoretical arguments of several influential works on generative priors for inverse problems and would be an important paper for the research community.", "rebuttal": "We very much appreciate your effort in reviewing our paper and are delighted by your positive assessment. Here we address the comments in your report.\n\n# Weaknesses\n\n## 1. The main weakness is that the authors do not explain any novel proof techniques they used to develop these generalization methods; the manuscript’s tone suggests they are simply leveraging arguments from prior work.\n\nThanks for the comment. We discuss this further below in our reply to your question.\n\n\n\n\n## 2. There is no remark, justification, or explanation for why the noise distribution is left unrestricted in Definition 2.5.\n\nThanks for this comment. Arguably, having a general noise distribution is not the biggest innovation in the paper, as in many applications the noise is assumed to be standard Gaussian. We agree the results are `cleaner' with Gaussian noise, and in fact we used this in our simplified results, Theorems 1.1-1.3. However, since a major focus of our work was to allow for arbitrary distributions $\\mathcal{R},\\mathcal{P},\\mathcal{A}$ it seemed strange to then consider only standard Gaussian noise in the main theorem. Unfortunately, as can be seen in Definition 2.5, we could not consider completely arbitrary noise - however, see also the discussion below. Regardless, we do think there are some benefits to doing this. For example, if the noise $\\mathcal{E} = \\mathcal{N}(0,\\Sigma)$ was Gaussian but with a a nontrivial covariance matrix (as arises in some applications), then we can still apply our results. Conversely, if one had only considered standard Gaussian noise, the proofs would have had to be redone for each new noise distribution. We agree a better justification could be added. Due to space limitations, we did not do this in the paper. **We will add a short justification/explanation to the revision, immediately after Theorem 3.1.**\n\n# Questions:\n\n## 1. Could the authors please outline their technical contributions that enabled them to generalize the arguments in [3, 14, 46]?\n\nThanks for this question. You are correct that our work is most closely related to [3,14,46]. \n\nThe works [3,14] consider the deterministic setting, where $x^*$ does not follow a distribution. They derive recovery guarantees for the point estimator $\\hat{x}$ obtained by minimizing the $\\ell^2$-loss. For a more detailed discussion on this setting, please see l.143-148. Note that this discussion is in reference to [20], but the same considerations apply to [3,14].\n\nWe want to stress that the proof techniques employed in the Bayesian case are completely different to those used in the deterministic case [3,14]. Unfortunately, at several points in the paper we referred to our work as 'generalizing' [3,14]. This may have given the wrong impression. Our work derives a Bayesian 'analogue' of [3,14] rather than a `generalization' per se. This aside, both [3,14] also make assumptions on the model class $\\Sigma$ (analogous to $\\mathrm{supp}(\\mathcal{P})$ in our work). In [14] $\\Sigma$ is the range of a ReLU generative model. [3] is more general, but it still assumes that $\\Sigma$ a subset of finite union of finite-dimensional subspaces. These works then use matrix concentration inequalities and union bounds [14] or chaining arguments [3] to derive recovery guarantees. We do not consider these specific models, or distributions related to them, nor do we use these techniques. The main concept we use from [3,14] is the coherence (Definition 3.7), which appears in Theorem 3.8. Our work is also inspired by [3] in the sense that it strives to be very general (in fact, more general than [3] -- see above), by considering arbitrary distributions $\\mathcal{P}$. However, we reiterate that there no overlap with the proof techniques employed therein.\n\n\nOur work is a generalization of [46], which considered the case where $\\mathcal{A}$, $\\mathcal{E}$ were Gaussian. Our proof techniques are certainly built on [46], however they involve significant modifications and nontrivial extensions to handle general $\\mathcal{A},\\mathcal{E}$. Perhaps the biggest technical contribution we make is encompassed by the introduction of the concentration bounds, Definitions 2.3 and 2.4. The key innovations here are threefold. First, we show that these concentration bounds, for general $\\mathcal{A},\\mathcal{E}$, precisely control the quality of recovery -- see the main bound in Theorem 3.1. Second, we impose the concentration bounds for $\\mathcal{A}$ over subsets of $\\mathbb{R}^n$ only. Please see $D_1,D_2$ in Theorem 3.1 and Remark 3.2 for more discussion. Here we would like to stress that it is not necessary to do this in the Gaussian case considered in [46], as one can get fast concentration over the whole of $\\mathbb{R}^n$ with a Gaussian random matrix. But it is absolutely crucial for other distributions, e.g. subsampled orthogonal matrices. Please see Remark 3.9. Showing that concentration was only required over sets related to the support of $\\mathcal{P}$ (see $D_1$ and $D_2$ in Theorem 3.1) was a major technical hurdle to overcome in this work. Had we only considered concentration over $\\mathbb{R}^n$, then the  measurement condition in the subsampled orthogonal matrix case would have been at best $m \\gtrsim n \\log(n)$ -- a largely meaningless bound. Third, it was necessary to introduce both relative $C_{\\mathsf{low}}$, $C_{\\mathsf{upp}}$ concentration bounds and, to our surprise, an absolute $C_{\\mathsf{abs}}$ concentration bound as well. Had we only considered the former two, we would have again ended up with meaningless bounds.\n\n\nWe agree these points could have been made clearer in the paper. **We will amend and expand the discussion in §1.4 on [3,14,46], emphasizing that our work does not generalize [3,14] and providing some more details (as discussed above) on the technical contributions in relation to [46].**\n\n\n\n\n\n\n## 2. Could the authors explain the technical difficulty of assuming a distribution over the noise term instead of specifying a density, as mentioned in the “Future Work” section?\n\nThanks for this question. The reason for specifying a density for the noise comes from a key step, Lemma C.6, in the proof of Theorem 3.1 where we need to replace the `real' distribution $\\mathcal{R}$ in the probability term $p$ in Theorem 3.1 by the approximate distribution $\\mathcal{P}$. This is done in order to align the prior and the posterior, which is necessary for the subsequent steps of the proof. The density shift bound arises in the proof of Lemma C.6 when we make a change of variables. Specifically, given $e \\sim \\mathcal{E}$ and $( x^* ,z^* ) \\sim \\Pi$, where $\\Pi$ is a coupling of $\\mathcal{R}$ and $\\mathcal{P}$, we introduce a new variable $e' = e + A(x^* - z^*)$. To handle this change of variables, we assume that the noise has a density and use the density shift bound $D_{\\mathsf{shift}}$ to bound the effect of this change.\n\nWe agree this term is a bit mysterious, and are looking into whether it can be removed in the future. **We will add some more details about where this assumption comes from in §5 (``Limitations and future work'').**"}, {"review_id": "qn5Bn5Z5Q5", "reviewer": "Reviewer_b54M", "summary": "This work seeks to quantify when, for linear inverse problems (i.e. compressive sensing), adequate Bayesian recovery is feasible in terms of the dimensionality reduction between the observation and original signal (i.e. the number of measurements). Assuming an approximate prior with low complexity and concentration bounds on the measurement and noise distribution, this paper upper bounds the probability that a sample from the posterior deviates too far from the original signal. Given this main theorem, the authors give results in specific instantiations, such as for sub-gaussian measurement designs and random sub-sampled orthogonal transforms.", "questions": "- When the prior is multimodal, with say $d$ modes, the covering number should also be $d$, assuming the modes can be contained in an $\\eta$-sized radius. Is it correct to interpret Theorem 3.5 as saying roughly $\\log{d}$ measurements are needed to specify what mode the signal was drawn from? Is there an intuitive way to see why this is the case?\n\n- Line 328; is there any practical benefit to requiring trained DNNs have small coherence? \n\n- It is worth reflecting on the literature around information-theoretically optimal recovery of $\\hat{x}$ with algorithms like approximate message passing (AMP), which also map out the hardness of linear inverse problems through statistical-computational gaps (some references: \"The dynamics of message passing on dense graphs, with applications to compressed sensing\", \"Message-passing algorithms for compressed sensing\", and \"Unrolled denoising networks provably learn to perform optimal Bayesian inference\"). For example, in the asymptotic limit, how do your worst case error bounds on $\\hat{x}$ relate to what is information theoretically possible for the minimal $||x^* - \\hat{x}||$ (for a given $m$)?\n\n- As a matter of clarity, it would be helpful to isolate (in a remark) where the bound presented in Theorem 3.1 depends on the measurement number: e.g., in $C_{\\text\\rm low}$ and $C_{\\text \\rm upp}$. It would also be helpful to include a brief sketch of the main ideas of the proof (especially where the different regions $\\mathcal{D}$ come from, )\n\n- Wherever you have $\\text{supp}(\\mathcal{P}) - \\text{supp}(\\mathcal{P})$ (lines 237, 291, etc.), do you mean $\\text{supp}(\\mathcal{P}) - \\text{supp}(\\mathcal{R})$?", "limitations": "Limitations were clearly discussed.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- This paper gives quite universal theoretical results that quantify the measurements needed for the posterior to be concentrated around the original signal in linear inverse problems, abstracting approximate priors, measurement designs, and error distributions.\n- The paper answers unsolved theoretical questions in the literature regarding sample complexity for recovery for subsampled orthogonal transforms.\n \n\nWeaknesses:\n- Since the paper gives sample complexity bounds for Bayesian recovery but doesn't approach, e.g., algorithms for actually sampling or estimating $\\hat{x}$, the practical scope is limited.", "was_revised": true, "final_justification": "- After reviewing the clarifications provided by the authors, I have a strong sense of the importance of this work as a fundamental theoretical contribution providing sample complexity bounds for Bayesian recovery and its broad applicability to posterior sampling algorithms. I have raised my score to a 5.", "rebuttal": "Thank you for your careful review our paper and your positive assessment of it. Here we address the comments in your report.\n\n# Weaknesses:\n\n## Since the paper… \n\nExcellent point. Indeed, we do not discuss any examples of posterior sampling algorithms. There is a considerable amount of literature on these methods, which have been mainly studied empirically. Our paper aims to provide theory that these supports these empirical results. As an example, one popular class of methods involves Langevin dynamics. Since this requires computing $\\nabla_x \\log \\mathcal{P}(x|y) = \\nabla_x \\log \\mathcal{P}(y|x) + \\nabla_x \\log \\mathcal{P}(x)$, a common approach is to use a score-based diffusion model which has access to an approximation of $\\nabla_x \\log \\mathcal{P}(x)$. We refer to [45, 50] as examples. Predictor-corrector methods that alter a trained generative model in the decoding process of a diffusion model have also been studied (see [65]). Non diffusion model based methods have also been studied (see \"Markov Chain Generative Adversarial Neural Networks for Solving Bayesian Inverse Problems in Physics Applications\").\n\nAn advantage of our paper is its independence from the choice of posterior sampling algorithm. Namely, our results do not depend on the algorithm used, and analysis of the sampling algorithm can be done separately, for instance in \"Diffusion Posterior Sampling for Linear Inverse Problem Solving\". We believe that further studies including analysis of these algorithms are interesting and important problems. In the future, we aim to examine these implementations for precise verifications of our theory and generalizations of our results. \n\n**We will add this discussion in §5 (\"Limitations and future work\").**\n\n# Questions:\n\n## When the prior is...\n\nThis is an excellent question. You are correct in your understanding. **We will add the following after Thm 3.5:**\n\n\"Suppose that $\\mathcal{P} = \\mathcal{R}$ is a sum of $d$ Diracs located at $X = \\{x_1,\\ldots,x_d\\} \\subseteq \\mathbb{R}^n$. Then Theorem 3.5 predicts recovery from roughly $m = O(\\log(d))$ measurements. Intuition for this comes from the Johnson-Lindenstrauss Lemma (JLL). The matrix $A \\in \\mathbb{R}^{m \\times n}$ is a linear dimensionality-reducing map. JLL states that distances in $X$ are preserved under $A$ if and only if $m = O(\\log(d))$. In this setting, preserving the distances in $X$ is equivalent to being able to stably identify the mode from which a signal is drawn.\"\n\n## Line 328; is there any...\n\nYes, good point. Theoretically, according to Thm 3.8, the smaller the coherence the fewer measurements are required. Empirically, [14] conducts numerical experiments in the deterministic case that show that incoherent generative models require fewer measurements for recovery. **We will add the following clarification at the end of l.328:**\n\n\"Numerically, they show that generative models with smaller coherence achieve better recovery from the same number of measurements than those with larger coherence.\"\n\nIn future work, we also intend to study this phenomenon experimentally in the Bayesian setting.\n\n## It is worth reflecting on...\n\nThanks for this insightful comment and references. This is very interesting work, and there are definite overlaps with ours. In a general, both approaches strive to consider arbitrary prior distributions and incorporate distributional information into the recovery. However, there are also some key differences. First, our results are nonasymptotic - they hold for fixed $m$ and $n$ - whereas most of the work on AMP considers an asymptotic regime. Second, much of the AMP literature focuses on Gaussian measurement matrices. Our focus is more on non-Gaussian matrices, e.g. subsampled orthogonal matrices. We are not aware of as complete a theory for AMP-type techniques for such matrices. Third, in our work we consider Bayesian recovery, where the aim is to approximate the posterior. As far as we are aware, AMP methods typically compute a point estimator for $x^*$ only. However, it's worth noting that AMP methods are fast algorithms for computing point estimators, whereas we do not consider algorithms for sampling from the posterior. As we commented above, efficient implementation of posterior sampling is an active area of investigation.\n\n**We will add this discussion and references to §1.4 (\"Related work\").**\n\n## For example, in the asymptotic....\n\nExcellent question. This was studied in [46], which gives information-theoretic lower bounds. [46] shows that if any recovery scheme achieves $O(\\eta)$ accuracy then the number of measurements (for any $A$) must scale at least linearly in $\\log \\mathrm{Cov}_{\\eta,\\delta}$. Combined with the upper bound for Gaussian matrices, the conclusion is that the approximate covering number sharply characterizes the number of measurements for recovery (up to constants). \n\nThe focus of our paper is upper bounds, and, as noted, non-Gaussian measurement matrices. Nonetheless, it is important to note that such lower bounds exist. **We will add a comment on this to §1.4 as well.**\n\n## As a matter of clarity, it...\n\nExcellent comment. You are correct that $m$ enters the concentration bounds, which are exponentially-decaying in $m$ for reasonable $\\mathcal{A}$, $\\mathcal{E}$.  **We will add the following remark about this immediately after Thm 3.1:**\n\n\"Since Thm 3.1 considers arbitrary measurement and noise distributions, the number of measurements $m$ does not explicitly enter the bound. For typical distributions, a dependence on $m$ is found in the concentration bounds $C_{\\mathsf{low}},C_{\\mathsf{upp}},D_{\\mathsf{upp}}$, as well as the terms $D_{\\mathsf{shift}}$ and $C_{\\mathsf{abs}}$. In particular, the former decay exponentially-fast in $m$ for the examples introduced in §1.2 and therefore compensate for the exponentially-large scaling in $k$ in the main bound. See §B for precise estimates. See also the discussion in §3.1 and 3.2 below.\"\n\n## It would also be....\n\nGood point. As there may not be space in the main paper, **we will add a clear description at the beginning of §C**.\n\nAllow us to briefly explain. The first step in the proof of Thm 3.1 is to decompose $\\mathcal{R},\\mathcal{P}$ into distributions $\\mathcal{R}',\\mathcal{P}'$ that are supported in balls of a given radius, plus remainder terms. The distributions $\\mathcal{R}',\\mathcal{P}'$ are close (in $W_{\\infty}$) to a distribution $\\mathcal{Q}$ supported on the centres of the balls that give the approximate cover satisfying eqn (3.1).\n\nThe next step is to replace $x^* \\sim \\mathcal{R}$ in the definition of $p$ in Thm 3.1 by $z^* \\sim \\mathcal{P}'$. The is done to align the prior with the posterior $\\mathcal{P}(\\cdot | y , A)$, which is needed later in the proof. We do this using Lemma C.6. Here, we have to consider the action of $A$ on vectors $x - z$, where $x \\in \\mathrm{supp}(\\mathcal{R}')$ and $z \\in \\mathrm{supp}(\\mathcal{P}')$. After determining the supports of $\\mathcal{R}',\\mathcal{P}'$, we see that $x - z \\in D_1$, where $D_1$ is the set in eqn (3.2).\n\nThe set $D_2$ in eqn (3.2) comes later in the proof. We decompose $\\mathcal{P}'$ into a mixture over the balls mentioned above. After a series of steps, we reduce the problem to considering the probability that the conditional distribution is drawn from one ball when the prior is drawn from another. Lemmas C.4-C.5 handle this. They involve estimating the action of $A$ on vectors $z - x$, where $z$ is the centre of one of the balls and $x$ comes from another ball. Since the balls are supported in $\\mathrm{supp}(\\mathcal{P})$ we have $x \\in \\mathrm{supp}(\\mathcal{P})$ and since the come from the approximate covering number bound (3.1), $z \\in \\mathrm{supp}(\\mathcal{P})$ if $\\mathcal{P}$ attains the minimum and $z \\in \\mathrm{supp}(\\mathcal{R})$ otherwise. Hence $z - x \\in D_2$, with $D_2$ as in (3.3).\n\n## Wherever you have...\n\nExcellent question. The short answer is no: we did mean to write $\\mathrm{supp}(\\mathcal{P}) - \\mathrm{supp}(\\mathcal{P})$. The key point is that if $\\mathcal{P}$ attains the minimum in (3.1) then the set $D_2$ in (3.3) depends on $\\mathcal{P}$ only.\n\nRecall that $\\mathcal{R}$ is the 'real' distribution, which is typically unknown, whereas $\\mathcal{P}$ is the 'approximate' distribution and is known. It is convenient to have results in terms of $\\mathcal{P}$, as this means the terms appearing in the recovery guarantees can be estimated numerically or theoretically. We discuss this further below.\n\nAs an aside, note that whether $\\mathrm{supp}(\\mathcal{P}) - \\mathrm{supp}(\\mathcal{R})$ or $\\mathrm{supp}(\\mathcal{P}) - \\mathrm{supp}(\\mathcal{P})$ arises is determined by which set $\\mathcal{R}$ or $\\mathcal{P}$ has smaller covering number. See eqn (3.1). This arises because it is the smallest set over which our concentration bounds are formulated. As we commented in Remark 3.2, one cannot generally expect good concentration bounds over the whole of $\\mathbb{R}^n$. Therefore, it is important to formulate them over as small sets as possible.\n\nWe believe it is useful to have results in terms of $\\mathcal{P}$ only. First, if $\\mathcal{P}$ is a generative model, we can estimate its approximate covering number analytically. See Proposition 4.1. Second, in Thm 3.8 the coherence in (3.5) is taken over $D = \\mathrm{supp}(\\mathcal{P}) - \\mathrm{supp}(\\mathcal{P})$. This has several benefits. First, one can derive analytical bounds in some cases. For example, [14] does this for ReLU generative models with random weights and biases. Second, one can estimate it empirically by, e.g., drawing a large sample from $\\mathcal{P}$ and replacing the supremum in Defn 3.7 by a maximum. This allows one to gauge empirically how well one can recover with a given $\\mathcal{P}$. Note that this may not be possible if one considered $\\mathcal{R}$, as we may not be able to sample from it.\n\nWe agree this point should be better highlighted. **We will add a comment about this after Thm 3.8.**"}, {"review_id": "hsET4YqpUS", "reviewer": "Reviewer_maR6", "summary": "This paper studies the sample complexity to recover the true parameter with controlled accuracy in linear Bayesian inverse problems. It gives the sufficient conditions for Bayesian recovery for arbitrary real and approximate prior distributions, and forward and noise distributions. It establishes a non-asymptotic bound for sample complexity depending on the prior complexity (approximate covering number) and the concentration bounds for the forward and noise distributions. Then it applies to particular scenarios such as subgaussian measurements and subsampled orthogonal transforms with specific bounds.", "questions": "Here are a few minor questions/suggestions:\n\n* line 280, why $\\mathbb{E}(A^*A)=I$? What I can tell $A^*A$ has at most rank $q$. To show $A$ is isotropic, $\\sqrt{n/m}$ ensures $\\mathrm{tr}(\\mathbb{E}(A^*A))=\\mathbb{E}(q)=m$, which is enough. I do not think $\\mathbb{E}(A^*A)=I$ holds or is needed.\n* Bring the definition of 'near-optimality' from line 318 to line 106 when it was mentioned for the first time.\n* line 216: based on lemmas B.2 and B.3, did you mean $\\log(C_{low}), \\log(C_{upp}) = \\mathcal O(t^{-2})$? Is a symbol $\\mathcal O$ missing in front of $(t-1)^{-2}$?\n* $\\varepsilon$ is not defined in Theorem 1.1. Add one before $\\eta>0$ so it reads as $\\varepsilon, \\eta>0$.\n* line 95: typo: 'achieve' $\\to$ 'achieved'.\n* line 163: 'be' and 'arise' are duplicate, remove one.\n* line 209: $C_-$ $\\to$ $C_{low}$.\n* line 213: $\\mathbb{P}$ $\\to$ $\\mathbb{P}_{A\\sim \\mathcal A}$.\n* line 253: $C_{low}(2\\sqrt{2}/\\sqrt{2};\\mathcal{A}, D_2)$ $\\to$ $C_{low}(2\\sqrt{2}/\\sqrt{c};\\mathcal{A}, D_2)$.\n* line 584: $x\\in B_\\eta(x_i)$ $\\to$ $z\\in B_\\eta(z_i)$.", "limitations": "yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "# Strengths:\n\n* This paper address the core question in Bayesian (linear) inverse problems on how many samples required to recover the truth.\n* The sample complexity bounds apply to general real and approximate prior distributions, and forward and noise distributions.\n* Its conclusion could potentially help resolve the \"hallucinations\" in deep learning.\n\n# Weaknesses:\n* Section 1.2 seems redundant given Sections 3.1 and 3.2.\n* It should be properly emphasized that concentration bounds ($C\\_{low}, C\\_{upp}$) exponentially decay. The probability upper bound right above (3.2) appears to be large (notice the $e^k$ term) and readers might doubt whether it is a useful bound (smaller than 1).\n* BTW, I understand the bounds are non-asymptotic; but it might help with the understanding if the authors could elaborate the asymptotic behavior of these probability bounds (e.g. $\\delta$) when $m\\to \\infty$ or $m\\to n$? Do they tend to 0?\n* Difference set $\\Sigma-\\Sigma$ (line 252) is not a standard notation and should be explicitly defined. I assume the author(s) meant for $\\\\{x-y: x, y\\in \\Sigma\\\\}$, not $\\Sigma\\backslash\\Sigma=\\emptyset$ as interpreted by convention. There are instances like this spread over the paper without a clear definition.", "was_revised": true, "final_justification": "Very good theory paper. I concur with other reviewers on the score and keep it.", "rebuttal": "We very much appreciate your effort in reviewing our paper and are delighted by your positive assessment. Here we address the comments in your report.\n\n# Weaknesses:\n\n## Section 1.2 seems redundant...\n\nThanks for this comment. We agree there is overlap between the sections. The aim of §1.2 is to present simplified versions of the main results that the reader can more easily digest without reading all the technical setup. §3.1,3.2 present the main results in full technical detail. We feel this style of presentation, despite some redundancy, makes it easier for the reader. It is also quite common, in our experience, for papers to adopt this style. For this reason, we prefer to keep it. \n\n## It should be properly emphasized...\n\nExcellent comment. This was also mentioned by reviewer b54M. **We will add the following remark about this immediately after Theorem 3.1:**\n\n\"Since Theorem 3.1 considers arbitrary measurement $\\mathcal{A}$ and noise $\\mathcal{E}$ distributions, the number of measurements $m$ does not explicitly enter the bound. For typical distributions, a dependence on $m$ is found in the concentration bounds $C_{\\mathsf{low}},C_{\\mathsf{upp}},D_{\\mathsf{upp}}$, as well as the terms $D_{\\mathsf{shift}}$ and $C_{\\mathsf{abs}}$. In particular, the former decay exponentially-fast in $m$ for the examples introduced in §1.2 and therefore compensate for the exponentially-large scaling in $k$ in the main bound. See §B for precise estimates. See also the discussion in §3.1 and 3.2 below.\"\n\n## BTW, I understand the bounds are non-asymptotic...\n\nGood comment. **We will add the following after Theorem 3.5:**\n\n\"It is worth at this stage discussing how the bound (3.4) behaves with respect to the various parameters. First, suppose that $\\eta$ decreases so that the error bound becomes smaller. Then $\\mathrm{Cov}_{\\eta, \\delta}(\\cdot)$ increases, meaning, as expected, that more measurements are required to meet (3.4). Second, suppose that $\\delta$ decreases, so that the failure probability shrinks. Then $\\mathrm{Cov} (\\cdot)$ and $\\log(1 /\\delta)$ both increase, meaning, once again, that more measurements are needed for (3.4) to hold. Both behaviours are as expected.\"\n\nYou raise an interesting point regarding the regime $m \\approx n$. Intuitively, one expects good recovery here, as there are as many, or even more, measurements $m$ as unknowns $n$. This is not reflected by our analysis. Our analysis is intended for the highly underdetermined regime, i.e., where the RHS of (3.4) is much smaller than $n$. However, it is conceivable that the RHS of (3.4) could be much larger than $n$ if, say, $\\mathcal{R},\\mathcal{P}$ had large approximate covering numbers.\nWe believe it may be possible to derive a bound that covers both regimes $m \\ll n$ (our bound) and $m \\approx n$. This is an interesting question for future work.\n\n\n\n\n## Difference set $\\Sigma - \\Sigma$ (line 252) is not...\n\nThanks for pointing this out. We do mean $\\Sigma - \\Sigma = \\{ x - z : x,z \\in \\Sigma \\}$. We agree this could be misinterpreted. Since this notation is first used in line 50, **we will add the following there:**\n\n\"Here, and throughout this paper, we write $S - S = \\{ x_1 - x_2 : x_1,x_2 \\in S \\} \\subseteq \\mathbb{R}^n$ for the difference set associated with a set $S \\subseteq \\mathbb{R}^n$.\"\n\n## There are instances like this...\n\nThanks. We have checked the paper and found several other instances. In particular, the norm $\\lVert  \\cdot \\rVert $ in the equation below line 49 is not defined until later (it is the Euclidean norm) and the norm $\\lVert \\cdot \\rVert_{\\infty}$ in the equation below line 93 is not defined (it is the infinity-norm). Also, we ought to state explicitly in line 50 that $\\mathrm{supp}(\\mathcal{P})$ is the support of the measure $\\mathcal{P}$. **We will make these changes. We will also carefully check through the whole paper to make sure everything is properly defined.**\n\n# Questions:\n\n## line 280, why $\\mathbb{E}(A^* A) = I$?\n\nWe believe the factor $\\sqrt{n/m}$ is needed. With this factor, we can write\n\n$$\n\\mathbb{E}(A^\\top A) = \\frac{n}{m} \\mathbb{E} \\left( \\sum_{j=1}^{q} u_{i_j} u^\\top_{i_j} \\right) = \\frac{n}{m} \\mathbb{E} \\left( \\sum_{i=1}^{n} X_i u_i u^\\top_i \\right)\n$$\n\nwhere $X_i \\sim \\mathrm{Ber}(m/n)$, as in Definition 3.6. Since $\\mathbb{E}(X_i) = m/n$, we get\n\n$$\n\\mathbb{E}(A^\\top A) = \\frac{n}{m} \\sum_{i=1}^{n} \\frac{m}{n} u_i u^\\top_i = \\sum_{i=1}^{n} u_i u^\\top_i = U^\\top U = I\n$$\n\nas required. We may have misunderstood your question. **Please let us know if we can provide further clarification.**\n\n\n\n## Bring the definition of 'near-optimality'...\n\nThanks. **We will do this.**\n\n## line 216: based on lemmas B.2....\n\nApologies. We discovered this result is incorrect. For $C_{\\mathsf{upp}}(t ; \\mathcal{A} , \\mathbb{R}^n)$ one does indeed have $C_{\\mathsf{upp}}(t ; \\mathcal{A} , \\mathbb{R}^n) = O(t^{-2})$ for any (isotropic) distribution $\\mathcal{A}$. This follows straightforwardly from Markov's inequality. However, one does not necessarily have $C_{\\mathsf{low}}(1/t ; \\mathcal{A}, \\mathbb{R}^n) \\rightarrow 0$ as $t \\rightarrow \\infty$ without further assumptions. **We will delete this sentence.**\n\n\n## $\\varepsilon$ is not defined in Theorem 1.1...\n\nThanks. **We will add this.**\n\n## Other comments\n\nThanks for pointing out these typos. **We will fix these.**"}, {"review_id": "znwPYkkFGV", "reviewer": "Reviewer_h9UA", "summary": "The authors provide a number of theoretical results with respect to sample complexity in Bayesian recovery. Namely, they show that sample complexity depends on the the intrinsic complexity of the prior and the concentration bounds for the forward operator and noise distributions. Overall, the authors unify prior theoretical work providing guarantees for the sample complexity of solving Bayesian inverse problems.", "questions": "See strengths and weaknesses.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nS1) The paper is very well-written and easy to follow.\n\nS2) The authors present a set of theoretical results which are thorough and (as far as I can tell) correct.\n\nS3) The theoretical contribution is meaningful and worthy of publication at NeurIPS.\n\n**Weaknesses**\nW1) While I understand that this is work is entirely a theoretical contribution, it would still be worthwhile to show simple experiments that demonstrate the proposed theory in practice. While this is not necessarily required, it would be further elevate the work.", "was_revised": true, "final_justification": "After reading other reviews + all rebuttals, I will keep my score the same. This is an impactful theoretical work worthy of acceptance.", "rebuttal": "We very much appreciate your effort in reviewing our paper and are delighted by your positive assessment. Here we address the comments in your report.\n\n## W1) While I understand that this is work is entirely a theoretical contribution, it would still be worthwhile to show simple experiments that demonstrate the proposed theory in practice. While this is not necessarily required, it would be further elevate the work.\n\nThanks for this comment. We wholeheartedly agree, and we are about to commence working on numerical implementations and developing a series of numerical experiments that demonstrate our theoretical results. We hope to report on these in the near future. However, we do not think doing so is feasible for this paper, given the tight deadlines and the space limitations. A particular issue is that practical posterior sampling algorithms are still very much an active area of inquiry. Please see our reply to reviewer b54M for more on this point. As a consequence, numerical implementations of posterior sampling are not 'simple', and therefore one has to be careful to ensure empirical verification of the theory is not obfuscated by numerical issues, e.g. lack of convergence of algorithms, parameter choices, and so forth. For this reason, we prefer to take more time to conduct a more rigorous and comprehensive study.\n\nNonetheless, we agree this is an vital topic for future work. **We will add some more discussion on this in the final paragraph of §5 (\"Limitations an future work\").**"}]

Author rebuttal:

Meta-review: The authors establish recovery guarantees for linear inverse problems with prescribed prior for the unknown when both the measurement operator and noise follow arbitrary distributions.  They specialize their approach to obtain guarantees in cases where forward operators are subgaussian matrices and subsampled orthonormal transforms, and finally tackle particular cases of Lipschitz-continuous generative models and sparse vectors. The paper was referred by four reviewers who all recommended acceptance, and I do so too.
Decision: Accept (spotlight)