Generalized Compressed Sensing for Image Reconstruction with Diffusion Probabilistic Models
Authors: Ling-Qi Zhang
Zahra Kadkhodaie
Eero P Simoncelli
David H. Brainard
Venue: Accepted by TMLR ()

Abstract: We examine the problem of selecting a small set of linear measurements for reconstructing high-dimensional signals. Well-established methods for optimizing such measurements include principal component analysis (PCA), independent component analysis (ICA) and compressed sensing (CS) based on random projections, all of which rely on axis- or subspace-aligned statistical characterization of the signal source. However, many naturally occurring signals, including photographic images, contain richer statistical structure. To exploit such structure, we introduce a general method for obtaining an optimized set of linear measurements for efficient image reconstruction, where the signal statistics are expressed by the prior implicit in a neural network trained to perform denoising (known as a ``diffusion model''). We demonstrate that the optimal measurements derived for two natural image datasets differ from those of PCA, ICA, or CS, and result in substantially lower mean squared reconstruction error. Interestingly, the marginal distributions of the measurement values are asymmetrical (skewed), substantially more so than those of previous methods. We also find that optimizing with respect to perceptual loss, as quantified by structural similarity (SSIM), leads to measurements different from those obtained when optimizing for MSE. Our results highlight the importance of incorporating the specific statistical regularities of natural signals when designing effective linear measurements.

Published in Transactions on Machine Learning Research (05/2025)
Generalized Compressed Sensing for Image Reconstruction with Diffusion Probabilistic Models
Ling-QI Qi Zhang
shangl5@@jeneiia.hhm...o
Janelia Research Campus, Howard Hughes Medical Instätute
Zahra Kadkhodaic
Flatéron Institute, Simons Foundation
Eero P. Simoncelli"
eenossmooneell@@myu.ddd
New York University
Flatiron Institute, Simons Foundation
David H. Brainard*
Trainard@@ssych..upen.. edu
University of Pernsylounia
Reviewed on OpenReview: https: // // opereeviee id- LmFP
Abstract
We examine the problem of selecting a small set lincar measurements for reconstruct- ing high-dimensional signals. Well-established methods for optimizing such measurements include principal component analysis (PCA), independent component analysis (ICA) and compressed sensing (CS) based on random projections, all of which rely axis- subspacc- aligned statistical characterization of the signal source. However, many naturally occurring signals, including photographic images, contain richer statistical structure. To exploit such structure, we introduce a general method for obtaining an optimized set of linear measure- ments for efficient image reconstruction, where the signal statistics are expressed by the prior implicit in a neural network trained to perform denoising (known as a "diffusion model"). We demonstrate that the optimal measurements derived for two natural image datasots differ from those of PCA, ICA, CS, and result in substantially lower mean squared construction error. Interestingly, the marginal distributions of the measurement values are asymmetrical (skewed), substantially more so than those of previous methods. We also find that optimizing with respect to perceptual loss, as quantified by structural similarity (SSTM), leads to measurements different from those obtained when optimizing for MSF. Our results highlight the importance of incorporating the specific statistical regularities of natural signals when designing effective lincar measurements.
1 Introduction
The natural world contains inherently high-dimensional spatial and temporal signals, but imaging systems such as cameras and microscopes typically capture only partial, lower-dimensional linear measurements of these signals. Maximizing the informativeness applications (Pruessmaun al., 1999; Lustig et al., 2007; Zhu et al., 2018; Nehme al., 2020; Deb et al., 2022). This raises a fundamental question: What is the optimal set of low-dimensional linear measurements for given class of signals?
these measurements critical for many real-world
To address this question, we first need to consider the task of reconstructing the original signal from set of linear measurements, referred to as a "linear inverse problem". In the general case, where the number of
"These authors contributed equally this work. Code available himbubbbomm/innggg///pmmmaal measuremet.

---

Published in Transactions on Machine Learning Research (05/2025)
available measurements is smaller than the dimensionality of the signals to be reconstructed, the problem is underdetermined. Thus, obtaining a solution requires addit ional constraints that, either explicitly or implicitly, incorporate assumptions about the structure of the signal distribution. In the Bayesian formulation of the problem, the signal structure is expressed as a prior probability distribution over the signal space. This is combined with the measurement constraints (i.e., likelihood function) to obtain a posterior distribution, from which the reconstructed signal computed, typically by minimizing an expected loss.
In its most common form, one assumes Gaussian signal prior, and mean squared error (MSE) loss. In this case, the optimal set of linear measurements are the most significant principal components (PCs), and the optimal reconstruction is the linear projection onto those PCs. Although this formulation is foundational, the Gaussian prior describes only the second-order statistical regularities of signals, and falls short of capturing important higher-order dependencies of many natural signal ensembles, particularly photographic images.
More recently, an alternative framework for optimal lincar mcasurements arose from the use of separable priors with sparse (heavy-tailed) marginals. The seminal work by Donoho (2006) in compressed sensing (CS) proved that when the signal lies within union of subspaces (an idealized form of separable sparse prior), the optimal measurements should be incoherent with the axes of these subspaces, which can be implemented in practice using a set of randomly chosen vectors. In this setting, an iterative non-linear reconstruction can achieve near-optimal recovery (Tropp, 2006). The sparse prior provides a reasonable model for some signal classes, such as medical images, for which compressed semsing leads to significant empirical improvements over PCA methods. This advance highlights the importance of the signal prior in the design of effective linear measurements, as well as for the reconstruction algorithm.
The statistical characterization undcrlying PCA and CS assumes alignment of signal content with particular coordinate system, but this assumption does not adequately capture the statistical structure of natural images (Portilla et al., 2003b; Ballé et al., 2016). In support of this, previous work (Weiss et al., 2007) has demonstrated that although random measurements outperform PCs for idcalized sparse signals, this does not hold for natural images. Over the past decade, deep neural networks (DNNs) trained for image processing lasks have been able to exploit ever more complex icall structure, often described terms of low-dimensional manifolds. Utilizing the priors implicit in these networks has led to substantial performance improvements in solving linear inverse problems (Romano et al., 2017b; Bora et al., 2017; Kadkhodaie & Simoncelli, 2020; Song et al., 2021). These dramatic performance improvements suggest that the DNN-based priors can more faithfully capture the statistical structure of natural images.
Here, armed with the prior implicit in a DNN trained for denoising (hercafter a "denoiser prior"), we re-visit the question of optimal linear measurement for natural images. Specifically, we develop a framework for optimizing set of lincar mcasurements to minimize the error obtained via non-linear image reconstruction under the denoiser prior. More specifically, our reconstruction algorithm uses a generative diffusson model based on trained DNN image denoiser. This enables us to apply our method to natural images and to analyze the impact of natural image statistics on the optimal linear measurements. We demonstrate that these measurements (1) vary substantially with the training dataset (e.g., digit vs. face images); (2) vary with the choice of reconstruction loss (e.g., MSE vs. SSIM); (3) are distinct from those of PCA, ICA and CS, with substantially more asymmetrical marginal distributions; and (4) lead to substantial performance improvements over PCA and CS. This work provides yet another cxample of the impressive improvements that can be achieved by applying modern ML methods to fundamental problems in signal processing, Our findings also establish a critical baseline for evaluating the potential benefits of non-linear measurements and the impact of measurement noise on the reconstruction of natural signals.
2
Optimized Linear Measurement (OLM)
2.1 Linear inverse problem
Given an image x E Rd, we express a linear measurement as m = MM x, where Me E Rdxk is a measurement matrix, and m E R* is the measurement which provides partial observation of x (i.c., M, is low rank, k < d), We assume m noise-free. The linear inverse problem is to reconstruct an approximation of the original image from the measurement, (mm), where &(-) can be noulinear.
2

---

