Learning to reconstruct signals from binary measurements alone
Authors: Julián Tachella
Laurent Jacques
Venue: Accepted by TMLR ()

Abstract: Recent advances in unsupervised learning have highlighted the possibility of learning to reconstruct signals from noisy and incomplete linear measurements alone. These methods play a key role in medical and scientific imaging and sensing, where ground truth data is often scarce or difficult to obtain. However, in practice measurements are not only noisy and incomplete but also quantized. Here we explore the extreme case of learning from binary observations and provide necessary and sufficient conditions on the number of measurements required for identifying a set of signals from incomplete binary data. Our results are complementary to existing bounds on signal recovery from binary measurements. Furthermore, we introduce a novel self-supervised learning approach, which we name SSBM, that only requires binary data for training. We demonstrate in a series of experiments with real datasets that SSBM performs on par with supervised learning and outperforms sparse reconstruction methods with a fixed wavelet basis by a large margin.

Published in Transactions on Machine Learning Research (11/2023)
Learning to reconstruct signals from binary measurements alone
Julián Tachella
julian, tacsela
Physics Laboratory
CNRS & École Normale Supérieure de Lyon
Laurent Jacques
ICTEAM
UCLowain
Reviewed on OpenReview; https: openreview. net/ pet//foum?? id= ioFIAQ0BOS
Abstract
Recent advances unsupervised learning have highlighted the possibility of learning to reconstruct signals from noisy and incomplete linear measurements alone. These methods play key role in medical and scientific imaging and sensing, where ground truth data is often scarce or difficult to obtain. However, in practice measurements and incomplete but also quantized. Here we explore the extreme case of learning from binary observations and provide necessary and sufficient conditions on the number of mea- surements required for identifying a set of signals from incomplete binary data. Our results are complementary to existing bounds on signal recovery from binary measurements. Fur- thermore, we introduce a novel self-supervieed learning approach, which we name SSBM, that only requires binary data for training. We demonstrate in series of experiments with real datasets that SSBM performs par with supervised learning and outperforms sparse reconstruction methods with fixed wavelet basis by a large margin.
not only noisy
1 Introduction
Continuous signals have to be quantized in order to be represented digitally with a limited number of bits in a computer. In many real-world applications, such as radar (Alberti el al., 1991), wireless sensor networks (Chen & Wu. 2015), and recommender systems (Davenport et al. 2014). the measured data is quantized with just few bits per observation. The extreme case of quantization corresponds to observing single bit per measurement. For example, single-photon detectors record the presence or absence of photons at each measurement cycle (Kirmani et al. 2014), and recommendation systems often observe binary measurement of users' preferences only (e.g., via thumbs or down).
The binary sensing problem is formalized as follows: we observe binary measurements y E {-1,1)m of a signal x E X' c Sn-1 with unit norn via the following forward model
== sign (Ar)
(1)
where R a linear forward operator. Recovering the signal from the measurements an ill-posed inverse problem since there are many signals æ E 5n that are consistent with a given mcasurement vector y. Moreover, often the measurement matrix is incomplete < n, e.g., as in one-bit compressed sensing (Jacques
et al. 2013 which makes the signal recovery problem even more challenging.
It is possible to obtain a good estimation of x despite the binary quantization, if the set of plausible signals X is low-dimensional (Bourrier et. al. 2014), i.e., if it occupies a small portion of the ambient space Sa-1
Note that the sensing model in provides no information about the norm x, so it is commonly assumed that signals verify ||^|||

---

Published in Transactions on Machine Learning Research (11/2023)
linear inverse
binary dataset
0
unknown signal set
sensing device(s)
self-supervised training
Figure We propose a method for learning to reconstruct binary measurement observations, using only the binary observations themselves for training. The learned reconstruction function can discover unseen patterns in the data (in this case the clothes of fashionMNIST see the experiments in Section 5 which cannot be recognized in the standard linear reconstructions (no learning). We also provide theoretical bounds that characterize how well we can expect to learn the set of signals from binary measurement data alone.
A popular approach is to assume that X' is single lincar subspace or union of subspaces (Jacques et al, 2013), imposing sparsily over a known dictionary. For example, the well-known lotal variation regularization assumes that the gradients of the signal are sparse (Rudin et al. 1992p. However, in real-world settings, the set of signals X' generally unknown, and sparsity assumptions on an arbitrary dictionary yicld a loose description of the true X, negatively impacting the quality of reconstructions obtained under this assumption. This limitation can be overcome by learning the reconstruction mapping y + x (e-g., with deep neural network) directly from N pairs of measurements and associated signals- -,e., supervised learning scenario with a labeled dataset {(),, =x)); with N assumed sufficiently large. While this learning- based approach generally obtains state-of-the-art, performance, il is often impractical since it can be very expensive or even impossible to obtain ground-trute signals x; for training. For example, recommender systems generally do not have access to high-resolution user ratings on all items for training.
In this paper, we investigate the problems of identifying the signal set and learning reconstruction mapping using dataset of binary measurements only J In this sctting, if the mcasurement process is incomplete m < n, the matrix A has non-trivial nullspace and there is no information in the measurement data about the set of signals X' in the nullspace (Chen et al. 2021]. As consequence, there is not enough information for learning the reconstruction function eit For example, the trivial pseudo-inverse reconstruction f(y) A )AAT)-1y is perfectly consistent with the binary measurements, i.e., sign (Af(w) = y, but is generally lar from being optimal [Boufounos et al. 2015).
Here we show that it is still possible (approximately) identify the signal set and learn to reconstruct the binary mcasurements, if the measurement operator varies across observations, i.e.,
yi sign (Ag.2:)
(2)
where each signal x; is observed via one out of G operators gi [L...., and i =,.,, N. This sensing assumption holds in various practical applications, where signals observed through different operators (e.g., recommendation systems access ralings about different set of items for each user) through an operator which changes through time (e.g., sensor that changes its calibration). Moreover, this assumption is also valid for the case where we obtain binary measurements via a single operator A, but the set X' is known to be invariant to a group of invertible transformations (T₃) 1C such as translations or rotations. The invariance of X' provides access to measurements associated with set of (implicit) operators (Ag = ATG g as we have that
y = sign (AT,T, sign (AT,a')
TT=T-'a E X' for all g 1.....G. G. This obscrvation has been exploited to perform fully unsu- pervised learning on various linear inverse problems, such as magnetic resonance imaging and computed tomography (Chen et al. 2021 2022 Tachella et. al. 2023
with = TT-
2

---

Published in Transactions on Machine Learning Research (11/2023)
Assumption X' _
None
None
boxdim < k
Assumption A, IRmx 9 E
[G]
rank [ ..... Ag)
<
None
Gaussian
Tdentification error bounds
2 mG
k+n/G
log k+n/G
mm
m
Section
Section
3.1
Section
3.1
Section
3.2
Table 1: Summary of the global model identification error ó bounds presented in this paper. The identification error 5 corresponds to the maximal error of the optimal estimation of the signal set from binary measurement data alone (see Definition 3.1h. The bounds depend on the size of the signals n, the number of binary measurement operators G with m measurements, and the dimension of the signal set k.
The problem of recovering a signal from binary measurements under the assumption of known signal set has been extensively studied in the literature (Goyal et al., 1998 Jacques et al. 2013 Oymak & Recht 2015
These works provide practical bounds that characterize the recovery error a function of the number of measurements m for different classes of signal sets. However, they assume that the signal set is known (or that there is enough ground-truth training data to approximate it), which is not often the case in real-world scenarios. Here we investigate the best approximation of the signal set that can obtained from the binary observations. This approximation lets us understand how well we can learn the reconstruction function from reconstruction
binary data. To the best of our knowledge, the model identification problem has not been yet addressed, and we aim to provide the first answers to this problem here. The main contributions of this paper are:
We show that for any G sensing matrices AI,..., Ag m and any dataset size N, there exists signal set whose identification error (precisely defined in Section 3 from binary measurements cannot decay faster than O ((m)) ) when increases.
We prove that, if each operator Ag. g E fl.....
G}, has iid Gaussian entries (a standard construction in one-bit compressed sensing), it is possible to estimate a k-dimensional signal set up to global nm with high probability.
error of O k+n/G log B+n/G)
We determine the sample complexity of the related unsupervised learning problem, i.e., we find that, for G operators with Gaussian entries, the number of distinct binary observations for obtaining the best possible approximation a k-dimensional signal set X' N = (OG(")")e with controlled probability, which reduces to N = (G((T) ( )*) if X is a union of k-dimensional subspaces.
We roduce a Self-Supervised learning loss for training reconstruction networks from Binary Mea- surement data alone (SSBM), and show experimentally that the learned reconstruction function outperforms classical binary iterative hard thresholding (Jacques et al. 2013) and performs on par with fully supervised learning on various real datasets.
A summary of the model identification bounds presented in this paper is shown in Table 1
Related Work
Unsupervised learning in inverse problems. Despite providing very competitive results, most deep learning-based solvers require a supervised learning scenario, i.e., they need measurements and signal pairs ((9,2:)) a labeled datasct, in order to learn the reconstruction function y H x. A first step to overcome this limitation is due to Noise2Noise (Lehtinen et al., (2018), where the authors show that it is possible to learn from only noisy data if two noisy realizations of the same signal ((x, + n, 24 + n()} are available for training. This approach has been extended to lincar inverse problems with pairs of measurements {(Ag, n4 Ag 24 + n2)) Yaanan et al. 2020: Liu et al., 2020). The equivariant imaging framework (Chen et al. 2022 shows that learning the reconstruction Tunction from unpaired measurement data {Aa; + n, of single incomplete linear operator A is possible if the signal model is invariant to group of transformations. This approach can also be adapted to the case where the signal model is not invariant, but measurements are
2021
2The definition of dimension used in this paper is the upper box-counting dimension defined in Section
3

---

Published in Transactions on Machine Learning Research (11/2023)
X = S
boxdim (X)) 1
E sign(Ar) f} x= f()
1 =
The binary sensing operator sign (A-) defines lessellation of the sphere into multiple consistency cells, which are defined all vectors x E S² associated with the same binary code. The consistency cell associated with given measurement is shown in green. Each red line is a great circle defined by all points of 3 perpendicular to one row of A. Middle: the signal set consists of all vectors in the sphere, i.c., X = the center of the cell the optimal reconstruction f(yy) (depicted with blue cross) and the recovery error (denoted by 6) is given by the radius of the cell. Right: the signal set (depicted in black) occupies only a small subset of $?, i.e., it has small box-counting dimension, the optimal reconstruction corresponds to the center of the intersection between the signal set and the consistency cell, and the resulting signal recovery error is smaller.
Figure 2: Geometry of the 1-bit signal recovery problem with 5 and 3. Left:
obtained via many different operators (A +n;) (Tachella al. 2022). ). Necessary and sufficient conditions for learning in these settings are presented in Tachella et al. (2023), however under the assumption of linear observations (no quantization). Here extend these results to the non-lincar binary sensing problem with unsupervised dataset with multiple operators {sign (Ag, and E (I,...,.), with single operator and a group-invarian signal set {sign (Ar;)).
Quantized and one-bit sensing. Reconstructing signals from one-bit compressive measurements is well-studied problem (Goyal et al.) 1998 Jacques et al. 2013 Oymak & Recht 2015 Baraniuk et al., 2017) both in the (over)complete case m 2 n [Goyal al. 1998). and the incomplete setting m < n, either
under the assumption that the signals are sparse (Jacques al. 2013), or more generally, that the signal set has small Gaussian width (Oymak & Recht 2015). Some of these results summarized in Section 2 The theoretical bounds presented in this paper complement those of signal recovery bounds from quantized data, as they characterize the fundamental limitations of model identification from binary measurement data.
One-bit matrix completion and dictionary learning. Matrix completion consists of inferring missing entries of a data matrix Y = "u......y.. whose columns can be seen as partial observations of signals Ia i.e., B: = sign (4, where the operators Ag. select a random subset of m entries of the signal mq. In order recover the missing entrics, it generally assumed that the signals I; (the columns of X [mı,..., #N)) belong to k-dimensional subspace with k & n. Davenport et al. (2014) solve this learning problem via programming and present theoretical bounds for the reconstruction error.
Zayyani et al. 2015 present an algorithm that learns dictionary (t.e., union of k-dimensional subspaces) from binary data alone in the overcomplete regime m > n. Rencker et al. (2019) presents a similar dictionary learning algorithm with convergence guarantees. In this paper, we characterize the model identification error for the larger class of low-dimensional signal sets, which includes subspaces and the union of subspaces as special cases. Moreover, we propose a superviid method that learns the reconstruction mapping directly, avoiding explicit definition (e-g., dictionary) of the signal set.
4

---

Published in Transactions on Machine Learning Research (11/2023)
2 Signal Recovery Preliminaries
We begin with some basic definitions related to the onc-bit sensing problem. The diameter of set is defined (S) su ||u vil, and the radius is defined as half the diameter. Each row a, E R in the operator A divides the unit sphere s=-1 into two hemispheres, i.e., {i sm-1 a 2 0} and for E -m-1 a. 0}. Considering all rows, the operator sign (A-) defines tesselation of ga-1 into consistency cells, where each cell is composed of all the signals that are associated with binary code 3/, i..., {ir E g sign (Ax) = y}- The radius and number of consistency cells play an important role in the analysis of signal recovery and model identification. Figure 2 illustrates the geometry of the problem for n 3 and m = 5.
The problem of rocovering a signal from one-bit compressod measurements with a known signal set has been well studied (Goyal al., 1998 Jacques el. al. 2013 Oymak & Recht 2015 Baraniuk al.) 2017). These works characterize the maximum estimation error across all signals obtained by an optimal reconstruction function f, i.e.
max ZEX
|| f(sign (Ax))
(4)
function of the number of measurements and complexity of the signal model. From geometric viewpoint (see Figure 2). the optimal reconstruction function with respect to the norm ||- is given by the centroid (with respect to the same norm || II) of the intersection between the consistency cell associated with the measurement y = y(x) = sign (Ax), i.e., Sy == {u E 5--1 : y sign (Au)), and the signal set X, i.e.,
fly) controid(S, nx).
(5)
while the maximum reconstruction error is given by the intersection with maximal radius, that is
8 max radius(S,(e)) (x).
(6)
zE
In the overcomplete case m > n, assuming that all unit vectors are plausible signals, i.e., X' sn the mean reconstruction error 8 is given by the consistency cell with maximal radius, which scales as (see Proposition 5p. The optimal rate is achieved by measurement consistent reconstruction functions, i.c those verifying y sign (Af()) (Goyal et al. 1998).
In the incomplete case m < n, non-trivial signal recovery is only possible the set of signals occupies a low-dimensional subset of the unit sphere g--1 (Oymak & Recht 2015). For example, a common assumption is that X is the set of k-sparse vectors (Jacques et al. 2013). In this paper, we characterize the class of dow-dimensional sets using a single intuitive descriptor, the box-counting dimension. The upper box-counting dimension Falconer 2004 Chapter 2) is defined for a compact subset. S C RR
log M(S,e) e) log 1/c
boxdim (S) = lim sup c
where c) is the minimum number of closed balls of radius with respect to the norm || that are required to cover S. This descriptor has been widely adopted in the inverse problems literature Puy et al. 2017 Tachella et al.] 2023)) and it captures the complexity of various popular models, such as smooth manifolds (Baraniuk & Wakin 2009) and union of subspaces (Blumensath & Davies 2009 Baraniuk et al, 2017). For example, the set of (k + 1)-sparse vectors with unit norm has a box-counting dimension equal to k. The upper box-counting dimension is particularly useful to obtain upper bound on the covering number of a set: if boxdim (X) k, there exists set-dependent constant 6n (0, }) for which
M(X -
(8)
holds for all S co (Puy et al. 2017). The following thcorem (proved in Appendix B exploits this fact provide a bound on the number of measurements noeded for recovering signal with an error smaller than 5 from generic binary observations.
5

---

Published in Transactions on Machine Learning Research (11/2023)
X
E2
X
Figure 3: Illustration of the model identification problem from binary measurements with n 3, m and G = 3. A signal set with box-counting dimension 1 is depicted in black. The red lines define the fronticrs of the consistency cells associated with operators A.,..., A3. From left to right: The signal set, the estimation of the signal set associated with Al...., Ag and the overall estimate X.
Theorem 1. Let a matria with iid entries sampled from a standard Gaussian distribution and assume that boxdim (X) < k, such that ()) S eh for all e < co with co E (0, 2) For 8 I 2an(30/ne, 2, if the nurbbe of measurements verifies
30 m 2 (2k log
log ))
(9)
8
then for all x, s E X, we have that
sign (Ax) = sign (As) = 11 8|l <
(10)
with probability greater than 1 - E.
This result extends Theorem 2 in Jacques et al. (013)). which holds for k-sparse sets only, to general low- dimensional sets and is included in Appendix B For example, if X' is the intersection of L (s 1--mmmmmmni
subspaces with the unit sphere, Theorem holds with constant 6g = (3* (3* - and & > s (Vershynin, 2018 Chapter 4.2). This theorem tells that we recover sparse signals from binary measurements up to error of
h which is sharp, up to the logarithmic factor (Jacques et al. 2013 present similar result, stated in terms of the Gaussian width of the signal set instead of the box-counting dimension.
log
Oymak and Recht (Oymak Recht, 2015)
3 Model Identification from Binary Observations
In this section, we study how well we can identify the signal set from binary measurement data associated with G different measurement operators A1,..., AG E Rmxx We focus on the problem of identifying the set X' from the binary sets (sign (Ag In practice, we observe subset of each binary set sign (A however, in Section 3.4 we show that the number of elements in each of these sets is controlled by the box-counting dimension of X, which is typically low in real-world settings (Hein & Audibert 2005)..
We start by analyzing how the different operators provide us with information about X. Each forward operator Ag constrains the signal space by the following set.
Eg = (VES--1 Bry E X, sign (Ag²) = sign (Agag)}-
(11)
Each set &, is thus composed of all unit vectors that are consistent with at least one point Xg of X according to the binary mapping sign (Ag.). We thus conclude that &, is essentially a dilation of X'aand we clearly have X C X, whose extension is locally determined by specific cells of sign (Ag.). example with binary mapping sign (A each cell is characterized by one binary vector in the range of this mapping,
three-dimensional measurements and = operators is presented in Figure 3 Note that, for a given
3Te Gaussian width of set defined F, (s xt T 8) where s distributed standard Gaussian vector.

---

Published in Transactions on Machine Learning Research (11/2023)
that, shown in this figure, all cells provide different tesselation of S"-1 whose size and dimension will play an important role in our analysis.
Since each &g is dilation of X, we can infer the signal set from the following intersection
& : &
(12)
g=1
which can be expressed concisely as
X = (u s--1; Eei...., IG E N, sign (Agu) sign (AgTa), Ag = 1, 1..... G].
(13)
Due to the binary quantization, the inferred set will be larger than the true set, i.e. X c &. However, we will show that is possible to learn a slightly larger signal set, defined in terms of a global identification error 0, i.e., the open 8-tube
2B = (
inf ||x - all < 6} sEX
(14)
such that the inferred set is contained in it, i.c., & c Xs. We define the model identification error as the smallest 5 such that X C Xg holds:
Definition 3.1 (Model identification error). The identification error of a signal set X C S"-1 from binary sets (sign (), defined as min(6 0 & C Ks).
For our developments be valid, we will further assume that X' is not too dense over gn-1 so that two tubes of X' with two distinct radii are distinct.
Assumption 1. The set X' is closed and there exists maximal radius 0 < gg < 2 for which Xs ç Xsg for any 0 < < 60-
This assumption amounts to saying that there exists at least one open ball in S that does not belong to X C gn-1 For instance, X' gn-1 does not verify this assumption, and X' g--1 fz E IR" 21 2 0} verifies it for do S /2 since Xa gm-1 for any ô 2 V2. The next subsections provide lower and upper bounds for 5.
3.1 A Lower Bound on the Identification Error
We first aim to find lower bound on the best 5 achievable via the following oracle argument: if we had oracle access to G measurements of each point æ in X through each of the G different operators, could stack them together to obtain larger measurement operator, defined as
A1
= sign (Ax) with A
E R
mmGn
(15)
.GG
Ac
This oracle measurement operator provides refined approximation of the signal set, specified as Roracle fo ga-1; 3r X, sign (Av) sign (Az)).
(16)
which is again a dilation of X.
Figure 4 shows example with the oracle set &aracles which provides better (or equal) approximation of the signal set than (13). due to the fact that X C &oracle C d by the construction of these sets. As the oracle estimate is composed of the cells associated with sign (A-) which are intersected by the signal set, the oracle approximation error depends on the diameter of the intersected cells. Given a certain oracle tesselation of gn-1, the worst estimate of X obtained when it intersects the largest cells in the tessellation. The following proposition formalizes the intuition that the maximum consistency cell diametor-é.er -.ee, the greatest distance separating two binary consistent vectors of X' according A serves as lower bound on the model ident ification error 5.

---

Published in Transactions on Machine Learning Research (11/2023)
p
X
oracle
Figure Illustration of the oracle argument the example of Figure 3 Left: The signal set X C S is depicted in black. Middle: Cells intersected by the oracle system are indicated in green. Right: The identified set & is indicated in green, and is larger than the oracle counterpart.
Proposition 2.
Given A RmGxx, for any set X Sn-1 respecting Assumplion 1 with 0 < do < 2, there erists rotation matria R E SO(n) such that the rotated set
x' (u e : RE, x E X} RX
(17)
verifies & ooaate I X3s for any 5 < min(d, do} where 0 < d < 2 is the largest cell diameter of the lesselation induced by sign (A.).
Proof. Given å < do. the proof consists in choosing an appropriate rotation matrix, such that we can find a point y which belongs the oracle estimate & of the rotated set X', but doesn't belong to the 6-tube Xn of this set. From Assumption and since the 8-tube Xs is open, there exists E X and that || vll 5 Let S denote the largest cell in the tesselation of g"-1 induced by sign (4.), such that d = dSam(S). If 8 < d, we always pick rotation R E SO(n) such that both x' = Ræ and v' Rv belong to S. As x' e S, X' intersects S and we have that S C & &racler and thus that v' E Pracle
Xss such
In words, Proposition 2 shows that we can rotate any signal set X' such that it intersects the largest con- sistency cell in the tesselation, obtaining a model identification error that proportional to the maximum cell diameter. The rotation used to remove the best-case scenarios where the signal set only intersects consistency cells that are smaller than the largest one.
In the rest of this subsection, focus bounding the maximum cell diameter, it is directly related to the model identification error through Proposition 2 We start with the following proposition which shows that, if the stacked matrix is rank-deficient, all cells have the maximum possible diameter.
Proposition 3. Consider the tessellation defined by sign (A.) with A RmGxn, If
rank( < n
(18)
all the cells in the tessellation have diometer equal 2.
Proof. If A has rank smaller than n, it has non-trivial nullspace. Let S"-1 be element in the nullspace with unit norm. Consider a cell associated with the code sign (Ax) for some R" inside the
complement of this nullspace (i..,, in the range of AT). The points TI T 5 belong this cell since they share the same code. As | + vll / T + | due to orthogonality, the distance between these two points is
2+t z-P
|||e
2
(19)
2
V1
which tends to 2 ||l||| goes to zero, without modifying the cell code sign (Ax).

---

Published in Transactions on Machine Learning Research (11/2023)
This result provides practical necessary condition for model identification, which is summarized in the following corollary:
Corollary 4. A necessary condition for the tesselation defined by sign (A:) to have consistency cells with diameter smaller than 2 is that there are at least.
2 n/G
measurements per operator.
This proposition tells us that n/G measurements are necessary order to obtain non-trivial cell diameters, and thus obtain a non-trivial estimation of X.
Moreover, in practice, it is possible to compute the rank of the stacked matrix À via numerical approxima- tions. The following theorem provides more refined characterization of the oracle error for m n/G: Proposition 5. Consider the tessellation defined by sign (A.) with E Rm The largest cell in the tessellation has diameter of size at least 2
3 mG
Proof. According to Thao & Vetterli 1996 Theorem A.7), the maximum number of cells Cλ induced by a tessollation defined by sign (A-) with A E RmCxx can be upper bounded as
(mG') 2nh
CA S
As (m)O) < (emG) ym, we have that C₁ S (2emG) yn We can inscribe all cells into spherical caps S of radius 6/2, where 8 is the maximum cell diameter. As shown in (Bal al. 1997 Lemma 2.3), spherical cap of radius 5/2 has measure bounded by (SS)) m 0n-1 where dx-1 is the measure of Sa-1, Since the fessellation covers the unit sphere Sm-1, we have that S"-1 C - and thus
C1 (St) 2 an-1
GnenG n ((()"on 2 On-1 82 mG
Remark The upper bound in this proposition is tight in the sense that there exist matrices that attain this bound. As special case of Theorem with mG measurements and the box-counting dimension of X' set to n, for mG Gaussian random matrix A, and by choosing the minimal number of required measurements in the condition of this theorem, we have with high probability that the largest cell of sign (A.) has a diameter that decays like O (g))) up to log factors. By a standard boosting argument 55] it thus means that there exists mG x matrix A with the same consistency cell diameter decay.
As stated in the following corollary, Proposition shows that the model identification error cannot decrease faster with the number of measurements and operators than O (()a)) since the largest cell in any oracle tessclation has a diameter of at least 3 mG
n
Corollary 6. Given operators AI....,AG= E R and any set C Sn-1 verifying Assumption 1 with 80 < 2, for any 5 min(ōu. mm)). there exists a rotation such that the inferred signal set X' of X" = R.X is not included in X i.c., X' c Xzg.
Proof. If X' C Sn-1 respects Assumption I with 0 < 2, and Roracto and d are the oracle set associated with A and the inferred set of X", respectively, then, derived previously, know that X' c &oraçle C &. According to Proposition 2 and Proposition there exists rotation R such that & = R.fruute & X = RX for 0 < < (6, m.m)) Therefore, from the inclusion above, we thus see that there exists X R& & Xz.
'A spherical cap of radius around point 3n-1 is defined (x g ||c vl <)..
6 Asssuming Gaussian matrix will fail to have the desired cell size with probability at most the probability that of independent Gaussian matrices will fail to have this property is 1 eT, which can made arbitrarily high increasing

