Analysis of Sensing Spectral for Signal Recovery under a Generalized Linear Model
Authors: Junjie Ma
Ji Xu
Arian Maleki
Venue: NeurIPS 2021 Poster (2021)
Keywords: phase retrieval
compressed sensing
approximate message passing
statistical physics

Abstract: We consider a nonlinear inverse problem $\mathbf{y}= f(\mathbf{Ax})$, where observations $\mathbf{y} \in \mathbb{R}^m$ are the componentwise nonlinear transformation of $\mathbf{Ax} \in \mathbb{R}^m$, $\mathbf{x} \in \mathbb{R}^n$ is the signal of interest and $\mathbf{A}$ is a known linear mapping. By properly specifying the nonlinear processing function, this model can be particularized to many signal processing problems, including compressed sensing and phase retrieval. 

Our main goal in this paper is to understand the impact of sensing matrices, or more specifically the spectrum of sensing matrices, on the difficulty of recovering $\mathbf{x}$ from $\mathbf{y}$. Towards this goal, we study the performance of one of the most successful recovery methods, i.e. the expectation propagation algorithm (EP). We define a notion for the spikiness of the spectrum of $\mathbf{A}$ and show the importance of this measure in the performance of the EP. Whether the spikiness of the spectrum can hurt or help the recovery performance of EP depends on $f$. We define certain quantities based on the function $f$ that enables us to describe the impact of the spikiness of the spectrum on EP recovery. Based on our framework, we are able to show that for instance, in phase-retrieval problems, matrices with spikier spectrums are better for EP, while in 1-bit compressed sensing problems, less spiky (flatter) spectrums offer better recoveries. Our results unify and substantially generalize the existing results that compare sub-Gaussian and orthogonal matrices, and provide a platform toward designing optimal sensing systems.