Published in Transactions on Machine Learning Research (05/2025)
We take Bayesian statistical approach to solving the inverse problem, in which prior distribution of the signal, p(z), characterizes the statistical regularities of z. Given partial observation m, one can obtain a posterior distribution, p(z/m), and the inverse problem is formulated to minimize an expected loss over this posterior. For squared error loss, the solution is the conditional mean of the posterior, f(m) = [xpx=|m) dr, and for a. "0-1" loss, is the mode, f(m) = arg max p(z[mm. These solutions are known as minimum mean squared error (MMSE) and maximum a posteriori (MAP) estimates, respectively. More recently, stochastic sampling approaches for solving inverse problems have emerged, where the reconstruction is not the mean maximum of the posterior, but high-prod high-prroabillty sample (Kadkhodaie & Simoncelli, 2020; Kawar et al., 2022; Chung et al., 2022). We describe the stochastic solution in more detail next.
2.2 Image prior embedded in denoiser
Traditionally, image priors were constructed by using simple parametric forms (Geman & Geman, 1984; Lyu & Simoncelli, 2008; Zoran & Weiss, 2011). Improvements in these priors led to steady progress over several decades. Over the last decade, however, the emergence of deep learning has made it possible to learn sophisticated priors from data. In particular, ccore-based diffusion models have exhibited incredible success in drawing samples from learned image priors. Scoro- diffusson models are deep neural networks trained to remove Gaussian white noise by minimizing the mean squared error between the clean and denoised images. The learned denoiser is applied partially and iteratively, starting from sample of Gaussian noise to generate an image. The generated image is sample from the image prior embedded in the denoiser. The connection between denoising function and prior is made explicit in Tweedie's equation (Miyasawa, 1961; Robbins, 1992; Raphan & Simoncelli, 2007; Vincent, 2011; Efron, 2011):
a(y) - o (v)
(1)
020, and ((v) is the MMSE denoising solution. This remarkable equation provides explicit connection between denoising and the densily of the noisy image (y). See Appendix A for the proof of Equation (1). The distribution of noisy images, Po is
where y is the noise-corrupted signal: y x
related to the image prior p(z) through marginalization:
Po Po(y)= - plulo) p(a) de =
fgolv goly 2) p(x) dx,
(2)
where go is the distribution of Gaussian noise with variance a². This equation expresses the convolution of p(x) with the Gaussian probability density function. That is, Po is a blurred version of p(x) where the extent of blur depends on a. The family of (v) over all > 0 forms a scale-space representation of p(x) and is akin to the temporal evolution of diffusion process of p(z). A learned denoiser trained over wide range of approximates this family of gradients of log densities and can then be used in a coarse-to-fine gradient ascent algorithm to sample from p(r) (see Algorithm 1).
2.3 Inverse problem as constrained sampling
To utilize the prior for solving inverse problems, the diffusion sampling algorithm can be modified to handle linear constraints. To draw samples from the denoiser prior given the partial linear measurements m = M x, the score of the conditional distribution, V, log Po (y)m), ,. is used instead. The conditional score can be written as the following partition (Kadkhodaic & Simoncelli, 2021):
Vy lologPo(ulla = My(m ME of + (T M,ME), log (v).
(3)
See Algorithm 2 for a detailed description of the constrained sampling algorithm.
Images obtained using this algorithm are high-probability samples that are consistent with the measurements from the prior embedded in the learned denoiser. Notice that these sampling-base solutions to the inverse problem are not unique, and do not typically minimize mean square error: the MMSE estimate is a convex combination of these samples, and thus will not generally lie on the manifold of natural images from which the conditional samples are drawn. The MMSE estimator is
h(m; M&) Ry Eujm [2]
(4)
3

---

Published in Transactions on Machine Learning Research (05/2025)
which can be approximated by averaging over multiple conditional samples for given mcasurement model Me, see Appendix E.3 for more details. Visually, however, individual samples will look sharper and of higher visual quality compared to the MMSE estimate (Kadkhodaie & Simoncelli, 2021; Kawar et al., 2022).
2.4 Optimized linear measurement
We solve mumerically for the set of k linear measurements that minimize the average error of reconstruction through conditional sampling of the posterior. We define a loss function to measure the performance of our MMSE estimate, h(m; M&):
C(M2) Ez [[h x; Ms) - xx|2 }. -x|1
(5)
which approximated by averaging over training set of images. The Optimized Linear Measurement (OLM) matrix, is computed by minimizing the loss:
M argmin ((M+)
(6)
Ma:M M
for given choice of k. Here, without loss of generality, we consider only matrices Mr with orthonormal columns (i.e., M M₁ = I).
In order to solve the optimization problem Equation (6), we use stochastic gradient descent in the space of orthonormal matrices. Specifically, we parameterize the set of matrices Q E Rd with orthonormal columns using the Houscholder product, which represents matrices as a sequence of clementary reflections the following (Trefethen & Bau, 2022; Shepard et al., 2015):
Q = H, H2...Hg, where H; I 7,00
Here, each elementary reflector H; defines reflection around a plane. Each vector U; is of the form (0, u,] with the first i - elements being zero, and т; is scale factor: = 2/(1 + ||u;1(²). The collection of us's forms lower triangular matrix of Rdxk They are the free parameters 6 of the parameterization ((Ø). We can thus search for measurement matrices in the space of Φ.
We re-write our empirical objective function from Equation (5) using the parameterization Q(Ø):
( = N Σ [n(Q(6)Taz; Q(6)) - -r,1/2
(8)
We search for the optimal measurement matrix within Q(Ø) through variants of gradient descent (Adam optimizer (Kingma & Ba, 2014), see Supplementary Appendix E):
Φ t- di - -
Vor
(9)
In practice, the gradient C(o)( is approximated by computing the MSE (Equation (8)) on subset of images sampled from the training set on each iteration. The gradient descent formulation is general, and applicable to any differentiable objective. As demonstration of this, also explore perceptual loss function, the structural similarity index measure (SSTM) (Wang et al., 2004), using the implementation in Detlefsen et al. (2022). See Appendix E for details of the datasets, network training, and linear measurement optimization.
3 Results
3.1
Two-dimensional example
signal As an illustration of our method, consider 1-D measurement problem 2-D signal space, for three different prior probabilitics (Figure 1A): a correlated Gaussian distribution, a K-sparse (union of subspace) model, and a tight distribution along a closed ID manifold. In each case, we train a small, two-layer fully connected denoising network the data distribution, which is then used solve the inverse problem via. Algorithm 2.
4

---

Published in Transactions on Machine Learning Research (05/2025)
A
C
1.0
Mean Squared Error
Denoiser
Projection
1,0
Test Data Samples MMSE
Optimized Angle
0.14
0.5
x2 0.0
0.10
x"
-0.5
-1.0
0.02
-1.0
Mean Squared Error
0.30
0.5
0.20
X,
x 0.0
-0.5
0.10
-0.5
0.00
Mean Squared Error
-1.0
0.30
-1.0
X2 0.0
0.20
X 0.0
1.0
0.10
1.0
X,
Measurement Angle
X
Figure/ Reconstruction of 2-D signals from 1-D linear measurement. Top row: Gaussian distribution. Middle row: K-Sparse distribution. Bottom A data distribution confined to curved one-dimensional manifold. A) Samples from the target distribution (blue points). Measurements between samples and unit vector (black vector) parameterized by angle 6. B) Mcan squared error (MSE) of sample reconstruction as function of measurement angle 0, for two estimators: linear projection onto the measurement vector (blue), and reconstruction using the denoiser prior (orange). The dashed vertical line indicates the optimal solution, 8*, obtained with our optimization procodure (basod on Equation (8)). C) Test data drawn from the prior (blue), plotted in new coordinate system (zf.z}) rotated by -0" (i.e., such that the optimal measurement, corresponds to the horizontal coordinate xi)) Example bivariate estimates sampled from the denoiser prior conditioned the optimal linear measurement are plotted in red. The MMSE solution (orange) is obtained by averaging over multiple conditional samples.
obtained via dot product
The mean squared reconstruction error obtained by this method function of the measurement vector angle is shown in Figure 1B (red). As baseline, compare this to the reconstruction obtained by linear projection onto the measurement axis (Figure 1B, blue). The optimal measurement vector is obtained by evaluating the reconstruction error for a set of densely sampled 2-D unit measurement vectors spanning orientations E [-n/2,,//' x/2] (Figure 1B, orange). For the optimal measurement vector, Figure 1C shows samples conditioned on each measurement value (red points) and the MMSE solution a function of the measurement value (orange line).
We first consider bivariate Gaussian distribution (Figure 1, top row). In this case, the first PC is the optimal measurement for both reconstruction methods, expected for a Gaussian prior. The second row of Figure depicts the result. for a union-of-subspace sparse distribution. Here, the first PC is aligned with the horizontal axis. However, the optimal measurement vector for the denoiser prior is dramatically different. The reconstruction crror at the optimal 8* is near zero. This recapitulates the classical compressed sensing result (Donoho, 2006; Tropp, 2006) that for sparse signals, improved estimates can be achieved by making off-axis measurements.
5

---

Published in Transactions on Machine Learning Research (05/2025)
The last row illustrates the scenario of primary interest in this paper: The data distribution lies in low-dimensional but curved manifold. This type of higher-order structure cannot be adequately captured by either the Gaussian or sparse prior, but can be effectively described using the more powerful diffusion models, such as our denoiser prior (Supplemental Figure 2). Notably, in this case, we also identified an optimal measurement angle that outperforms the principal axis. Importantly, the optimal angle 0* is correctly identified by our optimization method across all three cases, illustrating the generality of our approach.
Finally, we highlight another aspect of the reconstruction demonstrated by the 2D examples (Figure 1C). Our methods generate estimates by sampling from the denoiser prior, conditioned on the linear measurements. While individual samples are consistent with the conditional prior, the MMSE solutions are obtained by averaging multiple conditional samples. This averaging, however, can cause deviations of the MMSE solution from the prior. In the context of image reconstruction, the MMSE solution often exhibits lower visual quality (e.g.; blurrier images) compared to individual conditional samples, as it does not lie close to the image prior manifold (Kadkhodaic & Simoncelli, 2021; Kawar et al., 2022). This observation is particularly relevant in the results presented below and further motivates our approach of optimizing measurements with respect. to perceptual loss function later.
3.2 Optimized measurements for MNIST
Original
PC Projection
PC Denoiser Prior
OLM Denoiser Prior
8
8
O
9
0
3
6
k=1
6
C
8
6
S
5
k=2
8.80
11.02
11.12
# of Measurement
8
5
0
8
8
8 12.59
k
11.72
0
8
0
8
8
8
k=8
12:26
12:16
13.03
8
8
8
8
8
8
8 21.23
==16
13:41
16.45
k=4
10:48
14.05
15.05
of Measurement
k=8
14.62
15.01
16.63
k 16
17:13
18.07
20.80
k 32
18.86
22.54
22.56
k = 64
20.21
24.02
25.01
Figure 2: Example image reconstructions using different measurement matrices. Columns show the PC projection, three conditional samples from the denoiser prior using the PCs, and three samples using the OLMs, respectively. Rows correspond to incrcasing number of measurements, k. The numbers indicate the PSNR value of the reconstructions, obtained by averaging over 16 samples. Red boxes highlight examples showing significant visual improvement of the OLM relative to the PC measurements. Top: denoiser trained on (and test example drawn from) the MNIST dataset. Bottom: denoiser trained on the CelebA dataset.
6

---

Published in Transactions on Machine Learning Research (05/2025)
We used our method to obtain optimized measurements for the MNIST dataset (Deng, 2012). We first trained a DNN denoiser on these digit images for details of the architecture and training, see Appendix E. We apply our method as described in Section 2.4 to obtain the optimized measurement matrix (OLM) for this dataset, for a range of l values.
For comparison, we apply our reconstruction method to two other types of linear measurements: the top k PCs, and k random vectors, which are optimal measurements under Gaussian and sparse prior assumptions, respectively. We also compare to the optimal reconstruction for Gaussian prior, which is simply linear projection onto the space spanned by the top k PCs. The top half of Figure 2 illustrates test digit image. First, we observe that combining the PCs with the denoiser prior significantly improves the linear inverse estimates, which reflects the power of the denoiser prior. All conditional samples from the denoiser prior appear to be real MNIST images, which then gradually converge to the original image as k increases. Use of the optimal measurement matrix (OLM) offers additional improvements, reconstructing the correct digit with smaller k. These improvements are evident in both the identity of the digits and their more detailed appearance. Using random measurements (not shown) does not perform as well either the optimized linear measurments or PCA. See Supplemental Figure 3 for two more examples, including random mcasurement vectors.
results for a
MNIST
CelebA
A
Prior Pitor
B
50
40
Projection
PSNR, PC Phior
PSNR, PC + Prior
34
Prior
4.22
0.44
40
35
PSNR
233
PSNR
30-
30
30
9.12
25
20
26
k = 64
k = 512
32
128
512
20
25
30
64
256
1024
4096
26
30
34
# of Measurements (k)
PSNR, OLM Prior
# of Measurements (k)
PSNR, OLM Prior
Figure 3: Performance comparisons for A) MNIST and B) CelebA datasets. Left graph in each panel shows the peak signal-to-noise ratio (PSNR, in dB) as a function of the number of measurements k, for the denoiser prior reconstruction from OLMs (red), denoiser prior reconstruction from PCs (orange), linear (projection) reconstruction from PCs (blue), and denoiser prior reconstruction from random measurements (green). Inline numbers indicate the increase in PSNR from PC + denoiser prior to OLM + prior. The right graph in each panel plots the PSNR of the PC reconstruction against that of the OLM reconstruction over all images in the test set, for a value of k approximately 10% of the total number of pixels. Red points indicate the examples shown in Figure and Supplemental Figure 3 and Figure 4. Also see Supplemental Table for comparison of our results to other previous methods.
We quantify our results in terms of peak signal-to-noise ratio (PSNR), as function of k in the left panel of Figure 3A. The OLMs result in superior reconstruction (red curve), particularly for the values of k ranging from 1% to 30% of the total number of pixels. The peak performance gain of OLM over PC (both utilizing denoiser prior) reached 4.72 dB in PSNR at k = 256. Between the two PC reconstructions, the nonlinear prior- prior-based method (orange) shows a considerable improvement over linear reconstruction (blue), demonstrating the substantial advantage of using the more complex denoiser prior. See Supplemental Table for a comparison of our results to other methods the litcrature. Lastly, consistent with previous reports using simpler image priors (Weiss et al., 2007), we observe that PC measurements outperform random measurements when used with the denoiser prior (green). This raises the possibility that the union of subspace prior assumed in the compressed sensing literature (Donoho, 2006) does not fully capture the structure of these images, since random measurements are expected to perform well if the images indeed lie on a union of subspaces - a structure that we believe the denoiser prior is expressive enough to capture.
In addition to the average performance, we also compare the performance of these methods on individual images in the right panel of Figure 3A, in a scatter plot of the reconstruction errors from measurements using PCs versus those obtained using OLMs. Tn both cases, nonlinear reconstruction was performed using
7

---

Published in Transactions on Machine Learning Research (05/2025)
the denoiser prior; thus the plot highlights the differences due to the linear measurements. Importantly, we observe improvement in performance for almost all images in the test set for the OLM.
3.3 Optimized measurements for CelebA
To Lest the generality of our method for different image classes, repeated our experiments on the CelebA dataset (Liu et al., 2015); which consists of about 200, 000 centered face images. We resized all images to 80 x 80 and converted them to grayscale. The rest of the procedure is the same as described above. The bottom half of Figure 2 shows an example face image from the test set. Similar to the MNIST case, we observe that using the denoiser prior to reconstruct from PCs significantly improves the linear inverse estimates. Notably, the conditional samples all appear to be realistic face images even for low k;; this indicates that the denoiser prior adequalely caplured the statistical structure of this image dataset. As k increases, the reconstructed face images increasingly resembles the original. Optimizing the measurement matrix offers further improvements in the results, in this case most visible for k = 16. See Supplemental Figure 4 for two more examples, including reconstructions obtained with random measurements.
The effect of the optimized measurements is quantified in Figure 3B. As with the MNIST dataset, we observe that OLM leads to superior reconstruction using the denoiscr prior, illustrated by the red curve in the left panel. The improvements arising from OLM measurements are consistent across all values of k, although they are smaller than for the MNTST case. The peak difference in this case is 0.44 dB in PSNR at k 2048. Thus, the performance gain between PCA and OLM also depends the specific image dataset.
Consistent with results on MNIST, reconstruction from PCss using the denoiser prior results in higher perfor- mance than linear reconstruction, and all of these methods outperform reconstruction from random measure- ments. We confirmed that the improvements from the OLM are nearly universal for all images in our test set (Figure 3B, right pancl). For completeness, we also used independent component analysis (ICA, Hyvärinen & Oja 2000) generate linear measurement vectors. On both datasets, we found that reconstructions using the denoiser prior based on ICA measurements were marginally worse than those using the PCs (not shown).
3.4 Characterizing the optimized linear measurements
In this section, we present some qualitative and quantitative analyses to help interpret the difference between the lincar measurement subspaces defined by PCs and OLMs. For the MNIST dataset, expected, the first few PCs appear digit-like, and the measurement vectors contain increasing high-spatial frequency content k increases (Figure 4A, left). The OLMs, on the other hand, do not follow this coarse-to-fine (low to high froquency) ordering and are visually much more similar to cach other (Figure 4A, right). This is reflected, quantitatively, the measurement variance as a function of k; which falls rapidly for the PCs, but slowly for the OLMs (Figure 4C, left).
Similar phenomena are obscrved for the CelebA dataset (Figure 4B, C). The PCs, known "cigenfaces" (Sirovich & Kirby, 1987; Turk & Pentland, 1991), contain features that are geometrically aligned with features of the face, with increasing spatial frequency content. The variance of the measurements across PCs falls approximately exponentially. Although the OLMs also have a face-like appearance, they differ from the PCs. Each OLM vector has a detailed representation of fine facial features (eyes, nose, lips), and a coarse representation of the surrounding content (forehead, chin, hair). As in the MNIST case, all OT.ss have similar spatial frequency composition. Consistent with this, the variance of the measurements falls slowly across the OLMs (Figure 4C, right).
To quantify the differences between these two sets of measurement vectors, use the Grassmann distance between the subspaces they span (Hamm & Leo, 2008; Björck & Golub, 1973). Figure 4D shows this distance as a function of k. As a control, the blue line measures the distance between subspaces arising from PCs computed on two random halves of the training data. As expected, the distance between these two subspaces is small. On the other hand, for both the MNIST and CelebA datasct, the subspaces spanned by the optimal measurements are distinct from those defined by the PCs (Figure 4D, red), but they are more similar to the PCs than to the space defined by set of random measurements (Figure 4D, green).
8

---

Published in Transactions on Machine Learning Research (05/2025)
A
B CelebA:
MNIST:
PCs
OLM
PCs
OLM
0
H
4
?/
J
8
1
P
5
3
16
D
101
MNIST
CelebA
MNIST
CelebA
109
101
PC
Grassmann Distance
16.
FC- PND
40
Variance
10"1-
10-
OLM
10-1-
10-2-
10-3
10-3
128
128 # of Measurements (k)
64
256
1024 4096
k-th Component
k-th Component
# of Measurements (k)
F
1.0
MNIST
CelebA
Log-Frequency (a.u.)
MNIST
CelebA
0.8
Skewness
CLM
PCA
0.5
0.3
OLM
0.0
192
1024
0.05 Mutual Information
0.10
0.15
0
0.10 Mutual Information
0.20
k-th Component
k-th Component
OLM
H
OLM
35
OLM + Pricr OLM,, Prior
30
PSNR
PSNR
20
2-
3
DLM Proor
20
DIM Pricr
16-
32
64
0.01
0.1
Number of Measurements
Noise Sigma
Figure 4: Optimized measurement vectors are distinct from PC and random measurements. A) Left: Twenty-five selected principal components of the MNIST dataset, visualized as images, sorted by variance explained from top to bottom, and left to right. Right: Twenty-five components from the columns of the OLM for k- = 64. B) Same as A) but for the CelebA dataset. C) The variance of the measurement on each component function of number of measurements (k) for the PCs (blue) and OLMs (red). Note that the optimal measurements are sorted post hoc based on the variance explained by cach component. These vectors are optimized jointly for each & and are not ordered by the algorithm itself. D) The Grassmann distance between subspaces spanned by different linear measurements as a function of k (Hamm & Lee, 2008). We show the distance between subspaces spanned by PCs obtained on two random halves of the training data (blue), between subspaces spanned by PCs and OLMs (red), and between subspaces spanned by PCs and set of random measurements (green). See Appendix E for the definition of Grassmann distance. E) The (absolute) skewness value of the measurement on each component a function of number of measurements (k, sorted post hoc based on the skewness value) for the PCs (bluc) and OLMs (red). F) Distribution of mutual information between all pairs of measurement directions for PCA (blue), ICA (green), and OLM (red). G) Performance (on MNIST) and visualization of OLMs (olive, OLMssq obtained via a sequential version of the algorithm Appendix E.6. H) Performance as a function of measurement noise (on MNIST, k = 32) and visualization of OLMs obtained with Gaussian noise (a 0.4) added to the linear measurements during optimization (olive, OLMmoose), along with comparison to the regular OLMs (red) and PCs (orange).
9