---

Published in Transactions on Machine Learning Research (11/2023)
At this stage, it is natural to ask if the condition in Corollary 4 is sufficient to upper bound the model identification error 5. The answer is negative since, for certain families of operators, the maximum consistency cell associated with sign (A-) does not decrease with the number of measurements m or operators G, as illustrated by the following example inspired by a case considered in (Plan & Vershynin 2013 Sec. 1.1).
Example 3.1. Consider the operators with binary T entries AI,..., Ag E (-1,1))mx Let 2 - éi + Xez E T" where e E ga-1 is the ith canonical vector and À is a scalar. Due to the quantization of the operators, we have that sign (Axx)= = sign (Arx) for any value of X, e (-1,1). Thus, there exists cell in the oracle lesselation associated with sign (A-) which contains the set points { [ JxE(-1.1) and thus has a diameter equal to 22, independently of the values of m and G.
In the next subsection, we obtain an upper bound on the model identification error which overcomes this pathological example by sampling the operators from continuous random distribution.
3.2 A Sufficient Condition for Model Identification
We now seek a sufficient condition the number of measurements per operator that guarantees the iden- tification of X' up to global error of 5. As with the sufficient conditions ensuring signal recovery (see Section 2 we assume that X' is low-dimensional to provide bound that holds with high probability if the entries of the operators are sampled from a Gaussian distribution.
Theorem 7. Given the operators Ag....,AG E Rm with entries i. as a standard Gaussian distribution, a low-dimensional signal set X, with boxdim (X) < k, such that M(X <) S c- for all e < co with co E (0, })- For 0 < I min 1} and some faiture probability < E 1, if the number of measurements per operalor verifies
m 10x+ SAvE + |o
(20)
then with probability at least - E, we have that & Xs-
The proof is included in Appendix C Theorem 7 provides a bound on o, i.e., how preciscly we can characterise
the signal set X, which we can compare with the lower bound in Proposition From (00 we have that (sce A Appendix C for a detailed derivation),
O k+n/G log k+n/G/
(21)
m
The bound in (21) is consistent with existing model identification bounds in the linear setting (Tachella
ct al. 2023 which require m ls + n/G measurements per operator for uniquely identifying the signal set.
3.3
Learning to Reconstruct
The best reconstruction function f that can be learned from binary measurements alone can be defined function of the identified set &, as defined in 5
f(w) = centroid nz)
(22)
for binary input y with associated consistency cell S, (u gn-1; sign (Av) = y}. The reconstruction error of ff is lower bounded by the radius of the set S, &. This error must be larger than the error of reconstruction function that has full knowledge about the signal set X. Intuitively, if we have a large model identification error, & will be a bad approximation of X' and thus î will obtain large reconstruction errors. The following proposition formalizes this intuition, showing that the reconstruction error of f is lower bounded by the model identification error.
Proposition 8. Given G operators AI....,Ac Ag E Rm and a set X' C S with model identification error equal to 6, there erist points Ig E X for = 1......, G such that the reconstruction error is
| (sign (Az*t)) - x, 2 8/2,
6This example can be generalized operators with entries belonging discrete set. Q, and show that there exist cells with diameter equal to VA where the minimum distance between two elements in Q.
10

---

Published in Transactions on Machine Learning Research (11/2023)
where f is the optimal reconstruction function that can be learned from the measurement data (sign (Agx)))==1 as defined in 222
Proof. Following Definition 3.1 of model identification error, there exists a point & E & such that ||z | =1 2 for all x E X. According to the construction of the inferred set & in (13). there exist some Fi,..., 3G E X such that sign (Ag²) = sign (AgTg) for all g I,..., G. Therefore, for any g {L...., G), the diameter of the set (,,))( 7 at least || - -ll since both ig and f belong to this set. As the optimal reconstruction function outputs the centroid of the set (as defined 22 ), the reconstruction error of the point Tg is at least || /2 2 8/2.
Therefore, we can use the results on model identification developed in Section 3.1 to lower bound the reconstruction error for the where the function is learned from measurement data only. In particular, combining this result with Corollary 6 we obtain that the (worst-case) reconstruction error should be larger than n It is worth noting that this result also holds for the case where we have a single operator and mG.
group invariance, i.e., when A, = AT, for = 1......
An upper bound on the reconstruction error harder to obtain. Unfortunately, Theorems | and do not automatically translate into bound on the optimal reconstruction error of the reconstruction function defined in 22 Theorem 7 implies that the optimal unsupervised reconstruction (sign (A,a)) is most 00 KoinnGG log k+n/// away from the signal set X, but does not guarantee that it is close to x. heleth
mmm
conjecture that this rate holds with high probability if the operators follow Gaussian distribution:
Conjecture 9. Given binary measurements from the operators AI,..., Ag E RR with entries i.i.d. from standard Gaussian distribution, the optimal reconstruction function defined in 22 hos marimal recon- struction error that upper bounded as O ktn/G log k+n/C)
nm with high probability.
Conjecture 9 hypothesizes that the optimal unsupervised reconstruction function should obtain similar performance than the supervised one, i..,, O( k log am) shown in Theorem [ if the mumber of operators is m sulficiently large, i.e., G >>>n n/kk In the experiments in Section 5 we provide empirical evidence that supports this hypothesis.
3.4 Sample complexity
We end our theoretical analysis of the unsupervised learning problem by bounding its sample complexity, i.e., bound the number N of distinct binary mcasurement vectors {us), that must be acquired for obtaining the best approximation of the signal set X' from binary data.
Since we observe binary vectors E {+1)m there is limited number of different binary observations. We could naively expect to observe up to 2dh different vectors per measurement operator (i.e., all possible binary codes with m bits), requiring at most N I G2m samples to fully characterize the best approximation of the signal set & defined in (13). Fortunately, as alrcady exploited in the proof of Proposition 5 this upper bound can be significantly reduced if the signal set has a low box-counting dimension, as not all cells in the tessellation will be intersected by the signal set (see Figure 3). We can thus obtain better upper bound by counting the number of intersected colls, denoted as sign (-
If X is the intersection ion of a single k-dimensional subspace with the unit sphere, Thao & Vetterli 1996 Theorem A.7) tells us that, for any matrix mxx with m 2 k, there are sign (AX) $ (()) intersected cells. More generally, if X is a union of L subspaces, we have |sign (AX) < L2 (T). Thus, using the fact from the G measurement operators, we can observe up to
that (m) < (3m) K
N GL Gmyk
(23)
different measurement vectors. However, this result only holds for a union of subspaces having each dimension k. The following theorem extends this result to more general low-dimensional sets with small upper box- counting dimension.
11

---

Published in Transactions on Machine Learning Research (11/2023)
Theorem 10. Let the entries of A E R be sampled from standard Gaussion distribution, and let X S RR' with boxdim (X) < k. If k/mmm/) < min(co. 1/2), then, in expectation, the cardinality of the measurement set is bounded as
E sign (AX) _ (mmyn
(24)
Moreover, given failure probabilily 0 < < 1, if 2k/ (m S min(co. 1/2), then, with probability 1- E, have
sign (AX) - ( BmyAn
5k
(25)
5k
The proof is included in Appendix This result depends on the square root of the ambient dimension vn duc the application of Lemma and can be suboptimal for some signal sets. For example, the bound in 23 avoids this dependency for the case where X' union of subspaces.
In the setting where we observe measurements through G independent forward operators, we sum the number of intersected cells for each operator, so that with probability exceeding 1 - G for 0 < & (by union bound), the number of different binary measurement vectors is then bounded by
N N my
5k
with hidden multiplicative constant depending on &. Similarly to 23 this bound scales exponentially
only in the model dimension & but not in the number of measurements a single operator and a k-dimensional invariant signal set, we have the upper bound N == 0 mm/
operators G. In the setting of
5k
(mxx
4 Learning Algorithms
In this section, we present novel algorithm for learning the reconstruction function : A) + from N binary measurement vectors { Ag) which is motivated by the analysis in Section 3 We parameterize the reconstruction function using a deep neural network with parameters 8 E RP. The learned function can take into account. the knowledge about the forward operator by simply applying linear inverse at the first layer, i.e., foly. A) = fo(AT y), or using more complex unrolled optimization architectures (Monga et al, 2021).
In the case where we observe measurements associated with G different forward operators, we propose the SSBM loss
arg min
Σ
EMC (yis (o,s) + a Σ | - folsign (A.5a,)), A.)1
(26)
PERP
where $0,; = fo(y,, Ag.); , the cost LMC (yi, Ag. 2 0 enforees measurement consistency (MC), i.e., require that yi = sign( &g.)) and E R., is a hyperparameter controlling the trade-off between the two terms involved. In the setting where we have a single operator and the set X' is invariant to a group of transfor- mations (T such as rotations translations, aim to learn reconstruction function fo y x (we remove the dependence of fe on A to simplify the notation) via the following self-supervised loss:
N Σ
G
arg min BERP
EMC (ui, Afo + a Σ I1, - fo (sign (AT
(27)
9=1
where de., fe()s) and E R In practice, we minimize (26) by mini- tini-batching approaches (e.g., stochastic gradient descent) by using sampling one out of the G operators at random per batch. In both cases, we choose the measurement. consistency term to be the logistic loss, i.e.,
LMC () = loog (1 + exp(- yo o ())
(28)
which enforees sign-consistent predictions which are far from zero, as the logistic function tends asymptot- ically towards zero as [0] + co. An empirical analysis in Section 5 shows that the logistic loss obtains the best performance across various popular consistency losses.
12

---

Published in Transactions on Machine Learning Research (11/2023)
Analysis of the proposed loss We focus on the multi-operator loss in 26) although similar analysis also holds for the equivariant setting. The first term of the loss enforces measurement consistency, i.e., requires yi sign fol:. )) for every yi in the dataset. However, in the incomplete setting m < n, the simple pscudo-inverse solution
Iw: Ag) A.
(29)
with A1 = Ag (Ag44)) is mcasurement consistent for any number of operators G and training data N. Therefore, the first loss does not prevent learning a function fo(y, Ag) which acts independently for each operator (as there were independent learning problems). The second loss bootstraps the current estimates 02.0 = fo Ag.) as new ground truth references, mimicking the supervised loss
N
G
ΣΣ
| fsigign (A, As)ll
(30)
in order enforce consistency across operators. Importantly, this additional loss avoids the trivial pseudo- inverse solution in 29
Alv Ai sign (A.4ju) # 0
(31)
for * s if the nullspacos of Ag and Ag are different, e.g., the necessary condition in Corollary 4 is verified.
Model identification perspective The learning algorithm constructs a discrete approximation of the signal set using the reconstructed datasct, i.e., Ug-1,, where X, fo 9.99).g) Ag) for g -= I..... G and Y/ the subset of measurement vectors associated with the gth operator. From a model identification perspective, the measurement consistency loss ensures that D/ Ag for all l,...,G. G. The second loss ensures consistency across all operators, i.e., Xg fo As) for all pairs s,g {l,.... G}. acting as proxy for Xg Xz.
5 Experiments
For all experiments, we use measurement operators with entries sampled from a standard Gaussian distri- bution and evaluate the performance of the algorithms using by computing the average peak-to-signa ratio (PSNR) on a test set with N' ground-truth signals, that is:
NO N PSNR (2/, (signn (A, ..))),
(32)
where the PSNR is computed after normalizing the reconstructed image such that it has the same norm the reference image, i.C.,
||||||
PSNR(2, 2) = -20 -|= - | ||.
(33)
We choose fo A) fo(AT) y) where fo is the U-Net network used in Chen et al. 2021 with weights 0, and train for 400 epochs with the Adam optimizer with learning rate 10 and standard hyperparameters 31 0.9 and A2 = 0.99.
5.1 MNIST experiments
We evaluate the theoretical bounds using the MNIST dataset, which consists of greyscale images with n = 784 pixels and whose box-counting dimension is approximately & ss 12 (Hein Audibert, 2005). We use 6 1 images for training and 10 for testing.
Multiple operators setting. alternatives:
We start by comparing the logistic consistency loss in 28 with the following
Standard lo-loss, LxC (y. 0) sign (f) = y and unit outputs [Ø]
-1g-011.. As this loss zero only if 9 = y, promotes sign consistency,
13