Analysis of Sensing Spectral for Signal Recovery Under a Generalized Linear Model
Junjie Ma
Ji Xu
Academy of Mathematics and Systems Science Chinese Academy of Sciences mejuujle@@ssec.coo wc...c...c...o.
Department of Computer Science Columbia University
mixuucs.ccom columbia edu
Arian Maleki Department of Statisties
Columbia University
arian@stat.c. cow.ntttta.couumiaa..a columbia. edu
Abstract
We consider nonlinear inverse problem y f(Ax), where observations y E IR" are the componentwise nonlinear transformation of Ax E Rmm a E R is the signal of interest and A is known linear mapping. By properly specifying the nonlinear processing function, this model can be particularized to many signal processing problems, including compressed sensing and phase retrieval.
Our main goal in this paper is to understand the impact of sensing matrices, or more specifically the spectrum of sensing matrices, on the difficulty of recovering from y. Towards this goal, we study the performance of one of the most successful recovery methods. i.e. the expectation propagation algorithm (EP). We define a notion for the spikiness of the spectrum of and show the importance of this measure in the performance of the EP. Whether the spikiness of the spectrum can hurt or help the recovery performance
EP depends on ʃ. We define certain quantities based on the function I that enables to describe the impact of the spikiness of the spectrum show that for instance, in phasc-retrieval problems, matrices with spikier spectrums are better for EP, while in 1-bit compressed sensing problems, less spiky (flatter) spectrums offer better recoveries. Our results unify and substantially generalize the existing results that compare sub-Gaussian and orthogonal matrices, and provide a platform toward designing optimal sensing systems.
EP recovery. Based on our framework, we are able
Introduction
1.1 Problem statement and contributions
Consider the problem of estimating signal
R2 from the nonlinear measurements:
y = (Arr),
where A E mg is a measurement (or sensing) matrix and f : R y is function accounting for possible nonlinear effect of the measuring process. Here, the function f(-) is applied to Ax in component-wise manner. The above model arises in many applications of signal processing communications [56] 9 255, and machine learning (48 40]. For instance, the phase retrieval problem, which is special case of with f(2 | has received significant interest in recent years
13 10
5 In this paper, we assume that the signal is generic and prior information such as sparsity is not explored.
B D 54 60
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The main goal of our work is to understand the impact of the sensing matrix, or more specifically the spectrum of the sensing matrix, on the difficulty of recovering the signal x from its measurements y. In many applications, one has certain level of freedom in designing the sensing matrix (e.g., transmitter design in communications or the masks used in phase retrieval application) and hence understanding the impact of the sensing matrix on the recovery algorithms is the first step toward the optimal design of such systems. Rather than studying the information theoretic limits, where the computational complexity of the recovery algorithm is ignored, we would like to study the impact of the spectrum of the sensing matrix on efficient algorithms that are used in applications. For this reason, we consider one of the most successful recovery algorithms that has received substantial attention in the last few years, i.e. expectation propagation (EP) [36 38] (referred to as GLM-EP in this paper and study the impact of the spectrum of the sensing matrix on the performance of this algorithm. The EP algorithm studied here is an instance of the algorithm introduced in [22 28 and is
closely related the orthogonal AMP (OAMP) 30 and vector AMP (VAMP) 42 algorithms (in
that all these algorithms use divergence-free denoising functions
30
Similar to the approximate message passing (AMP) algorithm 17.. GLM-EP has two distinguishing features: (i) Its asymptotic performance could be characterized exactly by a simple dynamical system (with very few states) called the state evolution (SE). (ii) It is conjectured that AMP or GLM-EP achieve the optimal performance among polynomial time algorithms 12. [4]. Based on the SE framework, we investigate the impact of the spectrum of the sensing matrix A on the performance of GLM-EP. It turns out that the "spikiness" (or conversely "flatness") of the spectrum of the sensing matrix spectrum has major impact on the performance of GLM-EP. To formalize this statement, we first define a measure of "spikiness" of the spectrum based on Lorenz partial order []] We show that whether the spikiness of the spectrum benefits hurts GLM-EP depends the choice of the nonlinear mapping f (as well as the sampling ratio). For instance, spikier spectrums help the performance of phase retrieval problem (where fxx = (x)) but hurt the performance of 1-bit compressed sensing (where f(x)) sign(z)). We will characterize the classes of functions on which spikiness hurts or helps GLM-EP based on the monotonicity of a function (which is related the scalar minimum mean square error) that will be defined in this paper. As a byproduct of our studies, we will also show that when the spectrum spiky enough, the number of measurements required by GLM-EP to achieve perfect recovery approaches the information theoretical lower bound.
1.2 Related Work.
42 51 28 52 23 [50) have been used extensively for solving the estimation problems similar to the one we have in ①I. As a result of such studies, is known that partial orthogonal matrix is better than iid Gaussian
Message passing algorithms 7 6 45 49
20
21
36 38 31 30, 22 47
matrix for noisy compressed sensing [3I] and the spectral methods for phase retrieval perform better
with iid Gaussian sensing matrices than coded diffraction pattern matrices 22 37 33 19. However,
studying the impact of spectrum of the sensing matrix in the generality of our paper has not been done to the best of our knowledge. Recently. 335 considered the phase retrieval problem and a sensing matrix which can be written as the product of Gaussian and another matrix. They reached the conclusion that the weak recovery threshold with this type of matrices can be made arbitrarily close to zero. As special case of our results, we will also show that if we make the spectrum of the sensing matrix spiky GLM-EP can reach the information theoretic lower bounds in the phase retrieval problem. Aubin et al. 3 the form of deep neural networks with random weight matrices, and showed that it yields smaller katistical-to-algoriite
considered the phase retrieval problem with generative priors in
gap than sparse priors.
Another venue of research that is also related to our work is the derivation of the information theoretic limits for analog compression schemes. Analog compression framework was first introduced in Wu and Verdú [58 59 for compressed sensing. It was shown in Wu and Verdú [58 59 that the minimum number of measurements required for successful signal reconstruction in an information theoretic framework is related to the Rényi information dimension of the signal distribution. Riegler and Tauböck [44] studied the phase retrieval problem using the analog compression framework and proved that (real-valued) phase retrieval has the same fundamental limit as that of compressed sensing. In order to compare the performance of GLM-EP on matrices with different spectrums we generalize the work of [58 59 and AKI and obtain information theoretic limit for our sensing model. Note that
'The name GLM-EP is chosen because the model I is an instance of generalized linear models (GLM).

---

while we are using such information theoretic tools, the problem we are studying in this paper is fundamentally different from the one studied in [58 59 44 Here we are interested in the impact of the spectrum of the sensing matrix on the performance of GLM-EP, and information theoretic limits are mainly derived for comparison purposes (and evaluating the optimality of GL.M-EP).
1.3 Definitions
In this section, we mention some definitions that will frequently used throughout this paper. We first start with the Rényi information dimension of random variable.
Definition 1 (Information dimension
43 58
Let X be real-valued random variable, and Suppose the following limit exists
M [ quantization operator
H ((X)))
d(x)
lim
M-00
log M
where H.) is the entropy of a discrete random variable. The limit d(x) is called the information dimension of X. Further, if H ([X]) < co, then 0 S d(X) S 1.
As will be discussed later, d(X) plays a critical role the information theoretic lower bounds we derive for the recovery algorithms. The next lemma shows how d(X) can be calculated for the simple distributions we observe in our applications.
Lemma (Information dimension mixed distribution 43 58 ). Ler X be a random variable such that H H [[X]) is finite. Suppose the distribution of X can be represented as
Px (1 Pa
where Pa is a discrete measure and Pa is an absolutely continuous measure with respect to Lebesgue, and 0 S p S 1. Then,
d(X) p-
The minimum mean squared error (MMSE) defined below is an important notion in our analysis of GLM-EP.
Definition 2 (MMSE for AWGN channel (27)). Let U) be pair of random variables. The MMSE mmse L2 snr) and the conditional MMSE mmse( snr(U) given are defiedd as
mmse(2,snr)
EE
snr + N 2 Z
(2)
mmse(Z,snr(U) E (Z E snr + N,
where N N(00 1) is independent of (Z, U), and the outer expectation is taken over all random variables involved.
Informattin--heorrtic limit for signal recovery
Our main objective is to evaluate the impact of the spectrum the sensing matrices on the perfor- mance of GLM-EP. Before that, it is useful to compare what GLM-EP achieves with the information theoretic lower bounds, which we derive in this section.
2.1 Assumptions
Before we proceed to the technical part of the paper, let us review and discuss some of the assumptions will be making throughout the paper.
(A.1) The elements of æ are independently drawn from Px, which is an absolutely continuous distribution with respect to the Lebesgue measure. We assume E[ 1.
The notation [z] denotes the largest integer that is smaller than

---

(A.2) Let the SVD of A be A UEVU, U E R and V E R are independent Haar matrices, which are further independent of E. Let {or) be the diagonal entries of Σ and define A; A of We assume that the empirical distribution of {A.).-1 converges almost surely to a deterministic limit Px with compact support [a, b] where 0. Further, we assume that n - A Px.
E[ = m/n 1, where the expectation is with respect to
(A.3) f R + i/ is a piecewise smooth function. Specifically, the domain R can be decomposed into K E 4 non-overlapping intervals, and on each sub-interval, is continuously differen- tiable and either strictly monotonic or constant. Furthermore, we assume H (L)(( < co where Z (0,
Note that Assumption (A.2) is standard assumption in the theoretical analysis of GLM-EP 42 51 20]. Furthermore, all the nonlinearities that we observe in applications satisfy Assumption (A.3). We consider generic signal and do impose any structural assumption. Finally, the independence assumption we have made in the prior of x: is again standard in the literature of approximate message passing and expectation propagation 41 22 57 55]. One can weaken this assumption at the expense of making assumptions about the recovery algorithm.
2.2 Perfect reconstruction in a noiseless setting
In this section, we derive the information theoretic lower bound the number of measurements required by Lipschitz recovery scheme to achieve vanishing error probability. Note that the computa- tional complexity of the recovery algorithm is not of any concern in these lower bounds. We will later compare our results for GLM-EP with these information theoretic lower bounds.
Theorem (Perfect reconstruction under Lipschitz decoding). Suppose Assumptions (A.I)-(A.3) hold. Suppose that there exists an A E m and Lipschitz continuous decoder : : + IR" such that F(x= + (Ax)) + as m, n - oc and m/n + E (1, oo), then necessarily we have
(3)
opt
d(f(Z))
where dzf(Z)) the information dimension of f(Z), where Z N(O, Here, the envor probability is taken with respect to both æ and A.
The proof of this result can be found in the Supplementary Material. Intuitively speaking. d(f(Z)) E [0, may be interpreted as a measurement discount factor and the total number of effective measurements m d(f(Z)).
Remark 1 (1-bit CS). For the 1-bit compressed sensing (CS) problem, we have f(z) sign(2) and d(f(Z)) 0. In this case, the condition ö >> 6 + implies that perfect recovery is impossible in the regime
+ oc and m/n /n + 8 E (1, oo). Notice that our result does not contradict with existing 1-bit CS results [16 40). For instance, Dirksen et al. (66] analyzes the number of random measurements required by corvex minimization algorithm to achieve non-zero larget distortion p. and the bound blows up to infinity as p +
2.3 Stable reconstruction in the noisy setting
Theorem focuses on signal reconstruction for model ( without any noise. For practical considera- tions, is desirable to make sure that a small amount of measurement noise does not cause major performance degradation. In this paper, we consider the following noisy mode
y = f(A + w).
where w ~ (O og T) is independent of A and æ. Define the noise sensitivity minimum mean square error (MMSE) estimator by
18
59 of the
suu M f.8) 2 sup lim Emmsexxly. A)
(5)
n-
o2
'Other types of noisy models are possible, e.g., y 1 f(Ax) + w. Extending our results to these models is beyond the scope of the current paper.

---

where mmse( A) - (x Elzly, ] is the MMSE of estimating æ from and in the above limit - oo is understood as + oo and m + 8. Theorem bbelow shows that to achieve bounded noise sensitivity, one needs å 1/)(f(2)), ) the same necessary condition for achieving vanishing error probability in the noiseless setting. Its proof can be found in the Supplementary Material.
Theorem 2 (Noise sensitivity). Suppose Assumptions (A.1)-A.3) hold. Additionally, assume ~ (0, For any Px. necessary condition for achieving bounded noise sensitivity, namely M (x, < oc, is Sapa where 8 is defined in 3
Note that Theorem 2 different from Theorem iin that it holds for any eigenvalue value distribution PA satisfying Assumption (A.2). Further, we may calculate the MMSE (and hence the noise sensitiv- ity) using the replica method [34]. However, since the correctness of the replica predictions has not been proved for the current setting, we do not pursue it in this paper and leave it as possible future work.
2.4 Discussion of Theorems and 2
Theorems 1 and 2 show that that the quantity d(f(2)) determines the fundamental limit for signal recovery from the nonlinear model (T). Notice that f(2 is mixed pnucrete-contnnoon distribution (by Assumption (A.3)), where the discrete component in f(Z) corresponds to "flat" sections of f; see Figure for illustration. According to Lemma] 1 d( (2)) is simply the weight in the continuous component of the distribution of f(Z), which is the probability of Z ~ (0, 1) falling into the non-flat sections of f. For illustration, Figure shows three representative examples of f.
Type I: / is piece-wise monotone function without flat sections; see the left panel of Figure | for illustration. This type of functions includes the absolute value function = | which appears in phase retrieval problems. For such functions, fZ) has an absolutely continuous distribution when Z AO0 1). and hence d( d2)( = 1 according Lemma |
Type II: f consists of purely flat sections. special case the quantization function. Clearly, f(Z) has discrete distribution and d()( O.
Type III: consists of both flat and non-flat sections, e.g., the function shown on the right panel of Figure [ Note that such scenarios happen when sensors saturate for instance in the phase retrieval application. In this case, f(Z) has a mixed discrete-continuous distribution and < d(f(Z)) 1.
f(z)
f(z)
4 f(z)
(y)
(r)
Figure 1: Three types of f. Left: d(f(Z)) = 1. Center: d(f(2)) = 0. Right: < d(f(2)) < 1.
3 GLM-EP algorithm and performance analysis
type algorithm, referred to GLM-EP, for solving our nonlinear inverse problem and derive its state evolution (SE). We then study the impact of the spectrum of the sensing matrix on the performance this algorithm.
In this section, we introduce an expectation propagation (EP) 36 38
3.1 Summary of GLM-EP
The GLM-EP algorithm is summarized below. We superscripts represent iteration indices, and subscripts 'I' and 'y' to distinguish different variables.
Initialization: ,, 0, v. 1. For t O...., excute the following steps iteratively:

---

2f 1 (1t (zt y.
(1= t- , - -. )
(6a)
,2 .1, of =f (1) 1 y, 2/ 1)
(6b)
(2) y, ot )))
R¹ A (vfI + A A -1 AT.
AT)
(6c)
1
-R'- Tr(RR)) (R'=) -1) z1,
(6d)
m Tr(Rt)
Tr(R))
o/ of 1 (
(6e)
where 7/2 is defined by
7z v) Sr (()) u -NNu; 2r, v)du
(6f)
J '(v) N(u; 2r, v)du
and v/g denotes the derivative of 7/= with respect to the first argument. When f-) a discrete set, the integration in the above formula is simply replaced by summation.
Output: Lu = of [ + vf A AATA
In the above descriptions of the algorithm, we adopted the convention commonly used the AMP literature: 1)= (2,, v) denotes a vector with elements obtained by applying the scalar function 1)= to the corresponding elements of 2, and y, and (+) denotes the empirical mean of vector.
3.2 Asymptotic analysis
The asymptotic performance of GLM-EP could be described by two scalar sequences (Vi, V 7220. defined recursively by
V
- ((V(-1),
(7a)
mmse; (V,-1)
V
V
- (VV')
(7b)
VIA
Vi
E
where V--1 1--0 = L, mmse, (1,) mmse ( (2 lff())). and the expectation in (76) is w.r.t.
the limiting eigenvalue distribution of ATA A. (Recall that mmse( snr(U) denotes conditional MMSE; see (2) Equations (7a) and 7bb are known as the state evolution (SF) for the GLM-EP.
Roughly speaking, the deterministic sequences (V/. V122 are expected to be accurate predictions of (of, of Jr2 (which are generated by GLM-EP) asymptotically, We will formalize this claim below. Further, we will show that the per coordinate MSE of æ (see Lemma 2 below) is characterized by
V
MSE (V7)
E
(7c)
The subscript emphasizes the fact that the MSE depends on the limiting eigenvalue distribution Px-
Lemma 2 below gives a formal statement of the accuracy of SE, and its proof is mainly based on that of [23] Theorem 1]. Note that 23 requires the continuity of f and 7)- While this assumption holds for some problems, e.g. phase retrieval problem, it is violated for some other problems, e.g. one-bit quantization. Hence, we construct new algorithm, called GLM-EP-app hereafter, which satisfies the requirements of (23). This allows us to use SE for predicting the performance of this algorithm. Please note that if ʃ and y)= are Lipschitz continuous, then we can use GLM-EP well. LLM-EP-app uses the following iterations:
2 C.
(z) t-1
M. -B
[ii ,Y, -
(8a)
x
1
(R'
- z
(8b)
1
1 Tr(R.)
m

---

where i is function for which E [7 ,Z, exists. R - A (V/I+ -TA) AT, and Ce is a sequence of fixed numbers. The choices we choose for ýj and C2 (to make them close enough to GLM-EP) is discussed in the proof of Lemma 2 Finally, similar to GLM-EP the output of GLM-EP-app is given by
S - V/ VV A
Lemma 2 shows that the performance of GLM-EP-app could be arbitrarily close to the SE prediction. The details of the proof can be found in Supplementary Material.
Lemma 2. Suppose Assumptions (A.1)-A.3) hold. Additionally, assume f - V) to be Lipschitz continuous. Let {V7, , V F120 be generated according to 7 There exists iis and {Ci)120 such that á out of GLM-EP-app satisfies
MSEX(VI)) - -
|| Lout x1|2 MSEX(V()) t Ve > 0,
(9)
almost surely as m, n - oo with m/n 8 00), where MSE, defined
7c
According to Lemma 2 the asymptotic MSE of GLM-EP-app in the large system limit as can be obtained from the limiting value of V (or V/). Because this quantity of particular importance to will characterize it in the following lemma.
Lemma (MSE performance). Suppose ō > 1. Define V by
VI - inf { I [0,1] : P(v,) > O, Ve, E [e, 11}3
(10)
where
(vv))
1 - mmse: (1x))
P(e,) E
(11)
(v())) +
UF
g(m,)
Let (V7, V2 3120 be sequences generated according to with V
have
lim V
1-000
Further, the final MSE is given by MSE; (oV;)))(;))) where o is defined in (7a)
The proof of this lemma can be found in Supplementary Material. A direct consequence of Lemma is the perfect reconstruction condition stated in Lemma below.
Lemma 4 (Perfect reconstruction condition). Let {Vi', V/312 be sequence generated through with V. = 1. Then, the predicted final MSE MSE;, is zero if and only if
P(e,) where (vx,)) is defined in (1). Furthermore, necessary condition for 12 is defined in
> 0, Vu, E (0,
(12)
80 where 50
The proofs can be found in the Supplementary Material.
4 Impact of sensing matrix spectrum
In this section, we use Lemmas and to study the impact of the sensing matrix on the MSE performance of GLM-EP-app. Before presenting our detailed analysis, first discuss the so-called Lorenz order that compares the "spikiness" of different distributions.
4.1 measure spikiness of distributions
A natural tool to compare the spikiness of the distributions of two non-negative random variables is Lorenz partial order [1] (Since is partial order, there exist distributions that are incomparable in the Lorenz sense.) Lorenz order is well-known in economics to characterize the wealth inequality of different populations. Lorenz order is closely related to majorization, tool that has been extensively studied for transceiver design in communication systems [39].

---

Definition 3 (Lorenz partial order M... Consider nonnegative random variable with cumulative density function Fxx). Let F (y) be the quantile function defined by
(v) suplæ: F()) S v), 0 0<ソ<1.
(13)
The Lorenz curve corresponding to (xx) is defined by
L(u) Le F (
0 uss
Jo (y)d
X and Y be two nonnegative random variables, and xx (u) and Ly(u) be the corresponding Lorenz curves. We say that X is less spiky than Y in the Lorenz sense, denoted X 31 Y, if (u) 2 Ly (u) for every u E [0, 1]. Conversely, X = Y if Lx()) S Ly (u) for every u E [0, 1].
An important property of Lorenz partial ordering is the following.
Lemma 5 (.) Suppose X > 0, Y 0 and E E[Y]. We have X 31 Y if and only if
([) & B()(Y)) for every continuous convex function h IR, - TR.
4.2 Impact on MSE
Let \ι Ps and X2 Px2 be limiting eigenvalue distributions of A ATA. Let VX, and V
denote the corresponding limiting values of V (as оo) in 7 (proving that the iterations converge to a fixed point is straightforward, The associated MSEs, denoted as MSE,, and MSE can be compared according to the following lemma.
Lemma 6. Let 8 1. Suppose Px2 is more spiky than Px₂ in the Lorenz sense, iee, ò EL d2- Define
G(v,) - max (o(uz), 0), Vu, E [0,
(14)
where g(-) is defined in (II. We have
Gv, is increasing e E [0, 1), then MSE,, MSE,,
If (v,) is decreasing on v, E [0, 1]. then MSEX, Z MSE
G(,,) is not monotonic, then the comparison of MSE and MSE,, is not definite.
0.8
0.8
0.8
0.6
0.6
0.5
0.4
0.4
0.4
10
10
10-²
10a1
10
10.5
10a
Figure 2: Illustration of G(u,) for three choices of f. Left: f(z) = =|2]. Middle: f(z) = sign(=).
Right: f(z) | + (|2) 1)1 5 5= 1.1.
Remark 2. Notice that the function G(v.) also depends on the sampling ratio as can be seen from the definitions in (14) and (TT). (To keep notation light, we do not make such dependency explicit.) Hence, for given f. the monotonicity of G(v,) could change as varies.
Lemma 6 shows that the impact of the spectrum on the final MSE performance of GLM-EP-app depends on the monotonicity of the function G(v,) (which further depends on f) and the sampling ratio ò, For given of and ó, the function G(v,) can be numerically computed and its monotonicity

---

can be easily checked. Below are three examples of f, corresponding to each of the cases discussed Lemma
Example 1: It can be shown that that G(u,) of the following f monotonically increasing for all 8>1 1:
f(z) |z|.
See left panel of Figure 2
Hence, spiky spectrums are beneficial for MSE performance.
Example 2: The G(v)) of the following function is decreasing for all d > 1:
f(2) sign(2).
See the middle panel of Figure In this case, flatter spectrums are better.
Example 3: Consider the following function
|2|, if | <
f(=)
(15)
|2| -
if
2| 1.
In this case, G(v,) is not monotonic (See right panel of Figure 2. and other features of the spectrum affect the performance of GLM-EP-app.
4.3 Impact of spectrum on perfect recovery threshold
We have shown that the impact of the spikiness of the spectrum on the MSE performance is related to the monotonicity of the function G(v,)) which depends the nonlinear function and the sampling ratio 6. In this section, we will show that if our goal is to minimize the number of measurements required for perfect reconstruction, then more spiky spectrum benefit GLM-EP-app for all f. Furthermore, the information theoretic lower bound o can reached (as close as we wish) if the spectrum of A is spiky enough. Theorem 3 whose proof can be found in the Supplementary Material, summarizes the above discussions.
Theorem 3. For given nonlinearity f and eigenvalue distribution Px. let 8% be the minimum ò required for perfectly recovering the signal, i.e.,
59 inf {8 =
(16)
where MSE₁ is defined in Lemma 3 Let \1 and A2 represent two limiting eigenvalue distributions and 8% and 02 the corresponding thresholds for perfect reconstruction. We have
(i) \ L X2, then 8%, S 0
(ii) For any f satisfying mmse; (1) < and 80p < co, there exists a distribution of X for which 8% is arbitrarily close to 80ps. _ 1/d(f(Z)), where Z (O,
4.4 Noise Sensitivity Analysis
Up to now, we only studied the performance of GLM-EP-app the noiseless setting. In practice, it is also important to guarantee that the reconstruction performance does not significantly worsen due to the presence of a small amount measurement noise. We consider the noisy model in (4). GLM-EP-app remains unchanged except that 1), is replaced by posterior mean estimator that takes the noise effect into consideration.
The following lemma analyzes the MSE performance of GLM-EP-ape app in the high SNR regime, and shows that reconstruction is stable. The proof of Lemma 7 and other details about GI-M-FP-app in the noisy setting are provided in the Supplementary Material.
Lemma 7. Assume dZ)( + O. Let ö >> 62, where 8%, is defined in Theorem Let MSE, (o e
lim MVE)(V?) be the MSE in the noisy setting, As o2 + O, we have
MSE; (o = f)E [>-1] 0z (1 o(1)).
where < C( oo is a constant depending only on and f.
This lemma confirms that as long as 8 > 8%. GLM-EP-app can offer stable recovery. However, the minimum mean square error in this case depends on another feature of the spectrum, namely [A- The optimal sensing mechanism should be designed by considering both features based on the expected noise level in the system.

---

5 Numerical examples
A
= = -EV.. In experiments, approximate the random orthogonal matrix U in the following way: U = P.U.P.UJ. P3 where P1. P2, P3 are three diagonal matrices with entries independently chosen from +1 with equal probability, and Ua is discrete cosine transform (DCT) matrix. Note that all matrices are square. The hope is that by injecting enough randomness in these matrices,
make them look like Haar orthogonal matrices for GLM-EP In addition, such constructions allow fast implementation of GLM-EP using the DCT. Following [53], we consider a geometric distribution for the limiting empirical distribution of diag E Σ):
.x i (aA(3)e ,aA(3)) 0,
Pa 8)
(17)
otherwise,
where a >> is the mean, 3 2 controls the spikeness of the distribution (with 3 0 corresponding flat spectrum), and A(3) T-e T. In all of our numerical experiments, the eigenvalues of A are independently drawn from Px(
St
0.0
0.8
0.7
0.5
2 0.
0.4
0.4
03-
02
0.2
031
0.1
Senaton
haration
Figure 3: Noiseless reconstruction performance of GLM-EP. Left: f(z) = |z]. Right: f(z) defined in (5) n x 10a. m [1.01 nn]. 3 = 20. 1000 independent runs. The markers labeled 'SE' are predictions obtained from state evolution.
Figure demonstrates the performances of GLM-EP for f(2) = |2| and the function defined in (15). Clearly, dZ) for both functions. As Theorem shows, the GLM-EP algorithm could achieve perfect reconstruction as soon as 5 > 1 with a very spiky sensing matrix. Here, we considered the geometric eigenvalue setup with / = 20. From Fig. 3 we see that GLM-EP recovers the signal accurately when is only slightly larger than the lower bound (5 = 1.01). In our experiments, to
get rid of the uninformative fixed point we set x,- (1+1) 1- vVn) where n is standard Gaussian and V is large constant (here we V = 20).
More experimental results can be found the Supplementary Material.
Future work
The results in this paper can serve as the first step toward the optimal design of sensing matrices for the nonlinear model y = fAAx). However, there are several directions that require further investigation before one can apply our results to real-world applications: (i) Because the structure of the signal often used in recovery algorithms, the role the structure should be studied more carefully when we deal with spiky sensing matrices. (ii) While we discussed the high-signal-to-noiss ratio regime in the paper, some applications have low signal-to-noise ratios. The impact of the spectrum of the sensing matrix in such cases requires more careful considerations.
10