---

Published in Transactions on Machine Learning Research (05/2025)
We can also characterize the linear mcasurements by analyzing the distribution of measurement values they produce in response to natural images (i.e., the measurement distribution). We found that OLMs differ from traditional methods in two key aspects: First, their measurement distributions are highly asymmetrical, as indicated by the significant non-zero skewness values (sce Figure 4E). Second, unlike PCA or ICA, OLMs produce non-factorized measurement distributions: the measurements across axes are not fully independent. This dependency is reflected in the increased pairwise mutual information between different measurement directions observed for OLMs compared to those obtained with PCA or ICA (Figure 4F). This observation aligns with the intuition from the 2D example in Figure 1, where optimal measurements for non- non-Gaussian priors are not necessarily aligned with the axes.
Lastly, we also consider two modifications to the optimization procedure that result in different OLMs. First, in Figure 4G we present a set of OLMs that are sequentially organized - similar to PCs using a greedy version of the algorithm (sce Appendix E.6), where the measurement subspace for smaller & is always contained within that of larger k. We found that while enforcing this sequential constraint results in a slight decrease in performance, the resulting OLMs exhibit more ordered spatial frequency content. Nenetheless, they remain distinct from the PCs both visually and when comparing subspace distances (not shown).
Second, in Figure 4H we examine the robustness of different measurement matrices to noise. For both PCs and OLMs, PSNR decreases as an increasing amount of Gaussian noise is added to the measurements. The OLMs can be made more robust to noise by injecting measurement noise during the OLM optimization (in this case, with a fixed standard deviation of a = 0.4). This results in a more noise-robust set of linear measurements (OLMnoise); accompanied by a modest performance loss in low-noise regimes. The noise-optimized OLMs are less smooth than those optimized without noise (Figure 4H). A more thorough investigation of noise robustness is worthwhile, but will require the development of a reconstruction algorithm that operates on noisy measurements.
3.5
Optimized linear measurements for perceptual loss
A
0.8
- OLMuu Pror
-e- GLLM + Prir
SSIM, OLM MSE + Prior
0.8
B
Original
PG + Prior
OLM
OLM
OLM SORA
PG Prior
Projecton
0.7
0.7
SSIM
0.6
0,500
0890
0.5
0.5
0.4
409'
k= 32
32
64
128
256
0.5 0.6 0.7 0.8 SSIM, OLM SSm + Prior
0.4
2280
# of Measurements (k)
Figure 5: Optimal mcasurements for perceptual loss, as measured by the Structural Similarity Index Measure (SSIM, Wang et al. (2004)). A) Left: SSTM as a function of number of measurement k, for PC projection, PC, and OLM optimized for MSE and SSTM, all three using the denoiser prior. The number indicates the increase in SSIM from OLM optimized for MSE to OLM optimized for SSIM. Right: Scatter plot of the SSIM value for individual images, for OLM optimized for SSIM (x-axis) and MSE (y-axis), respectively. B) Example linear inverse solutions obtained from different measurement matrices (at h = =32) combined with the denoiser prior. The numbers indicate the SSIM value for each individual image. C) Example measurement vectors from the OLM optimized for SSIM.
The previous sections described measurements optimized for MSE. However, our method is general, and can be used to optimize any differentiable objective function defined on the linear inverse estimates.
As an example, we computed a set of OLMs with respect to structural similarity index (SSIM) (Wang et al., 2004), a widely used perceptual image quality metric. Figure 5 shows results obtained using this set of optimal linear measurements. We obtained a noticcable improvement in mcan SSIM for a range of k, and this improvement applies to the majority of the images in the test set. In Figure 5B, four example images are shown to highlight the visual improvement obtained by optimizing for the SSIM objective. However, it is
10