---

Published in Transactions on Machine Learning Research (11/2023)
25
Logistic
20
Loss
Tost
One-sided &
Oue-sided Eg
0.26
1.030.88
170
Figure 5: Evaluated training losses for enforcing sign measurement consistency sign (Aă) = y of reconstrue- tions fo(v) f. Left: The loss functions shown for the case y 1. Right: Average test PSNR of different measurement consistency losses the MNIST datasct with G = 10 operators.
One-sided fy-loss, LmC (v. = max(-y 9, 0) where denotes element-wise multiplication and the max operation is performed element-wise. This loss is zero as long as sign (f) regardless of the value of (g).
For all losses except the logistic loss, setting the trade-off parameter = obtained best results. For the logistic loss, we performed sweep over different values of a and m, finding that the optimal choice of a decreases with m (see Appendix for more details). Thus, we set = 0.1 for m < n and a = 0.06 for m 2 n. Figure 5 shows the different losses and the test performance for different values of measurements using 10 operators. The logistic loss obtains the best performance across all sampling regimes, whereas the one-sided & loss obtains the worst results.
Sccondly, compare the logistic loss with the following learning schemes:
Linear inverse (no learning), defined as 24 = AA. Vi. This reconstruction can fail to be measurement consistent (Goyal et al. 1998).
Standard supervised learning loss, defined Ei=l 22
Se(vi; Ag We also evaluate this loss together with the cross-operator consistency term in 26 which denote supervisod
Measurement consistency loss, defined Σn LMC (yi, Ag, fo Aq,)) using the logistic loss.
The binary iterative hard-threshokding (BIHT) reconstruction algorithm (Jacques et al. 2013) with a Daubechies4 orthonormal wavelet basis. The step size and sparsity level of the algorithm were chosen via grid search. Tt is worth noting that the best-performing sparsity level increases the mumber of measurements m is increased.
Proposed SSBM loss in 26 using the logistic loss for measurement consistency.
Test PSNR values obtained for the case of G = 10 operators are shown in the left subfigure of Figure 6 where the PSNR in dB is plotted against m/n in log-scale representation. The measurement consistency approach obtains performance similar to simply applying a lincar inverse for the incomplete m/n < 1 setting, whereas it obtains a significant. improvement over the linear inverse the overcomplete case m/n 2 1. This gap can be attributed to the lack of measurement consistency of the lincar roconstruction algorithm (Goyal let al. 1998). The proposed loss obtains performance that is several dBs above the linear inverse and BIHT for all sampling regimes. BIHT relies the wavelet sparsity prior, which does not capture well enough the MNIST digits. SSBM performs similarly to supervised learning as the sampling ratio tends to 1, and perhaps surprisingly, it obtains slightly better performance than supervised learning for m/n = 1.28. However, adding the cross-operator consistency loss to the supervised method (Le., the method supervised+ in Section 5.1 performs better for all sampling regimes than SSBM.
The right plot in Figure compares the performance of the SSBM with the bounds Proposition and Con- jecture g These bounds behave almost linearly in this log-log plot of both the error eereerrtrrroot throuuhh the PSNR and
14

---

Published in Transactions on Machine Learning Research (11/2023)
SSBM (ours)
PSNR (8)
Linear Inverse
PeNt (d8)
SSBM (ours)
Mess. Considenccy
1/m
16
BIHT
25
log
Supervised
10
Supervised+
R/G
15
0.06
0.10
0.30
0.74
1.28
4.00
m/n
0.06
0.18
0.30
0.74
1.28
4.00
m/n
Figure 6: Left: Average test PSNR of different supervised and unsupervised algorithms the MNIST dataset with G 10 operators. Right: The performance of the SSBM method follows closely the bounds
in Conjecture
Test PSNR
7
7
7
40
40
20
20
7
7
7
10
15
7
7
7
0.084
m/n
0.26
(a)
m/n
(b)
Figure 7: (a) Average test PSNR and (b) reconstructed test images of the proposed unsupervised method for different numbers of operators G and measurements m.
the log-scale representation of m/n. We thus observe a good agreement between the predictions in Conjec- ture 9 and the performance in practice.
Figure shows the average test PSNR and reconstructed images obtained by the proposed self-supervised method for different values of G and m. The method fails to obtain good reconstructions when G = the necessary condition in Corollary is not fulfilled.
Noisy measurements In many sensing applications, the sensor data are subject to noise. In the setting of binary measurements, noise affects the measurements by flipping the sign, as the observations can only be -1 or +1. We evaluate the proposed algorithm with m 274 measurements and 10 operators and different noise levels, according to the model
y1 sign (Ag., ())
(34)
where 6 (N 2 for i= 1...,.,, N. Figure 8 shows the performance of the SSBM algorithm for different values of The learning algorithm is particularly robust to noise, oblaining good performance for noise levels up to a = 0.13. This noise level translates to having approximately 15% of bits flipped per measurement vector. It is worth noting that these results indicate that we can expect similarly good performances for other noise distributions (c.g., Poisson noise) for a similar average number of bit flips.
Equivariant sctting using shifts. We evaluate the setting of learning with a single operator by using the unsupervised equivariant objective in 227 with 2D shifts as the group of transformations (as the MNIST dataset is approximately shift-invariant). Figure shows the average test PSNR and reconstructed images
15

---

Published in Transactions on Machine Learning Research (11/2023)
20
Test PSNR (dB)
PSNR (dB]
SSBM (ours)
16
15
Linear Inverse
10
10
0.02
0.05
0.13
0.36
1.00
5.0 15 24
percenlage meas. with Nipped bits
Figure 8: Robustness of the proposed learning algorithm to noise in the measurement data. Left: Average test PSNR as function of the standard deviation of the noisc. Right: Average test PSNR as a function of the average percentage of flipped bits per measurement vector.
Linear Inverse
Meas. Consistent
SSBM (ours)
BIHT
Supervised
7
Supervised
0.13
Text PSNR (15)
Linear
BIHT
Meas, Consistent SSBM (ours)
7
0.25
0.08
0.28
0.51
1.20
4.00
7
7
m/n
(a)
(b)
Figure 9: (a) Average test PSNR and (b) reconstructed test images by the compared algorithms with single operator A as a function of the undersampling ratio m/n.
function of the measurements m for various algorithms. The proposed unsupervised method significantly outperforms the linear inverse, BIHT, and the measurement consistent network in all sampling regimes, and performs closely to supervised learning for m/n > 0.4.
5.2 Other Datasets
In order to demonstrate the robustness of the proposed method across datascts, we evaluate the proposed unsupervised approach on the PashionMNIST (Xiao al. (2017). CelebA (Liu et al. 2015) and Flow- ers Nilssbcc & Zisserman 2008) datasets. The FashionMNIST dataset consists of 10* greyscale images with 28 28 pixels which are divided across G = 10 different forward operators. As with MNIST,
N 6 10 per operator for training and 10 per operator for testing. For the CelebA dataset, use G = 10 forward operators and choose a subset of 10 images for each operator for training and another subset of the same amount for testing. The Flowers dataset consists of 6149 color images for training and 1020 images for testing, all associated with the same forward operator. For both CelebA and Flowers datasets, a center crop of 128 128 pixels of each color image was used for training and testing. Section 5.2 shows the average test PSNR of the proposed unsupervisod mothod, standard supervised learning, BIHT, and the linear inverse. For BIHT, we the Daubechies4 orthonormal wavelet basis and optimize the step size and sparsity level via grid search.
The self-supervised method obtains an average test PSNR which is only to 2 dB below the supervised approach. Figures 10 and [1 show reconstrueted test images by the evaluated approaches for each forward operator. The proposed unsupervised method is able to provide good estimates of the images, while only having access to highly incomplete binary information. The supervised method obtains sharper images, however at the cost of hallucinating details, whereas the proposed method obtains blurrier estimates with less hallueinated details.
16

---

Published in Transactions on Machine Learning Research (11/2023)
linear
inverse
BIHT
propased
supervised
ground
truth
Figure 10: Reconstructed test images using the FashionMNIST dataset. Each column corresponds to test image observed via different forward operator Ag.
linear
inverse
BIHT
proposed
supervised
ground truth
Figure 11: CelebA results. Reconstructed test images using the CelebA dataset. Each column corresponds to test image observed via different forward operator Ag.
6 Conclusions and Future Work
The theoretical analysis this work characterizes the best approximation of a now-dimensional set that can be obtained from binary measurements. The model identification bounds presented here apply large class of signal models, as they only rely on the box-counting dimension, and complement those existing for signal recovery from binary measurements (Goyal et al., 1998 Jacques al., 2013). Moreover, the proposed self- supervised loss provides practical algorithm for learning to reconstruct signals from binary measurements alone, which performs closely to fully supervised learning. This work paves the way for deploying machine learning algorithms in scientific and medical imaging applications with quantized observations, where no ground-truth references are available for training.
We leave the proof of Conjecture g and a study of the effect of noise in the obscrvations and related dithering techniques for future work. Another avenue of future research is the extension of Theorem for the case of operators related through the action of group.
17

---

Published in Transactions on Machine Learning Research (11/2023)
Dataset
m
C
Linear
Inverse
BHHT
Supervised
(Surs(
FashionMNIST
784
300
10
6.38 +: 0.23
10.68
0.31
17.63 = 0.33
16.47 = 0.22
CelebA 49152
9830
10
4.81 + 0.32
16.26
0.40
21.59
0.31
19.53 + 0.3
Flowers
49152
9830
shifts
5.31 + 0.72
14.62
0.92
18.26 + 0.75
16.45 + 0.71
Table 2: Average test. PSNR in dB obtained by the compared methods for the FashionMNIST,, CelebA and Flowers datasets.
Acknowledgments
Part of this research was supportod by the Agence Nationalc de la Recherche (Project UNLIP) and by the Fonds de la Recherche Scientifique FNRS under Grant T.0136.20 (Project Learn2Sense).
References
G Alberti, G Schirinzi, Franceschetti, and V Pascazio. Time-domain convolution of one-bit coded radar signals. In IEE Proceedings F (Rador and Signal Processing), volume 138, pp. 438 444. LET, 1991.
Keith Ball et al. An elementary introduction to modern convex geometry. Flavors of geometry, 31(1-58):26, 1997.
R Baraniuk, Foucart, D Noedell, Y Plan, and M Wootters. One-bit compressive sensing of dictionary- sparse signals. Information and Inference: A Journal of the IMA, 7(1):83 104, 08 2017. ISSN 2049-8764. doi: 00.1093/mmaai//axx
URL https://dol wteeil.orr/1..0 wtt./....////////............ 1twp:/.110000/mmmaaaaa//0000
Richard G Baraniuk and Michael B Wakin. Random projections of smooth manifolds. computational mathematics, 91):51 77, 2009.
Poundations of
T. Blumensath and M. E. Davies. Sampling theorems for signals from the union of finite-dimensional lincar subspaces. IEEE Transactions on Information Theory, 55(4):1872 1882, 2009. doi: 2013003.
Petros Boufounos, Laurent Jacques, Felix Krahmer, and Rayan Saab. Quantization and compressive sensing. In Compressed Sensing and Applications: MATHEON Workshop 2013, pp. 193 103-237. Springer, 2015.
Anthony Bourrier, Mike Davies, Tomer Peleg, Patrick Pérez, and Rémi Gribonval. Fundamental performance limits for ideal decoders in high-dinensional linear inverse problems. IEEE Transactions on Information Theory, 60(12):7928 7946, 2014.
Ching-Hsien Chen and Yuh Wu. Amplitude-aided 1-bit compressive sensing over noisy wireless sensor networks. IEEE Wireless Communications Letters, 4(5):473 476, 2015.
Dongdong Chen, Julián Tachella, and Mike Davics. Equivariant imaging: Learning beyond the range space. Proceedings of the IEEE/CVF Indernational Conference on Computer Vision (ICCV), pp. 4379 4388, October 2021.
Dongdong Chen, Julián Tachella, and Mike Davies. Robust equivariant imaging: a fully unsupervised frame- work for learning to image from noisy and partial measurements, In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
Mark A Davenport, Yaniv Plan, Ewout Van Den Berg, and Mary Wootters. 1-bit matrix completion. Information and Inference: A Journal of the IMA, 3(3):189 223, 2014.
Kenneth Falconer. Fractal geomelry: mathematical foundalions and applications. John Wiley & Sons, 2004.
V.K. Goyal, M. Vetterli, and N.T. Thao. Quantized overcomplete expansions in RV; analysis, synthesis, and algorithms. IEFE Transactions Information Theory, 44(1):16-3) 61,1 1998. doi: 10.1109/18.650800 650985.
18

---

Published in Transactions on Machine Learning Research (11/2023)
Matthias Hein and Jean-Yves Audibert. Intrinsic dimensionality estimation of submanifolds in R In Proceedings of the 22nd international conference on Machine learning (ICML), pp. 2005.
Laurent Jacques, Jason N. Laska, Petros T. Boufounos, and Richard G. Baraniuk. Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors. TEEE transactions on information theory, 59(4): 2082-2102, 2013.
Ahmed Kirmani, Dheera Venkatraman, Dongeek Shin, Andrea Colaço, Franco NC Wong, Jeffrey H Shapiro, and Vivek K Goyal, First-photon imaging. Science, 343(6166)::88 61, 2014.
Jaakko Lehtinen, Jacob Munkberg, Jon Hasselgren, Samuli Laine, Tero Karras, Miika Aittala, Timo Aila, et al. Noise2Noise. In International Conference on Machine Learning (ICMT). PMLR, 2018.
Jiaming Liu, Yu Sun, Cihat Eldeniz, Weijie Gan, Hongyu An, and Ulugbek S Kamilov. RARE: Image roconstruction using deep priors learned without groundtruth. IEEE Journal of Selected Topics in Signal Processing, 14(6):1088-100) 10908,,-19,,,.. 2020.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
Vishal Monga, Yuelong Li, and Yonina C Fldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. IEEE Signal Processing Magazine, 38(2):18-44, 2021.
Maria-Elens Nilsback and Andrew Zisserman. Automated flower classification over a large number of classes. In 2008 Sizth Indion Conference on Computer Vision, Graphics & Image Processing, pp. 722-729. IEEE, 2008.
Samet Oymak and Ben Recht. Near-optimal bounds for binary embeddings of arbitrary sets. arXie preprinl arXiv:1512.04 2015.
Gilles Pisier. The volume of conver bodies and Banach space geometry, volume 94. Cambridge University Press, 1999.
Yaniv Plan and Roman Vershynin. One-bit compressed sensing by linear programming. Communications on pure and Applied Mathematics, (6(8):1275-129)) 2013.
Gilles Puy, Mike E Davies, and Rémi Gribonval. Recipes for stable linear embeddings from hilbert spaces R. IEEE Transactions on Information Theory, 63(4):21111221) -187, 2017.
Lucas Rencker, Francis Bach, Wenwu Wang, and Mark D Plumbley. Sparse recovery and dictionary learning from nonlincar compressive measurements. IEEE Transactions on Signal Processing, (7611))56),-6670 2019.
Leonid I Rudin, Stanley Osher, and Emad Fatemi. Nonlinear total variation based noise removal algorithms. Physico D: nontinear phenomena, 60(1-))2259 2682 1992.
Julián Tachella, Dongdong Chen, and Mike Davies. Unsupervised learning from incomplete measurements for inverse problems. In Alice H. Oh, Alckh Agarwal, Daniclle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL htt/ttts://opeerviieee wtt.:e/oooorm:dda//llsssssr.
Julián Tachella, Dongdong Chen, and Mike Davies. Sensing theorems for learning from incomplete measure- ments. Journal of Machine Learning Research, 24(39):1 45, 2023.
Nguyen T Thao and Martin Vetterli. Lower bound on the mean-squared error in oversampled quantization of periodic signals using vector quantization analysis. IEEE Transactions on Information Theory, 42(2): 469 479, 1996.
Roman Vershynin. High- dige-dimmnsional probability: An introduction with applications in data science, vol- ume 47. Cambridge university press, 2018.
19