---

Acknowledgments and Disclosure of Funding
J. Ma was partially supported by National Natural Science Foundation of China (Grant NO. 12101592) and the Key Research Program of the Chinese Academy of Sciences (Grant NO. XDPB15). A. Maleki was partially supported by a Google Faculty Research Award.
References
[1] Barry C Amold and José María Sarabia. Majorization and the Lorenz order with applications in applied mathematics and economics. Springer, 2018.
[2] Benjamin Aubin, Antoine Maillard, Jean Barbier, Florent Krzakala, Nicolas Macris, and Lenka Zdeborová. The committee machine: Computational to statistical gaps in learning a two-layers neural network. Journal of Statistical Mechanics: Theory and Experiment, (019(12):22402)) 2019.
[3] Benjamin Aubin, Bruno Loureiro, Antoine Baker, Florent Krzakala, and Lenka Zdeborová. Exact asymptotics for phase retrieval and compressed sensing with random generative priors. In Mathematical and Scientific Machine Learning, pages 55 73. PMLR, 2020.
[4] Sohail Bahmani and Justin Romberg. Phase retrieval meets statistical learning theory: A flexible convex relaxation. In Artificial Intelligence and Statistics, pages 252-260, 2017.
[5] Milad Bakhshizadeh, Arian Maleki, and Shirin Jalali. Using black- compression algorithms for phase retrieval. IEEE Transactions on Information Theory, 66 1171287777-8001 2020. doi: 10.1 109/T..00...0000. 3016183.
[6] Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, and Lenka Zdeborová. Optimal errors and phase transitions in high-dimensional generalized lincar models. Proceedings of the National Academy of Sciences, 116(12)5451-5446 2019.
M. Bayati and A. Montanari. The dynamies of message passing dense graphs with applications compressed sensing. IEEE Transactions on Information Theory, 57(2):764-) 785, Feb. 2011.
[8] M. Bayati and Montanari. The LASSO risk for Gaussian matrices. IEEE Transactions on Information Theory, 58(4): 1997)2999999771 April 2012.
[9] Ali Bereyhi, Saba Asaad, Ralf Müller, and Symeon Chatzinotas. RLS precoding massive MIMO systems with nonlinear front-end. arXiv preprint arXiv:1905.05227. 2019.
[10] Petros Boufounos and Richard G Baraniuk. 1-bit compressive sensing. In 2008 42nd Annual Conference on Information Sciences and Systems, pages 16-21. IEEE, 2008
[11] Zhiqi Bu, Jason M Klusowski, Cynthia Rush, and Weijie J Su. Algorithmic analysis and statistical estimation of SLOPE via approximate message passing. IEEE Transactions on Information Theory, 67(1): 506-537, 2020.
[12] E. J. Candes, X. Li, and M. Soltanolkotabi. Phase retrieval via wirtinger flow: Theory and algorithms. IEEE Transactions on Information Theory, 1185):1985-2007, April 2015.
[13] Emmanuel J Candes, Thomas Strohmer, and Vladislav Voroninski. Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming. Communications on Pure and Applied Mathematics, 144--1274, Nov. 2013.
[14] Michael Celentano, Andrea Montanari, and Yuchen Wu. The estimation error of general first order methods. In Conference on Learning Theory, pages 1078-1141 1141. PMLR, 2020.
[15] Yuxin Chen and J. Candes. Solving random quadratic systems of equations is nearly as casy as solving linear systems. Communications on Pure and Applied Mathematics, 70:822-883, May 2017.
[16] Sjoerd Dirksen, Hans Christian Jung, and Holger Rauhut. One-bit compressed sensing with partial gaussian circulant matrices. arXiv preprint arXiv:1710.03287. 2017.
[17] David L. Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed sensing. Proceedings of the National Academy of Sciencex, 196(45):199144188))) 2009.
[18] David L Donoho, Arian Maleki, and Andrea Montanari. The noise seniee-ennitivityy phase transition in com- pressed sensing. IEEE Transactions Information Theory, 57(10):6900-694) 2011.
11