---

Published in Transactions on Machine Learning Research (05/2025)
worth noting that optimizing for SSIM does result in lower average PSNR compared to the PCs, suggesting a trade-off between optimizing for perceptual quality versus MSE reconstruction, at least with our methods.
Lastly, in Figure 5C, the SSIM-optimized measurement vectors are visualized, which appear quite distinct from both the PCs and their MSE-optimized counterpart shown in Figure 4B. We further confirmed this difference by analyzing the measurement subspace, and found that the subspace distance between OLMs optimized toward different objectives is comparable to their distance from the PCs.
4 Related Work
In this section, discuss recent developments in specifying natural image priors as well as previous ap- proaches to optimizing linear measurements, including analyses of cameras and biological vision.
Traditionally, prior models have been developed by combining constraints imposed by structural properties such as translation or dilation invariance, with simple parametric forms, such as Gaussian, mixtures of Gaussian, or local Markov random fields. These models have been used for solving inverse problems with steady and gradual improvement in performance (Donoho, 1995; Simoncelli & Adelson, 1996; Moulin & Liu, 1999; Hyvärinen, 1999; Romberg et al., 2001; Şendur & Selesnick, 2002; Portilla et al., 2003a; Lyu & Simoncelli, 2008; Zoran & Weiss, 2012). More recently, methods such as VAEs (Kingma & Welling, 2013) and GANs (Goodfellow et al., 2020) have been developed to learn more complex image priors by taking advantage of the incrcased expressivity of deep neural networks. In the last few years, scoro-based diffusion models have emerged as the state-of-the-arl method for learning sophisticated image priors (Sohl- Dickstein et al., 2015; Song & Ermon, 2019; Ho et al., 2020; Nichol & Dhariwal, 2021), as evidenced by the high quality of generated images obtained as draws from these priors. Diffusion models rely on the explicit relationship between the MMSE denoising solution and the score of the noisy image density (Miyasawa, 1961; Raphan & Simoncelli, 2011; Vincent, 2011). In addition to enabling unconditional sampling from the implicit prior, the power of that prior can be utilized to obtain high-quality solutions to inverse problems (Kadkhodaic & Simoncelli, 2020; Kawar et al., 2022; Wang et al., 2022; Chung et al., 2022; Zhang et al., 2024; Li et al., 2024). A closely related line of work known as plug-and-ploy (P&P) (Venkatakrishman el al., 2013) used denoisers as regularizers for solving inverse problems. A number of recent extensions have used this concept to develop MAP solutions for inverse problems (Chan et al., 2016; Romano et al., 2017a; Zhang et al., 2017; Kamilov et al., 2017; Meinhardt et al., 2017; Chan et al., 2017; Mataev et al., 2019; Teodoro et al., 2019; Sun et al., 2019; Rechorst & Schniter, 2019; Pang et al., 2020; Sun et al., 2023).
Image Priors.
Camera and Sensor Design. The optimal linear measurement problem has arisen in studying the de- sign of cameras or sensory systems. In this case, the sensor measurements are also typically linear, but constrained to be positive-valued and spatially localized. Hardware design considerations often impose addi- tional constraints, for example, that the sensor array must be periodic in its structure. For example, Levin et al. (2008) evaluated the impact of different. choices in camera design through light field projections in a Bayesian framework. Manning & Brainard (2009) enumerated all possible arrangements of small one- dimensional sensory array to understand the tradc-off between spatial and chromatic information, again in the context of Bayesian framework. Similarly, important line of work has examined the problem of op- timizing the measurements made by retinal circuits using an information-theoree combined with biophysical constraints (Atick & Redlich, 1992; Karklin & Simoncelli, 2011; Jun et al., 2021; Roy et al., 2021; Jun et al., 2022; Zhang et al., 2022). The recent development of differentiable rendering has also allowed for end-to-end optimization of optical systems (Tseng et al., 2021; Deb et al., 2022).
objective, in some cases
Optimized Linear Measurements. Other work has considered the problem of optimizing linear mea- surements directly. Weiss et al. (2007) observed that neither PCA nor random mcasurement fully takes into account the statistics of natural images. They attempted to optimize linear measurement using information- based criteria, but were not able to find measurements that outperformed PCA. Wu et al. (2019b) also proposed a method to find better measurement. functions (i.e., both linear and noulinear) in a compressed sensing framework by using the restricted isometry property (Candes, 2008) as an objective. They showed that the optimized measurement functions (both lincar and nonlincar) are superior to simple random mea- surements, but did not compare their results with PCA. They also proposed an optimization method for finding additional structure in signals beyond sparsity (Wu et al., 2019a). Pineda et al. (2020) proposed
11

---

Published in Transactions on Machine Learning Research (05/2025)
method to improve sampling efficiency in an fMRI setting through reinforcement learning. In different line of work, Burge & Geisler (2015); Hersera-Fspoosio & Burge (2025) developed a method for finding linear measurements that are optimal for specific downstream tasks, such as estimating the motion presented in a video sequence.
The main advantages of our method are that (1) the linear measurements are optimized directly with respect the end objective of the reconstruction problem, and that (2) we incorporate a highly expressive learned prior to exploit the higher-order statistics of natural images. As was shown in Section 2, method outperforms both random measurements and PCA.
5
Conclusion
We present a method for finding optimal linear measurements, using a nonlinear reconstruction method based on a learned prior embedded a denoiser. We show numerically that the set of linear measurements found through our method results in better image reconstruction than PC measurement, despite the fact that the latter captures more signal variance. The key components of our method arc: (i) a denoising diffusion model, which allows us to learn complex prior underlying the dalasets; (ii) a linear inverse algorithm that uses the diffusion prior to generate image reconstructions from linear measurements; and (iii) an end-to-end optimization procedure to find the measurement matrix that minimizes a loss function on the reconstructed images. We show that the optimal measurements are sensitive to both the statistics the image dataset, and to the objective function for which they are optimized. Our results highlight the importance of accurately modeling the statistics of the signals to design efficient linear measurements.
One major limitation of our current work is that optimizing linear measurements through the iterative diffu- sion process is substantially more computationally expensive than computing PCs or generating random CS measurements. Additionally, the OLMs are obtained separately for each k and are therefore not sequentially ordered like the principal components. We have restricted ourselves to linear measurements to maintain a direct connection to classical signal processing literature, as they are easier to understand and visualize. Despite this simplifying assumption, it difficult to ascertain the relationship of the learned measurements to the diffusion prior, and thus to the reconstructed images. It is of interest to expand the current results to linear measurements with realistic noise models, or additional measurement constraints such as locality non-negativity. Finally, developing reconstruction methods that couple DNN priors with more general optimized nonlincar measurements presents a challenging but enticing goal for future rescarch.
References
Joseph J Atick and A Norman Redlich. What does the retina know about natural scenes? Neural compula- tion, 4(2):196 210, 1992.
Ballé, V Laparra, and E P Simoncelli. Density modeling of images using generalized normalization transformation. In Int?l Conf Learning Representations (ICLR), San Juan, Puerto Rico, May 2016. URL http://arxiv httt:://rxxv..orgabbb///ee org/abs/ 111111061001 06281.
1111/111..06211..
Rabi N Bhattacharya and Edward C Waymire. Stochastic processes with applications. STAM, 2009.
Ake Björck and Gene H Golub. Numerical methods for computing angles between lincar subspaces. Mathe- matics of compulation, 27(123):579 594, 1973.
Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G Dimakis. Compressed sensing using generative models. In International conference on machine learning, pp. 537-546. PMLR, 2017.
Johannes Burge and Wilson S Geisler. Optimal speed estimation in natural image movies predicts human performance. Nature communications, 6(1):7900, 2015.
Giovanni Bussi and Michele Parrinello. Accurate sampling using Langevin dynamics. Physical Review E, 75 (5):056707, 2007.
12

---