---

Published in Transactions on Machine Learning Research (11/2023)
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmist: novel image dataset for benchmarking machine learning algorithms, 2017.
Burhaneddin Yaman, Seyed Amir Hossein Hosseini, Steen Moeller, Jutta Ellermann, Kåmil Ugurbil, and Mchmet Akçakaya. Self-supervised learning of physics-guided reconstruction neural networks without fully sampled reference data. Magnetic resonance in medicine, 84(6))3172-319)) 2020.
Hadi Zayyani, Mehdi Korki, and Farrokh Marvasti. Dictionary learning for blind one bit compressed sensing, IEEE Signal Processing Letters, 23(2):187-191, 2015.
A Technical Lemmas
We begin by introducing some technical results that play important role in the main theorems of the paper. We start with result from (Jacques et al. 2013).
Lemma 11 (Lemma 9 in (Jacques et al. 2013)). ). Given 0 S E < 1 and two unit vectors ā, S R"
and R with a, Miid. (00, 1), we have
Po = P VV E B. (8), Vo (() sign (aTu) = =iign (a T xx) 2 d(ē, -
V
n
T
(35)
P = P Vo E (T). Vo E (T) sign (a vv) # sign (a xT)] 2 d(E, 0)
π
(36)
where d(.,)) denotes the angular distance.
Remark:
The angular distances in Lemma 11 can be translated into Euclidean distances due to the following
inequality:
d(ž, 0) 2 2 sin ($d(i, = i - T||.
(37)
Let (S) denote the set of continuous functions on the set This lemma has the following corollary: a E R" with a misd NNO, 1), we have Corollary 12. Given i E S 0 < <<<
P sign (a & C (B((t)))))) s Vnc.
Proof. The proof can be derived from the complement of the event associated with po in (35) when ă 8. Here is, however, simplified proof for completeness. We first observe that sign (a is discontinuous over
B, ( iff [ S e. Therefore, by the rotational invariance of the Gaussian distribution can choose f = [1,0,... OjT and the probability above amounts to computing
p p Pl
2 < c pla < 22||a|1?1 = Pia S (1-E (0 + ......... = S (
where & ~ (n - 1). Since Pla
- {l < 2
V - VE, and E / vn by Jensen's
ve inequality, we finally get p < V
-íー VT T <
2
E n < EVVT.
vn
B Signal Recovery Proof
Proof of Theorem 7 Proving this theorem amounts showing that the probability of the failure of the event
sign (Ax) = sign (As) | s|l < <
20

---

Published in Transactions on Machine Learning Research (11/2023)
decays exponentially in m provided that
m 2 (2klog 30,a 8 + log {
holds. In other words, we want to upper bound
= B 22 E X, |2] x2ll > d: sign (Ax1) = sign (Azz)]
with such an exponential decay.
As boxdim (X) < k, there exist constant eo E (0, ()) such that e) S e for all e S 6g. Thus, there is a covering set Qe of e- points, such that for every x E N, there exists point g E Qe which verifies ||a -ql < c.
Thanks to this covering, we can upper bound ps
P6 S P P 92 E Qe Er1 E Be(g)), E Be(92), ||=1 - x2ll > 8 sign (Az1) sign (Arz)]
However, since || x2l > 5, we must have |/ 2ell 2 || xzl 2e > 26. Therefore, defining Qe,s = ((9,4)) Q x Q llq q'l ő -c), the previous upper bound can be enlarged as
ps < P[((),)))) (2) E Qe,8s 3o, E (.()), 3rg (g(22) sign (Azı) sign (Ar2))
Given a fixed pair (q1.g) E Qe,s, Lemma 11 shows that for a E R" drawn from a standard Gaussian distribution
PP Van E Be(gi), ((())) sign (a x1) + sign
2 + |lg 42ll
2 c.
(38)
By setting e = c(6) 8447//0/2
6(1-a) and taking the probability of the complementary event we obtain
P Ron E B.(,), Br2 E (12)) sign (a (aTm) sign [x)]] S - 66/4.
(39)
Therefore, considering the m i..dd rows {a:)1 R of the matrix A (a) (aI. am) Rmxn drawn from standard Gaussian distribution, we have
P E (.()), Aea (x(22) sign (Ar1) sign (Arz))
< - Plaz E Be B.(g2): sign (a, (a]x1) sign (a. x2)]
< mm
Applying a union bound to all pairs (21,42) E Qe(6). C Qu Qe, since there are no more that (12-) S QQ12 < -2h such pairs, obtain
Ps < 8+44//TT/2 (4-
(1 8/4)" < exp 2k log( 8+ 4447 /
nn/2
m8
(40)
14-1)6
where used 1 - 5/4 < exp( -544 for 5
Upper bounding this probability by 0 < S 1 as in the statement. of Thm 1 and using the crude bound
(8+44 1////m/22/44//// S 30 for n > finally obtain 2k log 30 + m log which gives the sample
complexity bound 99
(2k log 30 क + log 1
(41)
where the condition c(8) < 6o holds if 30coyn.
21

---

Published in Transactions on Machine Learning Research (11/2023)
C Model Identification Proof
Proof of Theorem 7 We want to identify the condition that m, G and 0 < 8 < 1 must respect to induce that & C Xss holds with high probability with respect to a random draw of the operators , Ag. Equivalently, we need to show that, for this condition,
sign (Agaig) sign (Agu), Vgg I,...
(42)
holds for some U E Sn-1 \\ A's and some 21...., FG E X' with probability at most & with respect to random draw of the Gaussian matrices A1,..., Ag. This proof adapts some of the procedures given in (Jacques et al. 2013) to our specific setting. We start by bounding this probability for e-balls around vectors ú E Sm Xs
.1..... fg E X, that is
Po = IP| P[3 .G) E (ai X ... (. 3u E (T) Vg = 1, l....., G, sigu (Agu) sign (Agtt))
We first notice that from the independence of the operators {Ag )
Po S T P[3rg E (Zg)) Eo E (2) sign (Age) sign (Agzg)].
Furthermore, as every of each operator Ag is iid. as standard Gaussian random vector ags we have
Po [g IP [3ng Br 30 E (ō) sign (a v) sign (ag 2m,]
G
(43)
[I (1 - P VV., E B. (T,)), Vu E (T) sign (a] v) # sign (a (1),
(44)
From Lemma we know that
PP Varg E B. (Tg), Vo E (e) sign (a],;) # sign (aJ, 2 1 - -11 v n
(45)
where the distance || - i|l can be bounded by 8 obtain
P Vig E (Tx)). Ve (ū) sign (d),.0) + sign (dT, 2 $ VnTe. Vnze= $ which means that Plugging this into 44 and picking
(46)
c=e(6) ( /87" Vn
18 vn
we get
Po S (1 6 + V n m I eepl(- m
(47)
We can extend this result to all vectors E S=-1 Xss and It,..., Da E X' by applying a union bound over a covering of the product set x x (8"-1 1 \ Xz). Since we can cover X' with e balls with e S eg due to the assumption that boxdim (X') < k. and also cover gn
1 \ X' with (3/c)" balls Pisier 1999), we have
PP]a,,...... ....,.....6.. 2a 3v E (Sn-1 Xs): Vg = 1,..., G, sign (Agu) = sign (Agzg)) S e -=x((e//) ppo (48)
Using the bound
47 the upper bound on e, and bounding the resulting probability by &, we obtain
{
kG (5) ( expp-4mmmm exp(kG log( log(?) fmGG
2 exp log( (By7)) ) log( اسyر 4mG]..
Equivalently, m 2
18 2 log
4 8
x +
G log 34 + 1
ã log ( which holds if
8
m [ + ã log( s4 + log(
Recalling, we must have cg. we obscrve that this conditions is met if 18 /
22

---

Published in Transactions on Machine Learning Research (11/2023)
Derivation of 8. Here aim to upper bound the minimum identification error, i.e,, the minimum value of 6, for fixed number of measurements m. The bound in Theorem 7 that is
log(
sAv t log(
(49)
can be rewritten function of å as
(o) + da b
(50)
where
a=
m 4(++g)
and = log 54 54 n + (Gk+n) log
Notice that 6 2 1, and 2 1 from 49
since 0 < 8 < 1. The expression in 550 holds if
8 2 _ (log(a) + b).
(51)
Indeed, 51 implies that log(o) + óa 2 log(6) + log
+ b = log(ad) + b. However, again from as 2 (a) + b 2 1 since a, b 2 1. Therefore, log(d) + da 2 log(ad) + 2
51
we get
Finally, picking the smallest 8 respecting
51 we get for large m, n and G,
8 O k+ log 1-
(52)
which, for n/G < k reads
0 log man 1
(53)
D Sample Complexity Proof
Proof of Theorem 10 We aim to bound the number of different cells associated with the binary mapping sign (A.) which contain at least one element from the signal set X, i.e., siggn (AX) J. Our strategy consists in obtaining global bound on the number of discontinuities of the binary mapping (or in other words, sign changes) over the image of covering of X, which can then be related to the number of different cells that contain at least one element of X.
For < let Qe C X' be an optimal covering of X. If boxdim (X) < k, then there exists an E (0, such that [Qzl S = for all e < 60- Tet us define the number Z(S) of its discontinuous components of the binary mapping sign (A-) over a set S C gn-1 i.e.,
Z(S) = [ : sign (a. $ (S))
From the independence of the {a.) we observe that Z(S) Em Z((S) is a binomial random variable, that is the sum of i.i.d. binary random variables with probability
= P sign (a (a $ (S))
where a is standard Gaussian random vector. From Corollary 12
have
< /ne for any set of the form
S = Sq == (g) ns"=1 with E Ra, Using Bernstein inequality /Vershynin 2018 on the random variable 7(Sg,c) with (S,,) = mp S mynie, we obtain
(lZ(S > 2m S SPZ > 2EZ] S sap(-3mvnee)
Therefore, since IQel S -k we get from a union bound
PIq E Q.: ((S,)) S 2m/ 11- exxeep((llgg()) mmm/ncc.
(54)
Let us fix by setting failure probability
such that & exp(klog(H) {mmnee) ie.
2m 16 (lg({)) + log(?))
(55)
23

---

Published in Transactions on Machine Learning Research (11/2023)
This implicitly imposes my klog(2)) 2) and since min(co. 1/2), we get Gmy klog
8k log
3my'n < 6.
(56)
Since the left-hand side of [66 has to be smaller than min(co: 1/2), we have that (k/(m/n) < min(co, 1/2) (using the fact that > log 2).
For any S S "n the number of cells generated by sign (A-) in this set camnot exceed 2 to the power of the number of discontinuous components in this mapping, L.., sign (AS) s 22(5), Thus, with probability 5, and given E Q..
sign (ASq,)) S 2 [log()) +k log = ( 16
16
(H)
Since there are most -k balls in the covering, and using 56 we obtain the bound
sign (AX) S Egex, sign (AS,,c) I < ()))
3 ) < (
log
We now prove bound on the expected mumber of intersected cells. We first observe that E sign (AX) < EnEx, E sign (ASg,))
and, for any set S C S"-1, the independence of the random variables 2,(5) provides
E sign (AS) < E22(5) E|22..2..05) = E II 2 2
E 22))
Moreover, considering the previous covering 2, of X, if = Squer for some E 2e:
E22((5) =2P(( 0) +2 1) (1 p) + 2p + ps 1 Vne Sevie Therefore, [|| sign (AS,,c) S m and
E sign (AX) S kam log( mmree
The function lllg(2)) + n is convex in and reaches its minimum myn k/mm/n) and imposing k/myn & min(Eo, 1/2), we get
Therefore, by setting
log( myn + k = 1s(1 + log( my
which finally gives
E sign (AX) S (l my())) Te
E Choice of trade-off parameter
We evaluate the impact of the trade-off parameter of the proposed SSBM algorithm for different sampling ratios m/n on the MNIST dataset. In all cases, we use G = 10 operators. Figure shows the average test PSNR of the learned networks. The optimal choice of a decreases with the number of measurements m. the experiments, we choose a 0.1 if m < n and a = 0.06 otherwise.
24

---

Published in Transactions on Machine Learning Research (11/2023)
[dB)
trade-off a
0.63
0.16
0.04
0.25
0.5
2
undersampling m/n
Figure 12: Impact of the trade-off parameter a of the SSBM learning algorithm as function of the sampling ratio m/n network for the MNIST problem with = 10 operators.
25


Reviews:
[{"review_id": "uMfi1GNYuh", "reviewer": "Reviewer_DqqG", "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": "Besides what I have mentioned above in the summary, let me emphasize the following strengths:\n\n1. The paper is well-written and very pleasant to read, and I thank the authors for their effort on this point. \n  Results are well described in the introduction, which makes the paper much easier to read.\n2. The theoretical bounds presented are quite general and of interest, and well discussed.\n3. The self-supervised learning method is a good addition, its precise form is well justified,\n  and the numerical analysis showing that it performed comparatively to supervised learning approaches is convincing. \n\nIn my opinion, the paper has however some issues which would need corrections and improvements. If these are addressed properly I would recommend the paper for publication. These issues are given in the next paragraph on requested changes.", "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 focuses on the problem of reconstructing a set $\\mathcal{X}$ from binary measurements of the type $y_i = \\mathrm{sign}(A x_i)$ for $x \\in \\mathcal{X}$.\nThe authors tackle two problems: signal reconstruction (i.e.\\ estimating the inverse mapping $y \\mapsto x$) and model identification, i.e. the identification of the set $\\mathcal{X}$ provided this set is effectively low-dimensional.\nThe setup chosen is challenging, as the authors aim for a study of unsupervised learning procedures, in which the statistician only has access to $(y_i)_{i=1}^N$, and not the ground-truth signals $(x_i)$.\n\nTo make it tracktable, two separate setups are assumed: \n\n* The measurement operator varies accross observations, that is $y_i = \\mathrm{sign}(A_{g_i} x_i) \\in \\mathbb{R}^m$, and $g_i \\in [G]$. There are here $G$ different (known) measurement operators.\n* The measurement operator does not vary, but the set $\\mathcal{X}$ is known to be invariant under the representation $(T_g)_{g \\in [G]}$ of a finite group.\n\nIn both cases above, the authors derive a set of three theoretical results: \n\n1. A worst-case bound w.r.t. $(A_g)_{g \\in [G]}$ in Section 3.1. For any such measurement operators, there exists a set $\\mathcal{X} \\subseteq \\mathcal{S}^{n-1}$ such that one can not infer $\\mathcal{X}$ with an error smaller than $\\mathcal{O}(n / (mG))$. Having error at least $\\delta$ here means that there are points in the estimated set $\\hat{\\mathcal{X}}$ which are at distance at least $\\delta$ from the true $\\mathcal{X}$.\n2. An upper bound on the estimation error if $A_g$ are taken i.i.d. from a standard Gaussian distribution, in Section 3.2. If $\\mathcal{X}$ has ``effective dimension'' $k$, then the error is (with high probability) at most $\\mathcal{O}([(k+n/G)/n] \\log[nm/(k+n/G)])$, which is sharp up to the logarithmic factor. Furthermore, the authors conjecture (in Section 3.4) that the same error estimate should hold for the signal reconstruction procedure.\n3. Again in the case of Gaussian measurement operators, the authors show in Section 3.4 an upper bound on the minimal number of distinct measurements needed to perform an optimal estimation of the set $\\mathcal{X}$, as a function of $m, n, G$ and the effective dimension $k$ of $\\mathcal{X}$.\n\nThe proofs of the main results are based on classical tools of high-dimensional probability (covering arguments and concentration inequalities). Sections 4 and 5 are dedicated to introducing a self-supervised procedure (i.e. that does not need access to the ground-truth $(x_i)$) to perform signal reconstruction. The method leverages the fact that the statistician has access to $G$ measurement operators, so that she can build ``synthetic'' measurements for each measurement operator using the current estimates $(\\hat{x_i})_{i=1}^N$. The introduction of this approach is completed with numerical experiments on image datasets using random (Gaussian) measurement operators, and comparing this approach with a supervised learning approach as well as other simpler algorithms.\n\nThe paper contains an interesting and well-written discussion of existing literature: however, not being an expert on the topic of model identification, \nI may not be aware of some imporant other works.\nThe theoretical results of the paper generalize previous works to the case of model identification under binary measurements (both signal reconstruction under binary measurements and model identification under linear measurements were studied before).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I will list first the main issues and paths for improvements, before giving a list of more minor points.\n\n**Main issues and improvements --**\n\n1. The acknowledgements mention the funding, which might be a breach of double blindness. \n  I will refer to the editor for this point as I am not sure of the importance of this issue.\n2. The authors write that the self-supervised algorithm presented in Section 4 is motivated by the analysis of model identification in Section 3. How is that so? Perhaps this would deserve more explanation, especially since the algorithm performs signal reconstruction, not model identification.\n3. Why are there so few values of $m$ presented in Figures 6-7-8 ? Adding more values could allows for more convincing plots, e.g. for the scaling with $m$ shown in Figure 6 - right, by taking a large maximal value of $m/n$ (which is at the moment $1.28$).\n4. Why did the authors restrict the choice of the trade-off parameter to be $\\alpha \\in ${0.1, 1, 10}? A more thorough investigation of the optimal choice of $\\alpha$ (at least in some particular cases) would be an interesting addition, \n  as the current choice seems quite arbitrary.\n5. The proofs in appendices contain some mistakes (often easy to fix), and did not always seem to receive the same attention in the writing compared to the main text.While this does not impact the results, the repetition of small mistakes or the lack of clarity can make a bad impression on a careful reader. I list these problems now:\n    + In the proof of Theorem 1 the value of $\\epsilon$ chosen is (I think) not correct, as one obtains $\\delta/\\pi - \\delta/2 < 0$ in the lower bound between eqs. (34) and (35). This will probably change the constants later on and should be corrected.\n    + In the proof of Theorem 6, the equality of eq. (43) should actually be an upper bound, as the vector $v$ does not depend on $g \\in [G]$ there is no reason for it to be an equality.\n    + I think the derivation of $\\delta$ after Theorem 6 should be one of an upper bound on the minimal error $\\delta$ achievable for a given value of $m$, the current presentation of a lower bound is a bit confusing. For this minimal error eq. (61) becomes an equality, and the bound of eq. (63) becomes an upper bound, which is consistent (see the next point). \n    + I missed something in eq.(63): how does it follow from eq.(62)? Also eq.(62) is only valid if $ae^b \\geq 1$, how does this translate to the original parameters?  See also the previous point for a possibly simpler presentation.\n    + One should precise for which values of $\\xi$ eq.(64) holds (even though it holds even for $\\xi$ exponentially small in $n$ I believe).\n    + The argument in the proof of Theorem 8 combining Corollary 10 with a union bound needs to be explained more. To me it seems to be using Bernstein's inequality, which would need to be at least mentioned.\n    + In the proof of Theorem 8, how does the bound on $Z(S)$ transfers to a bound on $|\\Phi(S)|$? This is used in the proof, but not really explained.\n    + In the proof of Theorem 8, should the condition $m\\sqrt{n} / (sk) > e$ be replaced by (the stronger) $3 m\\sqrt{n} / (16sk) > e$?\n\n**Minor points --**\n\n1. In Table 1 one should introduce what the identification error is, since it is only introduced later in the text.\n2. In Theorem 1, the condition on $\\delta$ should be given before the condition on $m$, since the latter depends on the former.\n  Moreover I believe the implication that is proven is $\\mathrm{sign}(Ax) = \\mathrm{sign}(As) \\Rightarrow \\|x - s \\| < \\delta$.\n3. Does Section 3.4 assume $k < m$? It seems so since the arguments use binomial coefficients $\\binom{m}{k}$, but this condition is not written.\n4. Before eq. (25) it would be good to recall that in this setting $T_g$ is a representation of some group under which the set $\\mathcal{X}$ is invariant.\n5. In Figure 6 (and maybe the latter figures as well), one should emphasize that the PSNR grows logarithmically with $\\| x - \\hat{x} \\|$ as it goes to zero, or write on the axis that the unit is in dB, to enhance readability.\n6. In Figure 6 it seems to me that the measurement consistency actually clearly separates from the linear inverse approach for $m/n \\gtrsim 0.5$, not exactly at $m/n = 1$ as stated in the text. Is there an explanation for this phenomenon?\n7. In Figure 8, one should match the names of the different algorithms in the left and right figures.\n8. In the proof of Proposition 3, I think $v$ is just a non-zero element of the nullspace rather than a generator (as the nullspace might have dimension larger than $1$).\n9. The bound of eq. (46) is already used in the proof of Theorem 1 without being stated, it should be first stated there.\n10. It would be good to add a reference for the standard covering number upper bound above eq. (48).\n\n**Other questions --**\n1. Is the bound of Proposition 4 tight (up to constant factors) for some matrices? Proposition 3 shows that if $mG < n$ then it is tight, but what about when $m > n/G$?\n2. In Section 3.3, can one obtain a bound using Proposition 2 or Corollary 5? If model identification is difficult then signal recovery should probably also be difficult, but maybe this is not an interesting bound?\n\n**Typos --**\n1. Before eq. (27), the sentence ``As the first term...'' needs rewriting.\n2. In Figs. 9 and 10, should \"each column'' be \"each row''?\n3. Proof of Theorem 1: \"[...] such that'' should be \"[...] that''.\n4. In eq. (50) the exponent of $\\epsilon$ should be $-kG - n$ not $-kG + n$.\n5. In eq. (51) a minus sign is missing in front of the log in the denominator.\n6. In the proof of Theorem 8, $\\mathcal{X}$ should be replaced by $\\mathcal{Q}$ in several places.\n7. The sentence ``for some $c > 0$'' in the proof of Theorem 8 relates to nothing in the equations.\n8. In the proof of Theorem 8, there is a $2$ missing in the exponent in the last equation (when using the previously derived bound on $|\\Phi(V_\\epsilon(q))|$).", "broader_impact_concerns": "I have no broader impact concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "py3JroNdT6", "reviewer": "Reviewer_x5u4", "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": "This is overall a very good paper. The results proven are novel, relevant to both theoretical and practicioner audiences interested in self-supervised learning in compressed sensing, and rigorously proven. Even with low prior knowledge about this topic, the paper is easy to follow, with helpful diagrams explaining the key concepts of binary recovery.\n\nIt does have some unclear parts in the proofs (see the requested changes section), but this paper is overall very well suited for a TMLR publication.", "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 one-bit compressed sensing, where we observe a one-bit quantization $y$ of the signal $x$ after it went through a sensing matrix $A$. While previous works focused on the reconstruction of $x$ given the knowledge of the signal set $\\mathcal X$, this work focuses on reconstructing the signal set $\\mathcal X$ itself based on multiple observations $y_i$.\n\nThe paper provides upper and lower bounds for this reconstruction set, that match up to logarithmic factors if the set $\\mathcal X$ has low box-counting dimension. They also extend previous results on signal reconstruction from the sparse setting to the more general case with low box-counting dimensions.\n\nFinally, the authors propose a loss for self-supervised learning of the signal, and provide a set of experiments to compare it with supervised or other non-supervised methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "All of the changes can be considered as non-critical\n\n- The identification error should be actually defined, e.g. as $\\min \\\\{\\delta: \\hat{\\mathcal X} \\subseteq \\mathcal X_\\delta\\\\}$\n\n- It might be useful to add a sentence or two after Proposition 2, to explain exactly what has been proven\n\n- Proof of Prop.3: \n    - $v$ is not a necessarily a generator of the nullspace of $\\bar A$, only an element of it\n    - it'd be more intuitive to specify directly that $x$ is in $\\mathrm{Ker}(\\bar A)^\\bot$, instead of the range of $\\bar A^\\top$ (even though it's equivalent)\n    - I personally would've found it more intuitive to fix $x \\in \\mathbb S^{n-1}$ and consider $x \\pm \\eta v$ where $\\eta \\to \\infty$, but this is a personal preference\n\n- Experiments:\n    - you mention the \"necessary condition of Proposition 3\" multiple times; you should either move the $m > n/G$ inside this proposition, or (my preferred option) put this condition in a corollary and refer to it instead.\n\n- Proof of Theorem 1:\n    - the link from (34) to (35) could use a (simple) drawing to explain what's going on\n    - what does the $|$ sign mean in the probabilities ? In any case, I think it should be replaced by \"and\"\n\n- Derivation of $\\delta$:\n    - the link from (62) to (63) is unclear, but you can get (63) by the simpler inequality $W(x) > \\ln(x)/2$ valid for any $x \\in \\mathbb R$\n\n- Proof of Theorem 8: I feel like the use of discontinuity points is a bit circular and non-intuitive; the argument in the proof can be summarized as \n$$ \\text{number of cells} \\asymp \\text{number of cell borders} \\leq \\sum_{q \\in Q_\\epsilon} \\text{number of borders in } B(q, \\epsilon)$$\nwhich is more intuitive than the discontinuity argument.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "YSoNufzErM", "reviewer": "Reviewer_gnaz", "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\nClarity: Paper is well-written and figures like 2 are intuitive and useful.\n\nNovelty: To my knowledge unsupervised learning methods like equivariant imaging have not been applied to binary measurements.\n\n\n## Weaknesses\nThe theory/results are developed/tested without any measurement noise. ", "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 develops, analyzes, and tests an unsupervised learning (learn using only noisy observations) algorithm for reconstructing signals from binary linear measurements (1-bit compressive sensing). The first few sections theoretically lower bound the reconstruction error as a function of the number of measurement matrix size and the number of observations.  The last few sections develop a simple algorithm (essentially equivariant imaging) to train a network to reconstruct signals from binary measurements. It's tested and is proven reasonably effective on MNIST, Fashion MNIST, on CelebA datasets.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "On the first page, I'd use a different word than \"incomplete\" (maybe \"underdetermined\" or \"fat\") to describe the measurement matrix. The word \"incomplete\" has too many alternative meanings, e.g., matrix completion. I'd similarly avoid using \"incomplete\" to describe the measurement process.\n\nI think equation (10) should be an equality between the measurements. Presently (10) states that if the measurements of two points disagree then they must be close to one another with some probability.\n\nThe notation in (14) seems slightly odd. Would it be clearer to write X_d={v\\in S^{n-1}| inf_{x\\in X} ||x-v||<d}\n\nI think the paper would be stronger if one of the tests (e.g., Fig 9) were rerun with varying amounts of measurement noise. At present, it's unclear how sensitive the proposed method is to noise.\n\nTypos:\nAt least on my pdf reader, the Fashion MNIST and MNIST dataset descriptions are missing multiplication signs: 6 10^5\n", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper submitted to TMLR has received unanimous approval from reviewers for its novel and pertinent contributions. The authors have been in particular commended for their response to feedback, providing comprehensive explanations and making corrections that have enhanced the quality of the paper.
Decision: Accept (poster)