---

[19] Rishabh Dudeja, Milad Bakhshizadeh, Junjie Ma, and Arian Maleki. Analysis of spectral methods for phase retrieval with random orthogonal matrices. IEEE Transactions Information Theory, 66(8):5182-5203. 2020.
[20] Zhou Fan. Approximate message passing algorithms for rotationally invariant matrices. arXiv preprint (xXi::2008.11892 2020.
[21] Oliver Y Feng, Ramji Venkataramanan, Cynthia Rush, and Richard Samworth. A unifying tutorial on approximate message passing. arXiv preprint arXiv:2105.02 00..000..0.0..... 2021.
[22] Alyson Fletcher, Mojtaba Aadrace-Ardakan, Sundeep Rangan, and Philip Schniter. Expectation consistent approximate inference: Generalizations and convergence. Information Theory (ISIT), 2016 IEEE International Symposium on, pages 190-194. IEEE, 2016.
[23] Alyson K Fletcher and Sundeep Rangan. Inference deep networks in high dimensions. arXiv preprint arXiv:176..665 06540,66449220 2017.
[24] Bing Gao, Xinwei Sun, Yang Wang. and Zhiqiang Xu. Perturbed amplitude flow phase retrieval. IEEE Transaction on Signal Processing, 68:5427-5440, 2020.
[25] Martin Genzel and Peter Jung. Recovering structured data from superimposed non-linear measurements. IEEE Transactions on Information Theory, 66(1):453-477, 2020. doi: 10. 10.11099122209929922444
[26] T. Goldstein and Studer. Phasemax: Convex phase retrieval via basis pursuit. IEEE Transactions on Information Theory, 64(4):2675-2689, April 2018.
[27] Dongning Guo, Shlomo Shamai, and Sergio Verdú. Mutual information and minimum mean-square error in gaussian channels. 11(4))1261-128) 2005.
[28] Hengtao He, Chao-Kai Wen, and Shi Jin. Generalized expectation consistent signal recovery for nonlinear measurements. In Information Theory (ISIT), 2017 IEEE International Symposium on, pages 2333-2337.
TEFE, 2017.
[29] Yue M Lu and Gen Li. Phase transitions of spectral initialization for nigh-dimensional non-convex estimation. Information and Inference: A Journal of the IMA, 93)::577-44, 2020.
[30] Junjie Ma and Li Ping. Orthogonal AMP. IEEE Access, 5:2020-2033, 2017.
[31] Junjie Ma, Xiaojun Yuan, and Li Ping. On the performance of turbo signal recovery with partial DFT sensing matrices. IEEE Signal Processing Letters, 22(10):1580- -580-14458--1 2015.
[32] Junjie Ma. Ji Xu, and Arian Maleki. Optimization- based AMP for phase retrieval: The impact of initialization and & regularization. IEEE Transactions on Information Theory, 65(6), June 2019.
[33] Junjie Ma, Rishabh Dudeja, Ji Xu, Arian Maleki, and Xiaodong Wang. Spectral method for phase retrieval: an expectation propagation perspective. IEEE Transactions on Information Theory, 67(2): 1355. 2021.
[34] Antoine Maillard, Laura Foini, Alejandro Lage Castellanos, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. High-temperature expansions and message passing algorithms. Journal of Statistical Mechan- ies: Theory and Experiment, (019(11):11330) 2019.
[35] Antoine Maillard, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Phase retrieval in high dimensions: Statistical and computational phase transitions. Advances Neural Information Processing Systems, 33, 2020.
[36] Thomas Minka. Expectation propagation for approximate bayesian inference. In Proceedings of the Seventeenth conference on Uncertainty in artificial intelligence, pages 362-369. Morgan Kaufmann Publishers Inc., 2001.
[37] Marco Mondelli and Andrea Montanari. Fundamental limits of weak recovery with applications to phase retrieval. arXiv preprint arXiv: (e0:::70800000 17080032,, 2017.
[38] Manfred Opper and Ole Winther. Expectation consistent approximate inference. Journal of Machine Learning Research, 6DDe0)21177-2244 2005.
[39] D. P. Palomar, J. M. Ciofti, and M. A. Lagunas. Joint Tx-Rx beamforming design for multicarrier MIMO channels: unified framework for convex optimization. IEEE Transactions on Signal Processing, 51(9): 1281, Sep. 2003.
12