Published in Transactions on Machine Learning Research (05/2025)
Emmanuel Candes. The restricted isometry property and its implications for compressed sensing. Comptes rendus. Muthematique, 346(9-10):589--3) 592, 2008.
S. H. Chan, X. Wang, and O. A. Elgendy. Plug-and-play admm for image restoration: Fixed-point
convergence and applications. IEEE Transactions on Computational Imaging, 3(1):84 98, 2017. doi:
10.1109/TC122011.6629999 2629286.
Stanley H. Chan, Xiran Wang, and Omar A Elgendy. Plug-and-play admm for image restoration: Fixed-point convergence and applications. IEEE Transactions on Compulational Imaging, ((1):84-988 2016.
Hyungjin Chung, Byeongsu Sim, Dohoon Ryu, and Jong Chul Ye. Improving diffusion models for inverse problems using manifold constraints. Advances in Neural Information Processing Systems, 35:25683 25696, 2022.
L Şendur and I W Selesnick. Bivariate shrinkage functions for wavelet-basee denoising exploiting interseale dependency. IEEE Trons Signal Proc, 50(11):2744 -75642276,,
2756, November 2002.
Diptodip Deb, Zhenfei Jiao, Ruth Sims, Alex Chen, Michael Broxton, Misha B Ahrens, Kaspar Podgorski, and Srinivas C Turaga. Fouriernets enable the design of highly non-local optical encoders for computational imaging. Advances in Neural Information Processing Systems, 35:25224 25236, 2022.
Li Deng. The mnist database of handwritten digit images for machine learning research [best of the web]. IEEE signal processing mogazine, 29(6):141-142, 2012.
Nicki Skafte Detlefsen, Jiri Borovec, Justus Schock, Ananya Harsh Jha, Teddy Koker, Luca Di Liello, Daniel Stancl, Changsheng Quan, Maxim Grechkin, and William Falcon. Torchnetries-mcasuring reproducibility in pytorch. Journal of Open Source Software, 4(70) 2022.
D Donoho. Denoising by soft-thresholding. IEEE Trans Info Theory, 43:613 627, 1995.
David L Donoho. Compressed sensing. IEEE Transactions on information theory, 52(4):1289 1306, 2006.
Bradley Efron. Tweedie's formula and selection bias. Journal of the American Stalistical Association, 106 (496):1602-100) 1614, 2011.
Stuart Geman and Donald Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions pattern analysis and machine intelligence, pp. 721-741, 1984.
Ian Goodfellow, Jean Pouget-Abadic, Mchdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(11): 139-144, 2020.
Jihun Hamm and Daniel D Lee. Grassmann discriminant analysis: unifying view on subspace-basee learning. In Proceedings of the 25th international conference on Machine learning, pp. 376-383, 2008.
Daniel Hsprora-Esposito and Johannes Burge. Supervised quadratic feature analysis: An information geom- etry approach to dimensionality reduction. arXiv preprint arXiv:2502.00:: 001668 2025.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural
information processing systems, 33:6840 33:6840-6851, 2020.
Hyvärinen. Sparse code shrinkage: Denoising of nonGaussian data by maximum likelihood estimation. Newral Computation, 11(7):1739 1768, 1999.
Aapo Hyvärinen and Erkki Oja. Independent component analysis: algorithms and applications. Newral networks, 13(4-5):411-430, 2000.
Na Young Jun, Greg D Field, and John Pearson. Scene statistics and noise determine the relative arrangement of receptive field mosaics. Proceedings of the National Academy of Sciences, (115311111 2021.
13

---

Published in Transactions on Machine Learning Research (05/2025)
Na Young Jun, Greg Field, and John Pearson. Efficient coding, channel capacity, and the emergence of retinal mosaics. Advances in neural information processing systems, 35:32311 1-22331--3324, 2022.
Zahra Kadkhodaie and Eero Simoncelli. Stochastic solutions for linear inverse problems using the prior implicit in a denoiser. Aduances in Neural Information Processing Systems, 34:13242-13222 2021.
Zahra Kadkhodaic and Ecro Simoncelli. Solving lincar inverse problems using the prior implicit in a
denoiser. Xiviv preprint xrXx:22007.1300 13640, 2020.
Clugbek S Kamilov, Hassan Mansour, and Brendt Wohlberg. A plug- and-play priors approach for solving nonlinear imaging inverse problems. IEEE Signal Processing Letters, 24(12):187--1876 2017.
Yan Karklin and Ecro Simoncelli. Efficient coding of natural images with population of noisy linear- nonlinear neurons. Advances in neural information processing syslems, 24, 2011.
Bahjat Kawar, Michael Elad, Stefano Ermon, and Jiaming Song. Denoising diffusion restoration models. Advances in Newral Information Processing Systems, 35:23593- 226666, 2022.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint ar 6980, 2014.
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv:1312.611, 2013.
Andrew V Knyazev and Merico E. Argentati. Principal angles between subspaces in a-based scalar product: algorithms and perturbation estimates. SIAM Journal on Scientific Computing, 23(6):2008 2040, 2002.
Anat Levin, William T Freeman, and Frédo Durand. Understanding camera trade-offs through a bayesian analysis of light field projections. In Computer -SsV 2008: 10th European Conference on Com- puter Vision, Marseille, France, October 12-18, 2008, Proceedings, Part IV 10, pp. 88-101. Springer, 2008.
Xiang Li, Soo Min Kwon, Ismail Alkhouri, Saiprasad Ravishankar, and Qing Qu. Decoupled data consis- tency with diffusion purification for image restoration, orXiv preprint arXiv:2403.06054 2024.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. Tn Proceedings of International Conference on Computer Vision (ICCV), 2015.
Michael Lustig, David Donoho, and John M Pauly. Sparse mri: The application of compressed sensing for rapid mr imaging. Magnetic Resonance in Medicine: An Official Journal of the International Society for Magnetic Resonance in Medicine, 58(6):1182-15 1195, 2007.
Siwei Lyu and Eero Simoncelli. Modeling multiscale subbands of photographic images with fields of Gaussian scale mixtures. IEEE Transactions on pottern analysis and machine intelligence, 31(4):693-700 706, 2008.
Jeremy R Manning and David H Brainard. Optimal design of photoreceptor mosaics: why do not see color at night. Visual neuroscience, 26(1):5 19, 2009.
Gary Matacv, Peyman Milanfar, and Michael Elad. Deepred: Deep image prior powered by red. In Proceed- ings of the IEEE International Conference on Computer Vision Workshops, pp. 0-0, 2019.
T. Meinhardt, M. Moeller, C. Hazirbas, and D. Cremers. Learning proximal operators: Using denoising networks for regularizing inverse imaging problems. In 2017 IEEE International Conference on Computer Vision (ICCV), pp. 1799-1808, 2017. doi: 10.1109/ICCV 2017.198.
Koichi Miyasawa. An empirical bayes estimator of the mean of a normal population. Bull. Inst. Internat. Slatist, 38(181-188):1 1961.
14

---

Published in Transactions on Machine Learning Research (05/2025)
Sreyas Mohan, Zahra Kadkhodaie, Eero P Simoncelli, and Carlos Sranandez-Grandde interpretable blind image denoising via bias-free convolutional neural norks arXiv:1906.05. 75,78, 2019.
Robust and ar preprint
P Moulin and J Liu. Analysis of multiresolution image denoising schemes using generalized Gaussian and complexity priors. IEEE Trans Info Theory, 45:909 919, 1999.
Elias Nehme, Daniel Freedman, Racheli Gordon, Boris Ferdman, Lucien E Weiss, Onit Alalouf, Tal Naor, Reut Orange, Tomer Michaeli, and Yoav Shechtman. Deepstorm3d: dense 3d localization microscopy and psf design by deep learning. Nature methods, 17(7):734-744) 2020.
Alex Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. Int'l Conf Machine Learning, 38, 2021.
Tongyao Pang, Yuhui Quan, and Hui Ji. Self-supervised bayesian deep learning for image recovery with ap- plications to compressive sensing. In Computer Vision-Bi -ECVV 2020: 16th European Conference, Glasgow, UK, August 28-28, 2020, Proceedings, Part XI 16, pp. 475-491. Springer, 2020.
Luis Pineda, Sumana Basu, Adriana Romero, Roberto Calandra, and Michal Drozdzal. Active mr k-space sampling with reinforcement learning. In International Conference on Medical Image Computing and Computer-Assisled Intervention, pp. 23 33. Springer, 2020.
J Portilla, V Strela, M J Wainwright, and E P Simoncelli. Image denoising using scale mixtures of Gaussians in the wavelet domain. IEEE Trans Image Proc, 13118) 1351, Nov 2003a. doi: 10. 10.1109/TIP:2000 818640.
J. Portilla, V. Strela, M.J. Wainwright, and E.P. Simoncelli. Image denoising using scale mixtures of Gaus- sians in the wavelet domain. IEEE Transactions on Image Processing, 12(11):1338 1351, 2003b. doi: 10.1109/TTI (009/TIP.2000 2006.818640.
Klaas P Pruessmann, Markus Weiger, Markus B Scheidegger, and Peter Boesiger. Sense: sensitivity encod- ing for fast. mri. Mugnelic Resonance in Medicine: An Official Journal of the International Sociely for Magnetic Resonance in Medicine, 12(5):952-996) 1999.
M Raphan and E P Simoncelli. Learning to be Bayesian without supervision. In B Schölkopf, J Platt, and T Hofmann (eds.), Adv. Neural Information Processing Systems (NIPS*06), volume 19, pp. 1145-1152, Cambridge, MA, May 2007. MIT Press.
M Raphan and E P Simoncelli. Least squares estimation without priors or supervision. Neural Computation, 2342)3374-420, Feb 2011. doi: 10.1162/NECOL __00666...
E. T. Reehorst and Schniter. Regularization by denoising: Clarifications and new interpretations. IEEE Transactions on Computational Imaging, 5(1):52-63) 67, 2019. doi: 10.1109/TCL22018.288811 2882022.....
Herbert E Robbins. An empirical bayes approach to statistics. In Breakthroughs in Statistics: Foundations and basic theory, pp. 388 388-394. Springer, 1992.
Yaniv Romano, Michael Elad, and Peyman Milanfar. The little engine that could: Regularization by de- noising (RED). CoRR, abs/1611 abs/1611.02266. 2017a. URL http://arxiv.nt http:///aaxxii.oogaaa/////////// 111//111100000 02862.
Yaniv Romano, Michael Elad, and Peyman Milanfar. The little engine that could: Regularization by de- noising (red). SIAM Journal Imaging Sciences, 10(4):1804 -844, 2017b.
J. Romberg, H. Choi, and R. Baraniuk. Bayesian tree-structured image modeling using wavelet-domain hidden Markov models. IEEE Trans Image Proc, 10(7), July 2001.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In Medical image computing and computer-assisted InteruentionMIICCA. 2015: 18th inter- national conference, Munich, Germany, October 5-9, 2015, proceedings, part III 18, pp. 234 2412 Springer, 2015.
15

---

Published in Transactions on Machine Learning Research (05/2025)
Suva Roy, Na Young Jun, Emily L Davis, John Pearson, and Greg D Field. Inter-mossan coordination of retinal receptive fields. Nature, 592(7885):440-411 2021.
Ron Shepard, Scott R Brozell, and Gergely Gidofalvi. The representation and parametrization of orthogonal matrices. The Journal of Physical Chemistry A, 119(28):7924 7939, 2015.
Eero Simonnelli and Edward H. Adelson. Noise removal via bayesian wavelet coring. In Proceedings of 3rd IEEE International Conference on Image Processing, volume 1, pp. 379-382. IEEE, 1996.
Lawrence Sirovich and Michael Kirby. Low-dimensional procedure for the characterization of human faces. Journal of the Optical Society of America A, 4(3):519-5)) 524, 1987.
Jascha Sick-Dick,,nin, Eric Weiss, Niru Maheswaranathann and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International conference on machine learning, pp. 2256 2265. PMLR, 2015.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural informalion processing systems, 32, 2019.
Yang Song, Liyue Shen, Lei Xing, and Stefano Ermon. Solving inverse problems in medical imaging with ssore-based generative models. arXiv preprint arXiv:2111.0000 2021.
Y. Sun, B. Wohlberg, and U. S. Kamilov. An online plug-and-pp and-play play algorithm for regularized image reconstrue- tion. IEEE Transactions Compulational Imaging, 5(3):395 408, 2019. doi:
28935668.
Yu Sun, Zihui Wu, Yifan Chen, Berthy T Feng, and Katherine Bouman. Provable probabilistic imaging using score- score-based generative priors. arXiv preprint arXit:23100100335 2023.
Afonso M Teodoro, José M Bioucas-Dias, and Mário AT Figueiredo. Image restoration and reconstruction using targeted plug-and-play priors. IEEE Transactions on Computational Imaging, 5(4):675-686, 2019.
Lloyd N Trefethen and David Bau. Numerical linear algebra, volume 181. SIAM, 2022.
Joel A Tropp. Just relax: Convex programming methods for identifying sparse signals in noise. IEEE transactions on information theory, 52(3):1030 1051, 2006.
Ethan Tseng, Ali Mosleh, Fahim Mannan, Karl St-Arnaud, Avinash Sharma, Yifan Peng, Alexander Braun, Derek Nowrouzezahrai, dran-Francois Lalonde, and Felix Heide. Differentiable compound optics and procossing pipeline optimization for end-to-end camera design. ACM Transactions on Graphics (TOG), 40(2):1 19, 2021.
Matthew Turk and Alex Pentland. Eigenfaces for recognition. Journal of cognilive neuroscience, 3(1):7 86, 1991.
Singanallur V Venkatakrishnan, Charles A Bouman, and Brendt Wohlberg. Plug-and-plas priors for model based reconstruction. In 2013 IEEE Global Conference on Signal and Information Processing, pp. 945-948. IEEE, 2013.
Pascal Vincent. A connection between score matching and denoising autoencoders. Neural computation, 23 (7):1661-1674, 2011.
Yinhuai Wang, Jiwen Yu, and Jian Zhang. Zero-shot image restoration using denoising diffusion null-space model. arXiv preprint Xrx:2222 00490, 2022.
Zhou Wang, Alan C Bovik, Hamid R Sheikh, and Eero P Simoncelli. Image quality assessment: from error visibility to structural similarity. IEEE transactions on image processing, 13(4):600-612, 2004.
Yair Weiss, Hyun Sung Chang, and William T Freeman. Learning compressed sensing. In Snowbird Learning Workshop, Allerton, CA, 2007.
16

---

Published in Transactions on Machine Learning Research (05/2025)
Shanshan Wu, Alex Dimakis, Sujay Sanghavi, Felix Yu, Daniel Holtmann-Rice, Dmitry Storcheus, Afshin Rostamizadeh, and Sanjiv Kumar. Learning a compressed sensing measurement matrix via gradient unrolling. In International Conference on Machine Learning, pp. 6828 6839. PMLR, 2019a.
Yan Wu, Mihaela Rosca, and Timothy Lillicrap. Deep compressed sensing. In International Conference Machine Learning, pp. 6850-6860. PMLR, 2019b.
Bingliang Zhang, Wenda Chu, Julius Berner, Chenlin Meng, Anima Anandkumar, and Yang Song. Improving diffusion inverse problem solving with decoupled noise anncaling. arXiv preprint arXiv:2407.01521, 2024.
Kai Zhang, Wangmeng Zuo, Shuhang Gu, and Lei Zhang. Learning deep cmn denoiser prior for image restoration. In Proc. IEEE Conf. on Compuler Vision and Pallern Recognition (CVPR), volume 2, 2017.
Ling-Q. Qi Zhang, Nicolas P Cottaris, and David H Brainard. An image reconstruction framework for charac- terizing initial visual encoding. Elife, 11:e71 132, 2022.
Bo Zhu, Jeremiah Liu, Stephen F Cauley, Bruce R Rosen, and Matthew S Rosen. Image reconstruction by domain-transforn manifold learning. Nature, 486777 492, 2018.
D) Zoran and Y Weiss. From learning models of natural image patches to whole image restoration. In TEEE International Conference for Computer Vision, 2011.
Daniel Zoran and Yair Weiss. Natural images, Gaussian mixtures and dead leaves. In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 25, 2012.
17

---