---

[40] Yaniv Plan and Roman Vershynin. The generalized lasso with non-linear observations. IEEE Transactions information theory, 62(3):122-15377, 2016.
[41] S. Rangan. Generalized approximate message passing for estimation with random linear mixing. In JEEE International Symposium on Information Theory Proceedings, pages 2168 2172, July 2011.
[42] S. Rangan, P. Schniter, and A. K. Fletcher. Vector approximate message passing. IEEE Transactions on Information Theory, 65( 66666666664466,4 Oct 2019.
[43] Alfréd Rényi. On the dimension and entropy of probability distributions. Acta Mathematica Academiae Scientiarum Hungarica, 10(1-2):133-215, 1959.
[44] E. Riegler and G. Taubück. Almost lossless analog compression without phase information. In 2015 IEEE International Symposium on Information Theory (ISIT), pages 999-1003, June 2015.
[45] Cynthia Rush and Ramji Venkataramanan. Finite sample analysis of approximate message passing algorithms. IEEE Transactions on Information Theory, 64( (4(11))7264-7286 2018.
[46] Philip Schniter and Sundeep Rangan. Compressive phase retrieval via generalized approximate message passing. IEEE Transactions on Signal Processing, 63(4):1043-1055, 2015.
[47] Philip Schniter, Sundeep Rangan, and Alyson K Fletcher. Vector approximate message passing for the generalized linear model. In 2016 50th Asilomar Conference on Signals, Syxtems and Computers, pages 1525-1529, IEEE, 2016.
[48] Takashi Shinzato and Yoshiyuki Kabashima. Perceptron capacity revisited: classification ability for correlated patterns. Journal of Physics A: Mathematical and Theoretical, 41(32)3324013, 2008.
[49] Pragya Sur and Emmanuel J Candès. A modern maximum-likelihou theory for high-dimensional logistic regression. Proceedings of the National Academy of Sciences, 116((9): 14566-914516-4555 2019.
[50] Takashi Takahashi and Yoshiyuki Kabashima. Macroscopic analysis of vector approximate message passing in model mismatch setting. 2020 IEEE International Symposium on Information Theory (ISIT), pages 1403-1408. IEEE, 2020.
[51] K. Takeuchi. Rigorous dynamics pnpeecatiionpropaaaatinn--oo signal recovery from unitarily invariant mcasurements. IEEE Transactions on Information Theory, pages 1-1, 2019.
[52] Keigo Takeuchi. A unified framework of state evolution for message-passing algorithms. 2019 IEEE International Symposium on Information Theory (ISIT), pages 151-155. IEEE, 2019.
[53] M. Vchkaperä, Y. Kabashima, and S. Chatterjee. Analysis of regularized LS reconstruction and random matrix ensembles in compressed sensing. IEEE Transactions on Information Theory, 62(4):2100 April 2016.
[54] G. Wang, G. B. Giannakis, and Y. C. Eldar. Solving systems of random quadratic equations via truncated amplitude flow. IEEE Transactions on Information Theory, 64(2):733774, Feb 2018.
[55] Shuaiwen Wang, Haolei Weng. Arian Maleki, et al. Which bridge estimator is the best for variable selection? Annals of Statistics, 48(5):271--2823, 2020.
[56] Y-C Wang and Z.Q Luo. Optimized iterative clipping and filtering for PAPR reduction of OFDM signals. IEEE Transactions on Communications, 59(1):33-37, 2010.
[57] Haolei Weng, Arian Maleki, Le Zheng, et al. Overcoming the limitations of phase transition by higher order analysis of regularization techniques. Annals of Statistics, 46(6A):3099-3119 2018.
[58] Y. Wu and S. Verdú. Récnyi information dimension: Fundamental limits of almost lossless analog compression. IEEE Transactions Information Theory, 56(8) -748, Aug 2010.
[59] Y. Wu and S. Verdú. Optimal phase transitions in compressed sensing. IEEE Transactions on Information Theory, 58(10)6221 -6263, Oct 2012.
[60] Huishuai Zhang and Yingbin Liang. Reshaped wirtinger flow for solving quadratic system of equations. In Advances in Neural Information Processing Systems, pages 2622 2230, 2016.
13


Reviews:
[{"review_id": "kr599POEVH", "reviewer": "Reviewer_7HR7", "summary": "The paper considers a general class of non-linear inverse problems. It first provides a necessary condition for Lipschitz guarantee in terms of information dimension based on nonlinear operations. The authors also consider expectation propagation algorithms and their analysis using state evolution. They introduce the notion of spikiness based on the impact of sensing matrix spectrum on MSE analyzed using SE. An interesting result of the paper is that if the spectrum is spiky enough, the information theoretic bound can be achieved (Theorem 3). \n", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Overall, the paper is very well written and I enjoyed reading it. The proofs seem sound, although I glanced over them and their structure. Using Lorenz order for performance analysis of EP seems novel and interesting. \n\nI would like to raise two issues of the paper and am curious about the answers:\n- Input structure is overlooked. This is mentioned in the conclusion part too, but I think it deserves more detailed discussions in the main part of the paper. As I argue below, some of the conditions are overly pessimistic. \n- The results are purely qualitative. The authors could use the algorithm and plot the phase transitoin for different choice of non-linearity and spikiness. The experiments could help to compare the current result along side similar result on the generalized linear models (see comments below).\n\n\nMore comments:\n\n- How does the result of Theorem 1 compare with Wu-Verdu bounds? As I see it now, the information dimension in Theorem 1 depends merely on the structure of the function f and not the input. Therefore, the theorem cannot give Wu-Verdu’s result as a special case, which is stated in terms of input information dimension. For example, for identity function, delta should be bigger than 1, which is very pessimistic.\n\n- The result of Theorem 1 is also pessimistic for 1-bit compressed sensing. There are already recovery guarantees for 1-bit CS assuming input sparsity for Gaussian and sub-Gaussian matrices (see the survey paper from S. Dirksen). But the current theorem gives delta>infty, which is a sort of impossibility result.\n\n- Following up on 1-bit CS, if d(f(Z))=0 for this case, how can one interpret theorem 3 for EP algorithm? The authors should clarify if we expect to get better non-asymptotic results for EP and therefore using it in this context is still sensible. Having numerical results could help better interpret the results of the paper.\n\n-On the other hand, the result for phase retrieval is optimistic with d(f(Z))=1, which is the same as not having any non-linearity. Having numerical results could significantly help the message of the paper.\n\n-The notion of spikiness is also very interesting but lacks experimental backup. The  authors could design experiments verifying each one the claims for different setups for example 1-bit CS and phase retrieval.\n\n- How does the information dimension bound compares with the recovery guarantee for Generalized lasso in Plan-Vershynin paper?\nhttps://arxiv.org/abs/1502.04071\nIn that paper, the authors consider similar GLM setup and provide bounds that depend, in a similar fashion, on the non-linearity modulated by a Gaussian random variable (parameters mu and sigma in that paper). The comparison can be very interesting and relevant.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "aG7smo33DAf", "reviewer": "Reviewer_d33P", "summary": "The paper considers a non-linear inverse problem y = f(Ax). The goal is to recover the signal x from the observations y, where A is the sensing matrix and f is component-wise non-linear function. The paper studies the impact of the sensing matrix spectrum and f properties on the recovery performance. Their theorems show that depending on f, the spikiness of the sensing spectrum may improve or worsen the expectation propagation algorithm recovery.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Non-linear inverse problems is of interest to the society. The paper takes an interesting approach to study the recovery using the spectrum of the sensing matrix and the property of non-linear function. Proper citations and explanation is provided on the assumptions made. The paper proposes several theorems such as the impact of the sensing matrix spectrum on signal recovery. However, the main concern is that there is no numerical results to support and verify the theorems. In the absence of such numerical experiments showing the recovery performance as f, the size of A (i.e., m and n) and its spectrum changes, paper lacks the NeurIPS publication standards. Below are minor comments.\n\n- The wording and the organization need improvement.\n\n- Sufficient related work is provided. For better clarity and organization, I suggest that the content related to the author's work in Section 1.2 to be moved to Section 1.1, and leave Section 1.2 to focus on related works.\n\n- Abbreviations (e.g., MMSE and AWGN) should be defined at the first time that they are used.\n\n- The statement at line 109-110 is repeated multiple times within the paper. I recommend to emphasize only once or twice.\n\n- For better clarity, a brief notation explanation is recommended (e.g., capital letters stands for ..., bold letters stands for ...)\n\n- Recommend to show Section 3.1 as an \"Algorithm\".\n\n- Line 262, There are typos (e.g., \"is is ..\").", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are breifly discussed in the conclusion. However, no societal impact is provided.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "KHCr7dyZFCR", "reviewer": "Reviewer_fMoa", "summary": "This paper studies the influence of the sensing matrix on the recovery of signals in noiseless generalized linear models The authors define a mathematical property of a given spectrum, that they call “spikiness”. Given a specific activation function, the authors characterize the behaviour of the MSE and of perfect recovery threshold of the signal (as a function of the sampling ratio) depending on the spikiness of the singular value distribution of the sensing matrix. In particular, they show that for all non-linearities, more “spiky” spectrums always possess smaller (i.e. better) perfect recovery thresholds. Some generalizations are also given for simple instances of noise, namely when it is added before the non-linearity as $\\mathbf{y} = f(\\mathbf{A}\\mathbf{x} + \\sigma_w \\mathbf{w})$ with $\\mathbf{w} \\sim \\mathcal{N}(0,1)$, and infinitely small $\\sigma_w \\downarrow 0$. \n\nNote that I could not check the calculations and proofs given in the supplementary material.\n\n**I edited this review to modify my score, according to the comments below**", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "I found the paper overall well-written (with very few typos, see below) and pleasant to read. However in my point of view, some points lack discussion, and it is hard to see the scope of many results, as I detail below.\n\nOverall, I believe this paper is above the acceptance threshold of NeurIPS 2021, and could have interest for the community of information theory and statistical-physics approaches to learning. However the authors should dismiss some of the comments and criticisms expressed hereafter. I believe the majority of these issues are more related to the discussion of the results than to the scientific content itself, which I found quite interesting. \n\n**Strengths of the paper**\n\n- As I mentioned, the writing of the paper is good. Previous literature is cited quite thoroughly, with some minor misses, see below.\n\n- Concerning the comparison of the MSE achieved by different spectrums (Section 4.2), for some very common choices of activation (sign, absolute value) the results are strong, as the function $G(v_r)$ is monotonous, so the results allow to precisely compare the performance of two spectrums (if one is more spiky than the other).\n\n- On the other hand, for any non-linearity the authors present interesting results on the comparison of the perfect recovery thresholds for the algorithm.  In particular, they show that they can build sensing matrices that reach a spectrum-independent lower bound: e.g. in real noiseless phase retrieval, this amounts to build spectra that have perfect algorithmic recovery already at $\\delta = 1$ (as in [1]).\n\n[1] AUBIN, Benjamin, LOUREIRO, Bruno, BAKER, Antoine, et al. Exact asymptotics for phase retrieval and compressed sensing with random generative priors. In : Mathematical and Scientific Machine Learning. PMLR, 2020. p. 55-73. \n\n- Previous results are shown to be stable against some types of noise (in Sections 2.3 and 4.4), which adds relevance to the analysis, as in many actual applications (e.g. compressive sensing) the observations are indeed affected by noise.\n\n**Main concerns and remarks**\n\n- Being quite used with the AMP literature, I am a bit puzzled by the use of the “GLM-EP” algorithm. While the authors mention briefly its links with Vector Approximate Message Passing in the introduction, I would have liked to understand better if there is an actual reason to not choose this algorithm which is described for the GLM in [2] (and also possesses a well-studied State Evolution, and is in my point of view more widely used), or if it would be an equivalent choice which would yield the same results.\n\n[2] SCHNITER, Philip, RANGAN, Sundeep, and FLETCHER, Alyson K. Vector approximate message passing for the generalized linear model. In : 2016 50th Asilomar Conference on Signals, Systems and Computers. IEEE, 2016. p. 1525-1529. \n\n- I am bit puzzled about the impact of the results for discrete outputs: the lower bound of Theorem 1 is $\\delta_\\mathrm{opt} = + \\infty$ since $d(f(Z)) = 0$.  Are Theorems 1, 2 and 3 informative for such problems (e.g. 1-bit compressed sensing with $f(z) = \\mathrm{sign}(z)$, which is taken as example in the paper) ?\n\n- I believe the paper lacks discussion of the notion of spikiness of the spectrum, defined by the authors in Definition 3. As I was not familiar with this definition, I was a bit surprised that orthogonal matrices are less “spiky” than Gaussian matrices, which seems strange: if I am not mistaken, the Marchenko-Pastur density is more spiky than a delta distribution according to this definition. This is counter-intuitive when considering spiky as the inverse of flatness (however when looking at it as a quantification of “wealth inequality” as briefly mentioned in the paper it makes a bit more sense), and I believe that the paper would benefit from adding a clearer discussion of this point, with examples. \nOn a related note, here spikiness is only related to the asymptotic eigenvalue distribution of the sensing matrix. I find the word choice confusing, as in this context I expected rather spikiness to describe the presence of isolated eigenvalues in the spectrum of the sensing matrix (commonly referred to as “spikes” in the literature), that are not present in the asymptotic eigenvalue distribution but that might be very important in the dynamics of the algorithms, a topic not discussed in the paper.\n\n- Importantly, spikiness in the sense of Definition 3 is not a complete order between spectra: two arbitrary spectra are in general not comparable, and perhaps the authors could discuss further how this point can impact the scope of their results.\n\n**Minor points and questions** \n\n- Could some results be generalized to stronger versions of the noise? By “stronger” I mean either not infinitely small, or more generic type of noises added after the non-linearity, which are standard to take into account in message-passing approaches, and (I believe) more interesting for real applications, e.g. Poisson-noise phase retrieval, compressive sensing, etc... I am thinking in particular to the results of Section 4.2 on the comparisons of the MSE (as perfect recovery might be impossible with noise).\n\n- In hypothesis (A.2) the authors assume that the support of the limiting distribution is an interval $[a,b]$. Is this necessary, or would any compact support work? I don’t see where the fact that it is an interval is needed (but it might be a technicality in the proofs). \n\n- Similarly, in (A.2) both right and left rotation invariance of the sensing matrix are assumed. Is it necessary? For instance, the VAMP approach requires only right-rotation invariance, see [2]. \n\n- In their discussion of the literature on the performance of message-passing approaches, I believe the authors should mention [3], which precisely analyses the state evolution of the Vector Approximate Message Passing approach for rotationally-invariant generalized linear models, from the point of view of statistical physics. \n\n[3] TAKAHASHI, Takashi et KABASHIMA, Yoshiyuki. Macroscopic analysis of vector approximate message passing in a model mismatch setting. In : 2020 IEEE International Symposium on Information Theory (ISIT). IEEE, 2020. p. 1403-1408. \n \n**Typos**\n\n- Line 31: “has certain level” → “has a certain level”\n- Line 101: “we define, enable” → “we define enable”", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors addressed correctly the societal impact of their work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "around 5 hours"}, "extra_text": {}}, {"review_id": "FyJzgPf-QZ1", "reviewer": "Reviewer_Mw3P", "summary": "The authors consider the recovery of unstructured random signals x from measurements of the form y=f(Ax), where f(.) is a component-wise nonlinear function, A is a large and rotationally invariant random matrix, and the dimension of y is strictly larger than the dimension of x.  They assume the use of the GLM-EP recovery algorithm, for which a state-evolution has been previously derived in [21].  (Actually, they use a simplification GLM-EP since they assume an unstructured signal.)  Their primary focus is understanding how the spectrum of A affects reconstruction performance under the stated assumptions.  For this, they define a measure of \"spikiness\" based on the Lorenz partial order.  First, they show that, for some nonlinearities (e.g., the magnitude nonlinearity used in phase retrieval), more spikiness reduces MSE; for other nonlinearities (e.g., 1-bit sensing), less spikiness reduces MSE, and for yet other nonlinearities, there is no monotonic relationship between spikiness and MSE.  Second, they show that, in the noiseless setting, for any nonlinearity, more spikiness reduces the number of measurements needed for perfect recovery.  ", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "The results are interesting, and the paper is clearly written (for the most part).  Although the state-evolution analysis appears to be borrowed entirely from [21], the use of the Lorenz partial order to characterize the recovery performance is novel.\n\nThat said, I think the title, abstract, and introduction significantly over-sell the scope of the results, as described below.  \n1. The paper is not about \"designing optimal sensing matrices\" for signal recovery, but only about analyzing the effect of the spectrum of a random matrix for signal recovery.  There is a large literature on the design of optimal sensing matrices for signal recovery (e.g., for MRI), but that problem is entirely different than the one considered by the authors.  First, no spectrum \"design\" procedure is given in the paper, only an analysis of a given spectrum.  Second, the authors never give an expression for the \"optimal\" spectrum.  Third, the design quantity under consideration (the spectrum) is not a matrix but a vector.  Fourth, the authors only consider a very particular form of \"nonlinear inverse problem,\" which is the GLM.  For all these reasons, the title should be changed to \"Analysis of Sensing Spectra for Signal Recovery under a Generalized Linear Model.\" \n2. The considered recovery problem is non-compressive, in that the number of measurements must be strictly larger than the signal dimension.  Thus, it does not apply to compressed sensing as claimed in the abstract.  The restriction to non-compressive sensing should be clearly stated up front.\n3. Unlike nearly every existing paper on AMP/EP/GLM/CS, the method under review has no ability to leverage signal structure. Yet, the signal is still not \"generic\" as claimed on line 129, because it must be drawn i.i.d. from an absolutely continuous distribution.  So, for example, finite-alphabet signals are not allowed, and even sparse signals are not allowed.  The i.i.d. structural assumption is also restrictive and not \"standard\" as claimed on line 130, because there are now numerous papers on AMP/EP methods with non-separable denoisers designed to recover non-iid signals (e.g., natural images).\n\nThe paper also falls significantly short on practical demonstration.  For example, although the authors prove that MSE can be decreased with an appropriate spectrum, but how much the MSE decreases in practice (e.g., large but finite dimension, large but finite SNR) in the (real) phase-retrieval and 1-bit sensing problems is not clear. \n\nMinor comments:\n1. It would be helpful to label the axes in Figure 1.\n2. It would be helpful to label the subplots in Figure 2 with the corresponding f(.) functions.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no potential negative societal impact of this work. ", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical issues in this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "CAnJ0UqeCyg", "reviewer": "Reviewer_h9Kx", "summary": "This work investigate the problem of recovering a signal vector x from measurements y=f(Ax) where A is a known matrix and f is a scalar function that is applied coordinate-wise.\n\nIn many applications, the practitioner has the freedom of the choice of the matrix A. The present paper seek to understand the influence of the spectrum of A on the estimation performance.\n\nThe authors study this problem in the asymptotic regime where the number of observations as well as the number of entries to estimate (the dimension of x) go to infinity, while their ratio converges to some positive number $\\delta$. They also assume the entries of x to be iid from some prior distribution with unit second moment, and A to be random with SVD $A = U \\Sigma V^T$ where U and V independent and Haar-distributed and that the empirical distribution of the square of the diagonal values of Sigma converges to some distribution $P$.\n\nMost of the paper is devoted to the noiseless case (f is a deterministic function). In this setting, the authors show:\n1) A lower bound delta_p on delta (ratio #observations / # unknown variables) that is needed in order to reconstruct x perfectly whp.\n2) Introduce an Expectation-Propagation algorithm, whose asymptotic behavior can be precisely tracked by a simple scalar recursion. The authors therefore obtain a precise formula for MSE(P,f), the limiting mean square error of the EP-algorithm.\n3) Derive a function G (that only depends on f - and delta I presume, otherwise I guess it would be incompatible with (4) below) such that:\n                - If G is increasing, then spikier distributions P lead to smaller MSE(P,f)\n                - If G is decreasing, then spikier distributions P lead to larger MSE(P,f)\n\n4) Show that spikier distributions P always need a smaller number of measurement in order to achieve perfect reconstruction with the EP algorithm.\n\nA noisy case is also investigated but with less results. Assume now that y=f(Ax + w) where w ~ N(0, sigma Id) is some  Gaussian noise. The authors show in that case that\n1) One need to have delta > delta_p in order to have a bounded noise-sensitivity.\n2) That the MSE of the EP-algorithm verify when sigma -> 0:\n   MSE(sigma) ~ Constant(delta,f) E_P[ 1 / lambda ] sigma^2\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Strength:\nThis paper is relatively original and novel: there is not that many result about the impact of the spectrum of the sensing matrix for such nonlinear inverse problem. The insights from this paper could potentially be very useful in practice.\n\nThe results obtained are also surprising: spikier eigenvalues distribution need less samples in order to achieve perfect recovery, but may lead to larger MSE (for some delta). I may miss something here, because this seems a bit contradictory to me: \nif $MSE_{P_1}(delta, f) \\geq MSE_{P_2}(delta,f)$ for all $\\delta$, then one has $\\delta^p_{P_2} \\leq \\delta^p_{P_1}$. I guess that my issue comes from the fact that the function $G$ in Lemma 6 depends on $\\delta$ and that its monotonicity may change with $\\delta$. If this is correct, I guess it would be important to mention it and specify the value of $\\delta$ chosen in Figure 2. Again, I might be missing something important here.\n\n\nWeaknesses:\nIn my view, the main weakness of this paper is that most of the results only apply to the EP-algorithm. Does the phenomena observed here also apply to other algorithms ? For example, does a spikier spectrum leads to a smoother optimisation landscape and help gradient-based method to converge ?\nAlso, the information - theoretic results of the paper are relatively weak: only a lower bound is obtain and no claim is made about the dependency of the information-theoretic threshold on the eigenvalue distribution.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the author brilliantly address these limitations. No issue here.", "review_text": "", "extra_scores": {"ethical_concerns": "No issue here.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "-dTefgxffDV", "reviewer": "Reviewer_kRWV", "summary": "This paper studies the impact of the sensing matrix spectrum in nonlinear inverse\nproblems. In the first three sections, the authors present the\ninformation theoretical limits to perfect recovery, the expectation propagation\n(EP) like algorithm to solve such nonlinear inverse problems, and its MSE performance\npredicted by the state evolution formalism. However the main focus of this\nresearch is the last section, where a measure of spikiness of the\nsensing matrix spectrum is defined (based on Lorenz partial order), and its\nimpact on EP recovery is investigated, both in term of the MSE performance and\nthe measurement threshold for perfect recovery. This impact is shown to depend\non the type of nonlinearity used in the inverse problem, for instance for the absolute value\na spikier spectrum helps while for the sign function it hurts.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Overall the manuscript is very clearly written, well referenced and the\nmain line of investigation is easy to follow. The results of the first three\nsections, on the EP algorithm, its recovery performance and\ninformation theoretical limits for the GLM are already known in the\nliterature. However these results are clearly meant to lay ground for the final\nfourth section (impact of the sensing matrix spectrum), which is the\nmain goal of this research; they are nicely put together and provide all the\nnecessary information. The most interesting results are Lemma 6\n(which shows how the spectrum spikiness of the spectrum helps or hurts the MSE performance\ndepending on the nonlinearity) and Theorem 3 (that the perfect recovery threshold is\nalways lower for spikier spectrum). As far as I know these results are\noriginal and certainly help in designing better sensing matrices.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main limitation of this work is I think the assumption A1 on the prior,\nwhich if I understand correctly excludes for instance a binary prior or a\nspike-and-slab prior. Unfortunately this means that the perfect\nrecovery for a perceptron with binary weights, or the compressed sensing\napplication, are outside the scope of this study.\nThis limitation seems manifest in the GLM-EP algorithm which do not include a\nprior denoising step. Perhaps this limitation could be better acknowledged by the\nauthors and highligthed in the introduction and discussion of the results.\n\nAlso the results of Lemma 6\n(spikier spectrum leads to higher MSE for functions like sign) and\nTheorem 3 (spikier spectrum always leads to lower perfect recovery threshold\nwhatever the nonlinearity) seem contradictory at first. How can the MSE\ncurve (vs $\\delta$) be above for spikier spectrum\nwhile at the same time have a lower perfect recovery threshold ?\nIf I understand correctly, the contradiction is resolved by Theorem 1,\nas the optimal threshold $\\delta^p_{opt}$ is\ninfinite for the sign activation. Perhaps this point could be clarified in\ndiscussing Theorem 3.\n\nMinor typos/details:\n- lines 194 and 219 \"where $V_r^{-1} = 0$\"may be confusing. Perhaps \"initialised at\n$V_r^{t-1} \\vert_{t=0} = 0$\" would be clearer.\n- line 273 \"GMM-EP-app\"\n- line 290 \"lemme\"", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper the author studies the impact of the choice of the sensing matrix spectrum in nonlinear inverse problems. In the first three sections, the authors present the information theoretical limits to perfect recovery, the expectation propagation (EP) message-passing type algorithm to solve such nonlinear inverse problems, and its MSE performance predicted by the state evolution formalism. The main result is presented in the last section, the impact of the spectrum is investigated, both in term of the MSE performance and the measurement threshold for perfect recovery. This impact is shown to depend on the type of nonlinearity used in the inverse problem.

The consensus among the reviewers was  that the paper was overall well-written, and above the acceptance threshold of NeurIPS 2021. It was judge to  have interest for the community of information theory and statistical-physics approaches to learning. A number of comments and criticisms expressed were expressed during the rebuttal, especially concerning the discussion of the results. For instance, the title was judge misleading, as the emphasis on the spectrum should be clearer.

During the rebuttal the authors seem to have answer most of the critics in a satisfactory way to a majority of reviewers. They also shared additional result from their numerical experiments. We believe these new results should definitely be a part of the paper. The reviewers believe that these experiments and their discussion can really improve a lot the paper, and should not only be include din the supplement, but should also be fairly discussed in their new version of the main paper, as they answer a important criticism.

Overall, there is an agreement on the reviewers side (that is, to all but one) to accept the paper for publication at Neurips. Given the good grading, and the fact that authors successfully answered most criticisms from the referee, I therefore recommend acceptance to Neurips, and that the author proceed to the promised change to the paper.



Decision: Accept (Poster)