Published in Transactions on Machine Learning Research (05/2025)
Appendix
A Tweedie Miyasawa Proof
For completeness, we provide the proof of the core relationship underlying diffusion models (Miyasawa, 1961; Robbins, 1992; Efron, 2011; Raphan & Simoncelli, 2007). Consider the problem of estimating natural image x given noise-corrupted measurement y to minimize the mean of the squared error || 2 over all images and observations y corrupted with known o². In Bayesian terms, the solution to this denoising problem is the posterior mean:
6, with A o2). The estimate F(y) is chosen
/ p(xly) dx - / J ( dr.
p(ylx)p(z)
a(y) =
(10)
Miyasawa (1961) showed that the optimal estimator has a direct relationship to the score function of V (ogg(y) First, write p(y) = (())x))(x)dz. Assuming a Gaussian PDF for p(yla) and taking the gradient with respect to y gives:
1 vup(y) = T² / (0- ()((ll))(()ddd.
(11)
Dividing both sides by p(y) yields:
V ply) ply)
/ (x y) plzz v)
plu) dx
/ (x - y)p(zll)da
(12)
/ xp(xly)drr / yp(aly)dr.
Simplifying this gives the result:
,²V, log logg(y) =(v)-
(13)
Thus, the residual of the optimal denoiser, ((y) y proportional the gradient of log p(y). Note that p(y) is equal to the signal prior p(z) convolved with (blurred by) Gaussian with variance σ². This quantity be used to sample from the implicit prior p(z), for example, by using annealed Langevin dynamics, where the noise x² corresponds to different temperature levels Song & Ermon (2019); Bussi & Parrinello (2007); Bhattacharya & Waymire (2009). See Appendix D for a detailed description of our sampling procedure.
B Principal Components Analysis
Denote by X the data matrix where the columns are individual mean-subtracted samples Ti. The linear projection is defined as & = MM z,, where M is matrix with orthogonal columns. Plugging this expression into Equation (5), we have the expected squared-error loss for linear projection:
1 N
((M)
Σ
|0 MM 2M
Tr[(X - TM x) -M XX]
N
(14)
(Tr[X - xX]]
N (TI[X" x|
Im xx= m.))
To minimize ((M), the my should be the eigenvectors associated with the largest eigenvalues of X which is the empirical covariance matrix. Note that this solution does not assume Gaussian data distribution:
18

---

Published in Transactions on Machine Learning Research (05/2025)
For any data, the optimal (MMSE) linear projection is the projection onto the leading principal components of the covariance matrix.
When the data is in fact Gaussian distributed, linear projection onto the first & PCs does achieve the minimal error possible, as shown in the bivariate example in Fig. 1A. For non-Gaussian distributions, nonlinear estimation can potentially improve performance.
C Sampling Algorithm
Algorithm Sampling via ascent of the log-likelihood gradient from a denoiser residual
Require: denoiser J, step size h, stochasticity from injected noise (3, initial noise level do, final noise level
doa: distribution mean
==0
2: Draw ~ (/m, ogld)
3: while ot 2 doe do
4:
t +
5:
8t - -(( - Ft-1
> Compute the score from the denoiser residual
of - ||s2||/d
b Compute the current noise level for stopping criterion
T = ((1 (h)2 (1 - )
8:
Draw 2t (0, 1)
+ 21-1 + hs, + 7
> Perform a partial denoiser step and add noise
10: end while
11: return Zt
D Constrained Sampling Algorithm
We adopt a previously developed sampling algorithm for solving linear inverse problems (Kadkhodaie Simoncelli, 2020). Given a trained least-squares denoiser #(y), define the denoiser residual g(y) = A(v) y. which is equal to the score of the learned implicit distribution, log The orthogonal lincar mcasure- ment matrix is denoted M E Rdxk The parameters of the algorithun step size h, the magnitude of injected noise B, and stopping criterion dend. The inputs are the linear measurements R
Algorithm 2 Constrained sampling for solving linear inverse problem
Require: m, 9, M, h, 3, Jend
1: 1++ 2: - 0.5(1 1M + Mm
> initialization
V1 N(H, I)
of 119(1))1B/d
5: while > Jend do
4 (I MM + M(m M yt)
compute the conditional gradient A scale factor for the added noise move up the gradient and add noise A compute an estimated noise level
72 [[1 3 h)2 2 (1-4)²)
h)2 x of
Vt+1 + y1 + h +
02 + ///////
++1
end while
For the current paper, we chose 0.1, 3 = 0.1, and aend = 0.01.
The impact of these parameters on reconstruction performance, along with the number of conditional samples used to obtain the MMSE, illustrated in the figure below.
19

---

Published in Transactions on Machine Learning Research (05/2025)
Reconstructon Performance, OLM at k MNIST
25.54
PSNR
PSNR
86.80
20-
25.46
02
0.4
0.6
0.0
02
08
Step Size
Noise
85-
24-
PSNR
PSNR
22
24.5
26.0
21-
0.00
0.10
0.20
0.50
0.40
Stop Critorion Ane
N Average
Supplementary Figure 1: The effect of different paramcters (step size h, injected noise B, stop criterion dend: and number of conditional samples used for averaging) of the algorithm on reconstruction performance, demonstrated using the OLM at 32 on the MNIST dataset.
In general, the step size h has a very small effect (note the scale of the y-axis). Achieving good reconstruction performance requires larger amount of injected noise and sufficiently small noise stop criterion. Addi- tionally, averaging multiple conditional samples significantly improves performance, but the effect quickly diminishes as increases.
E
Experimental Details
E.1
Dataset
We used two primary two dalasets for our experimental results. The CelebA celebrity faces datasel (Liu al., 2015), which contains approximately 200, 000 images, and the MNIST handwritten digits dataset, which contains 60, 000 images (Deng, 2012). For the CelebA dataset, downsampled the images to a resolution of 80 x 80 x 1 grayscale in our main results. The images in the MNIST dataset are the original 28 x 28 x grayscale.
In both cases, we randomly selected n = 512 images as the test set. The rest of the images were used for training the denoiser, computing the principal components, and optimizing the linear measurement matrix. The test set only used for reporting the final performance of the optimized linear measurements.
E.2 CNN denoiser
We performed empirical experiments using UNet architecture. Our UNet networks contain 3 encoder blocks, one mid-level block, and 3 decoder blocks (Ronneberger et al., 2015). (For MNIST images reduced the encoder and decoder blocks to 2, since they are smaller images.) Each block consists of 2 convolutional layers followed by a ReLU son-linearity and bias-free normaliziiiiiiiinnnn.. Each encoder block followed by a 2 spacial down-sampling and a fold increase in the number of channels. Each decoder block followed by a 2 spacial upsampling and a 2 fold reduction of channels. The total number of parameters is 7.6m. All the denoisers are "bias-free": remove all additive constants from convolution and batch-normalizztion
20

---

Published in Transactions on Machine Learning Research (05/2025)
operations (i.e., the batch normalization does not subtract the mean). This facilitates universality (denoisers can operate at all noise levels) see Mohan et al. (2019).
We follow the training procedure described in Mohan et al. (2019), minimizing the mean squared error in denoising images corrupted by i.d.. Gaussian noise with standard deviations drawn from the range [0, 1] (relative to image intensity range [0, 1])- Training is carried out on batches of size 512, for 1000 epochs. Note that all denoisers are universal and blind: they are trained to handle a range of noise, and the noise level is not provided input to the denoiser. These properties which operate without manual specification of the step size schedule (Kadkhodaie & Simoncelli, 2020). This method produces high-quality results in generative sampling, as well sampling conditioned on lincar measurements (Kadkhodaie & Simoncelli, 2021). To train each denoiser, NVIDIA A100 GPU were used. The total training time for each denoiser was approximately 10 hours.
exploited by the sampling algorithm,
E.3 MMSE estimate
We construct the linear inverse estimate by averaging multiple samples obtained using Algorithm 2. The individual samples are shown Figure and Supplementary Figure and Figure 4. Averaging multiple samples achieves a lower MSE by approximating the postcrior mean, which we use when reporting perfor- mance (PSNR values). The number of samples n is set to = 2 when optimizing the linear measurement to optimize performance, we found empirically that using more samples for the MMSE estimates during optimization does not improve performance during testing. For reporting performance on test data, we used n 16.
E.4 Optimizing linear measurement
We search for the optimal linear measurement by performing stochastic gradient descent in the space of orthogonal matrices as described in the main text. The linear inverse procodure Algorithm 2 is end-to-end differentiable, and thus optimization the measurement matrix can be done directly in PyTorch by taking derivatives of reconstruction loss with respect to the matrix parametcrization. In all cases, we used the Adam optimizer (Kingma & Ba, 2014) with a learning rate of 10-4 with exponential decay of 0.90. We used batch size of 64, and training was run for 16 epochs. The optimization was done GPU cluster, with 4 NVIDIA A100 GPUs. The optimization for single OLM requires a few hours for the MNIST dataset, and about 24 hours for the CclebA dataset. The computational cost is primarily due to backpropagation through the diffusion model sampling procedure, which involves iterative applications of the U-Net denoiser.
single node in
E.5 Subspace distance
To quantify the difference between two linear measurement subspaces, we used the distance defined on the Grassmann manifold of subspaces. Concretely, given two lincar subspaces F and G defined by the column of two measurement matrices M, and M2, the principal angles (01, 02 ..., 0x) are defined sequentially Björck & Golub (1973):
cos 02 max max u. Uk; || = 1,11vx |||
T
E EtEG
(15)
subject to uff Ug = 0, of = 0, Vj = 1k,,..,,
The principle angles can be computed numerically using the singular value decomposition as described in Knyazev & Argentati (2002). The Grassmann distance is defined as the L2 norm the vector of principal angles 0:
k de = Σ
2/2
(16)
1=1
21

---

Published in Transactions on Machine Learning Research (05/2025)
E.6 Sequential OLM
The algorithm presented in Section 2.4 learns OLM independently for each value of k. Empirically, we observe that the linear measurement subspace of smaller & is typically not fully contained in that of larger k. In this section, we modify the algorithm into a greody version, where mcasurement vectors are added one at a time, each conditioned on the previous measurement matrix. This results a sequentially ordered set of OLMs, analogous the structure of PCA.
The algorithm works follows: Given a measurement matrix Ms Rd*k find set of vectors U {ui, u2 Udd+)
basis of the mull space of Mg. The new measurement vector m is parameterized m = UX, where À is unit vector. The next measurement matrix M Rdx(k+1) is obtained by concatenating Mr with m as M = [Mx m"]. The objective function in Equation (8) can be written with respect to as:
N Σ (I((M(A)) M*(A)) x2l.
((A)
(17)
To obtain complete set of sequential OLM (denoted OLM start with kn 1, and run the greedy algorithm iteratively, incrcasing the number of measurements k by one at each step.
F
Supplementary Figures and Tables
Gaussian
Sparse
Manifold
1.0
1.0
0.5
0.5
V2 0.0
Y2 0.0
Y2
-0.5
-0.5
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
0.0
1.0
y,
y1
y,
(o), depicted as vector field, for the Supplementary Figure 2: Denoiser implicit prior, - = o
three different data distributions of Figure Each vector indicates the direction in which the probability of the noisy density increases most rapidly (see Eq. 1).
22

---

Published in Transactions on Machine Learning Research (05/2025)
Random Projection
Original
PC Projection
PC Denoiser Prior
OLM Projection
OLM + Denoiser Prior
Random + Denoiser Prior
==1
0
6
0
0
S
8
3
8
4
U
9
9
6
9
2
8
6
k ==2
k
9
4
4
7
4
4
8
7
8
k =
4
4
4
4
4
4
6
7
3
= 32
4
4
$
4
8
7
0
8
5
9
8
S
7
6
k 2
f
4
9
9
9
9
9
8
9
9
7
9
9
9
7
7
7
/
0
3
k 8
7
7
7
7
7
7
7
8
1
3
7
7
7
7
7
7
7
4
8
7
k= 32
7
7
7
7
7
7
7
4
9
9
k=
7
7
7
7
7
7
7
7
7
7
Supplementary Figure 3: Individual samples of the linear inverse estimates from the denoiser prior for two example digit images in the MNIST dataset. The leftmost columns show the PC projection. The next three columns show individual stochastic samples from the denoiser prior, conditioned on the PC measurements, The middle set columns show the OLM projection, and the samples conditioned on the OLMs. The last set of columns show the results from a random measurement matrix. Rows correspond to increasing number of measurement k.
23

---

Published in Transactions on Machine Learning Research (05/2025)
Original
PC Projection
PC Denoiser Prior
OLM Projection
OLM Denoiser Prior
Random Projection
Random Denciser Prior
k=4
k
k 16
k 32
64
k 128
= 512
k
16
k= 32
k= 128
k 512
Supplementary Figure 4: Individual samples of the linear inverse estimates from the denoiser prior for two example digit images in the CelebA dataset. The leftmost columns show the PC projection. The next three columns show individual stochastic samples from the denoiser prior, conditioned on the PC measurements, The middle set columns show the OLM projection, and the samples conditioned on the OLMs. The last set of columns show the results from a random measurement matrix. Rows correspond to increasing number of measurement
24

---

Published in Transactions on Machine Learning Research (05/2025)
METHODS
Bora et al. (2017)
Wu et al. (2019b)
Our Method
DATASET
LASSO (Wavelet)
VAE or GAN Prior
Learned Linear*
Learned Non-Linent
PC + Prior
OLM + Prior
MNIST,
103
17.2
4.0
3.1 + 12
4.31 = 0.13
3.47 0.11
MNIST,
MNIST, 250
49.1
6.2
0.13 0.01
0.04 + 0.002
CelebA, k 50
233
129
32.0 + 6.7
28.0 = 6.7
39.31 + 0.86
38.29 + 0.84
CelebA, k == 100
~y 197
< 76
26.51 0.61
21.77 = 0.58
CelebA, k 500
~v 102
36
9.13 = 0:27
9.01 0.26
Table 1: Compare reconstruction performance to different compressed sensing methods. We compare the per-image MSE (lower is better) of our method with previous methods for compressed sensing using deep neural networks (Bora et al., 2017; Wu et al., 2019b). Methods with symbol *** measurement function that are explicitly optimized; The symbol */ indicates the results are not available, as Wu et al. (2019b) reported performance only for small k; The symbol "~" indicates the MSE are estimated from images of different size (64 x 64) assuming a constant per-pixel error. In addition, + indicates standard error of the mean. Bold numbers highlight the best result for linear measurement.
We compare the per-image MSE of our method with previously proposed methods for compressed sensing using deep neural networks (Bora al., 2017; Wu et al., 2019b). Bora et al. (2017) used both VAE and GAN as image priors to obtain the linear inverse solution. Their methods outperform standard method for compressed sensing using LASSO (sparse prior) in the wavelet domain. They did not attempt optimize the measurement matrix, and as result were vastly outperformed by our method.
Wu et al. (2019b) optimized both linear and nonlinear measurements using the restricted isometry property as an objective, but only for very small k. We found that on MNIST, our OLM is able to match the performance of even the nonlinear measurement function. On CelebA dataset, for k 50, we obtained slightly worse performance for the OLMs compared to the learned lincar measurements Wu et al. (2019b). However, we may have underestimated the error in Wu al. (2019b), as estimated MSE based on images of smaller size (64 64) from their results but assumed constant per-pixel error. Furthermore, method is most effective for k at around 10% of the total number of pixcls. Thus, we expect our advantage to improve further for larger k. Lastly, our method has the distinct feature that we can produce individual high-probability samples, in addition to the MMSE solution.
25


Reviews:
[{"review_id": "0l8B0Nw8f5", "reviewer": "Reviewer_wxhP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strength\n1. the experiment of this paper, demonstrates that given a non-linear prior, a better approximation of the prior (compared with an approximation like Gaussian) could significantly improve the compressed sensing performance, and even the linear measurement could be benefited. It will inspire future work for compressed sensing areas.\n2. experiments in this paper are solid, and clearly demonstrate the proposed compressed sensing method outperforms PCA and ICA.\n3. The writing in this paper is well-organized in general, I could follow the entire paper even without much background in compressed sensing. \n\n## Weakness\n1. The proposed method is not efficient compared with PCA and ICA, both for 1. optimizing the measurement matrix and 2. using the diffusion model to reconstruct from the measurement, as mentioned by the author in the paper. Also, the cost of training a diffusion model is not negligible.\n2. The paper misses the ablation study of the posterior estimation, i.e., the number of samples to estimate the posterior mean, sampling steps for the diffusion model, sampling method, and hyperparameters you proposed in Algorithm 2. \n3. I am a little concerned about extending this method to real-world applications. As I mentioned, there is a need for a training diffusion model for this proposed method, which needs enough training data and time. However, for real-world scenarios like cameras, is there enough training data to train the diffusion model? Otherwise, given out-of-domain data from the camera, what's the performance of the proposed method? Therefore, I highly suggest using a large-scale diffusion model, like stable diffusion [1], to test the zero-shot performance of your method on the out-of-domain dataset. This experiment will significantly improve the practical impact of the proposed method.\n\n[1] Rombach, Robin, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. \"High-resolution image synthesis with latent diffusion models.\" In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 10684-10695. 2022.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents an enhanced linear compressed sensing method that leverages a prior model based on the diffusion probabilistic model. By incorporating the constraint sampling method from previous work, the posterior mean under a given linear measurement is more accurately approximated. Building on this improved approximation, the paper formulates an optimization problem to determine the optimal linear measurement. Experimental results on a 2D synthetic dataset, MNIST, and CelebA demonstrate that the proposed method consistently outperforms conventional approaches such as PCA and ICA. This advancement has the potential to enhance practical applications relying on compressed sensing.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. In section 2.3, the definition of the MMSE proposed in (4) is not clear. It was not until I read section E.3 that I realized how the MMSE is estimated. I suggest moving section E.3 to section 2.3 or at least referring to it in section 2.3. It will make the writing more clear.\n2. Above equation (7), is there a typo for $Q \\in \\mathbb{R}^{d \\times k}$? From (7), Q seems to be a square matrix.\n3. Could the author discuss more about the statement on Page 7 under Figure 3: \"This indicates that the union of subspace priors used in compressed sensing literature does not accurately describe the properties of natural images.\"\n4. I have a question related to the optimizing time. Why does it cost a few hours for MNIST and 24 hours for the CelebA dataset to optimize the matrix with only $dk$ variables? Also, with A100 of 80 GB, why could you only use 2 samples to estimate the posterior mean? Where does the cost and computation come from?", "broader_impact_concerns": "No concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "I7K67O448n", "reviewer": "Reviewer_o6TM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "#### Strengths\n\n- The approach of optimizing linear measurements for compressed sensing using diffusion-based inverse problem solvers is both innovative and effective.\n- The experimental results show clear advantages of OLM against both principal components and random projections, which shows the data compressing ability of data-driven prior.\n- Analyses on the characteristics of measurements and optimizing image perceptual loss are interesting and may interest a boarder audience.\n- The paper is overall well-written and easy to follow.\n\n#### Questions\n\n- How does the optimization of measuring matrices scale with respect to the data dimension and the number of diffusion sampling steps?\n- How do OLMs optimized by perceptual loss differ from those optimized by MSE? Specifically, do measurements optimized for SSIM also reduce reconstruction error in terms of PSNR?\n- I notice some missing recent works on solving inverse problems with plug-and-play diffusion priors, such as [1,2,3], which seem to claim better performance on image reconstructions. Would the OLMs be different using the same diffusion prior but a different plug-and-play inverse problem solver? Would it be a meaningful direction to explore OLMs with more advanced plug-and-play diffusion samplers?\n- The MMSE estimate is calculated \"as the average over multiple conditional samples.\" How does the number of conditional samples used affect the final performance of OLMs? \n\n[1] Wang et al. \"Zero-Shot Image Restoration Using Denoising Diffusion Null-Space Model.\" ICLR 2023.\n\n[2] Zhang et al. \"Improving Diffusion Inverse Problem Solving with Decoupled Noise Annealing.\" arXiv:2407.01521.\n\n[3] Li et al. \"Decoupled Data Consistency with Diffusion Purification for Image Restoration.\" arXiv:2403.06054.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a novel method for optimizing linear measurements used in compressed sensing image reconstruction. This is achieved by leveraging recent developments on solving inverse problems with diffusion prior and optimizing the measurement matrices for a lower reconstruction loss. Experimental results on both synthetic and real image data demonstrate that the proposed method (OLM) outperforms both principal components (PC) and random measurements when using diffusion priors for reconstruction.  Additionally, the paper provides insightful visualizations and statistical analyses that reveal distinct characteristics between PCs and OLMs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The manuscript looks great in its current version, but I believe addressing the questions above in more detail could further enhance its clarity and impact.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ePrpZLTzAS", "reviewer": "Reviewer_oCSD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths:*\n- To the reviewer's knowledge, learning optimal linear measurements for a data-driven diffusion prior is novel. In particular, I am unaware of prior methods focusing on learning measurements for the prior embedded in denoisers. \n- The proposed framework provides nice flexibility in determining what \"optimal\" means by allowing different loss functions to be used, encouraging either low reconstruction error or high perceptual similarity.\n- The results provide nice geometric intuition for how the OLM behaves and the authors do a good job of analyzing various properties of the learned set of measurements.\n\n*Weaknesses:*\n- Focusing on the mean estimate requires a fair amount of computation, as you would need to run the Langevin-style algorithm multiple times and then take an average to get a single estimate.\n- The way the method is proposed does not allow for a type of ordering of the optimal linear measurements. That is, for each fixed k, the set of measurement vectors could be different. This is somewhat of a limitation on interpretability of the resulting measurement vectors. \n- Noise could be naturally integrated into the proposed framework (e.g., one could add a fixed amount of Gaussian noise to M^T_k x in the loss function), but it was not considered here.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the problem of learning a linear measurement operator to minimize reconstruction error when using a diffusion prior. In particular, they consider a denoiser prior in which one can then use a conditional sampling algorithm to generate estimates or find an MMSE estimate. Over a training set of images, one optimizes a loss over the space of orthogonal matrices to find an optimal projection such that the posterior mean estimate is as close to the true underlying image as possible. While an ell2-norm is a natural choice to measure discrepancy, the authors also consider different loss functions such as SSIM and perceptual metrics. The authors show that their method, OLM, consistently outperforms PCA and random measurements on several datasets and provide interesting findings on the different types of operators learned using different reconstruction metrics.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I am requesting the following two changes, which I believe would strengthen the work in my view.\n\n*Experimentation on two facets:* I think it would be very interesting to see what the differences are between the current approach and a sequential greedy approach to learn the OLM, leading to a hierarchical set of measurement vectors. Moreover, adding noise to this objective feels quite natural and it would also be interesting to see how such OLMs change with different types of noise (e.g., if one added Gaussian noise vs Poisson).\n\n*Prior literature discussion:* Some prior literature is missing from the discussion, e.g., there are other works that have tried to learn measurement matrices for compressed sensing, but instead use \\ell_1 decoders for their reconstruction algorithm, such as\n\nWu et al, Learning a Compressed Sensing Measurement Matrix via Gradient Unrolling, ICML 2019\n\nThere are also other works in the MRI literature that have aimed to learn subsampling strategies by, e.g., using reinforcement learning:\n\nPineda et al, Active MR k-space Sampling with Reinforcement Learning, MICCAI 2020\n\nIt could be good to talk about more recent learning-based methods to learn measurement matrices and discuss the pros and cons.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: After a thorough evaluation of the paper, I recommend **acceptance**.

### Summary and Strengths

This paper presents a compelling framework for learning optimal linear measurements tailored to the priors embedded in diffusion probabilistic models. The central idea, jointly optimizing a measurement matrix to minimize reconstruction error via denoiser-guided diffusion, is well-motivated and executed with rigor. Key strengths include:

- **Empirical Validation**: Extensive experiments on MNIST and CelebA show consistent performance gains over PCA, ICA, and random projections under both MSE and SSIM-based loss functions.
- **Thorough Analyses**: The authors investigate the impact of sampling parameters, number of measurements, noise robustness, and sequential optimization, reinforcing the robustness of the approach.
- **Reviewer Consensus**: All three reviewers recommend acceptance and find the claims supported by convincing evidence. Their comments raised several important points that prompted meaningful author revisions, including improvements in clarity (e.g., MMSE definition and matrix orthogonality), additional experiments using a sequential (greedy) optimization algorithm and robustness to noisy measurements, and better positioning with respect to prior work. The authors engaged constructively with all feedback, and the discussion phase helped significantly enhance the quality and clarity of the final manuscript. Several constructive points were raised and addressed, including computational cost, generalizability, and missing literature.

### Points of Discussion

Some concerns were raised around generalizability and practicality:

- **Computational Cost**: The optimization process is more intensive than PCA or ICA. However, the authors justify this by highlighting the benefits in reconstruction quality and the once-off nature of the optimization.
- **Out-of-Domain Generalization**: Reviewer wxhP suggested testing with large-scale pretrained diffusion models like Stable Diffusion. While a valid future direction, the authors appropriately focus on within-domain scenarios, aligning with typical compressed sensing use cases.

The authors also made decent efforts to improve the paper during the discussion phase, including:

- Adding results on greedy (sequential) optimization and noise robustness.
- Expanding the related work section to include more recent literature.
- Clarifying definitions and revising unclear sections (e.g., MMSE estimation and matrix orthogonality).
Decision: Accept (poster)