Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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). 

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. 

I would like to raise two issues of the paper and am curious about the answers:
- 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. 
- 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).


More comments:

- 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.

- 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.

- 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.

-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.

-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.

- How does the information dimension bound compares with the recovery guarantee for Generalized lasso in Plan-Vershynin paper?
https://arxiv.org/abs/1502.04071
In 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.

limitations_and_societal_impact: None
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

- The wording and the organization need improvement.

- 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.

- Abbreviations (e.g., MMSE and AWGN) should be defined at the first time that they are used.

- The statement at line 109-110 is repeated multiple times within the paper. I recommend to emphasize only once or twice.

- For better clarity, a brief notation explanation is recommended (e.g., capital letters stands for ..., bold letters stands for ...)

- Recommend to show Section 3.1 as an "Algorithm".

- Line 262, There are typos (e.g., "is is ..").
limitations_and_societal_impact: Limitations are breifly discussed in the conclusion. However, no societal impact is provided.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the impact 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) like algorithm to solve such nonlinear inverse problems, and its MSE performance
predicted by the state evolution formalism. However the main focus of this
research is the last section, where a measure of spikiness of the
sensing matrix spectrum is defined (based on Lorenz partial order), and its
impact on EP recovery 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, for instance for the absolute value
a spikier spectrum helps while for the sign function it hurts.
main_review: Overall the manuscript is very clearly written, well referenced and the
main line of investigation is easy to follow. The results of the first three
sections, on the EP algorithm, its recovery performance and
information theoretical limits for the GLM are already known in the
literature. However these results are clearly meant to lay ground for the final
fourth section (impact of the sensing matrix spectrum), which is the
main goal of this research; they are nicely put together and provide all the
necessary information. The most interesting results are Lemma 6
(which shows how the spectrum spikiness of the spectrum helps or hurts the MSE performance
depending on the nonlinearity) and Theorem 3 (that the perfect recovery threshold is
always lower for spikier spectrum). As far as I know these results are
original and certainly help in designing better sensing matrices.
limitations_and_societal_impact: The main limitation of this work is I think the assumption A1 on the prior,
which if I understand correctly excludes for instance a binary prior or a
spike-and-slab prior. Unfortunately this means that the perfect
recovery for a perceptron with binary weights, or the compressed sensing
application, are outside the scope of this study.
This limitation seems manifest in the GLM-EP algorithm which do not include a
prior denoising step. Perhaps this limitation could be better acknowledged by the
authors and highligthed in the introduction and discussion of the results.

Also the results of Lemma 6
(spikier spectrum leads to higher MSE for functions like sign) and
Theorem 3 (spikier spectrum always leads to lower perfect recovery threshold
whatever the nonlinearity) seem contradictory at first. How can the MSE
curve (vs $\delta$) be above for spikier spectrum
while at the same time have a lower perfect recovery threshold ?
If I understand correctly, the contradiction is resolved by Theorem 1,
as the optimal threshold $\delta^p_{opt}$ is
infinite for the sign activation. Perhaps this point could be clarified in
discussing Theorem 3.

Minor typos/details:
- lines 194 and 219 "where $V_r^{-1} = 0$"may be confusing. Perhaps "initialised at
$V_r^{t-1} \vert_{t=0} = 0$" would be clearer.
- line 273 "GMM-EP-app"
- line 290 "lemme"
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.  
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.

That said, I think the title, abstract, and introduction significantly over-sell the scope of the results, as described below.  
1. 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." 
2. 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.
3. 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).

The 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. 

Minor comments:
1. It would be helpful to label the axes in Figure 1.
2. It would be helpful to label the subplots in Figure 2 with the corresponding f(.) functions.


limitations_and_societal_impact: There is no potential negative societal impact of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

In 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.

The 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$.

Most of the paper is devoted to the noiseless case (f is a deterministic function). In this setting, the authors show:
1) A lower bound delta_p on delta (ratio #observations / # unknown variables) that is needed in order to reconstruct x perfectly whp.
2) 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.
3) 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:
                - If G is increasing, then spikier distributions P lead to smaller MSE(P,f)
                - If G is decreasing, then spikier distributions P lead to larger MSE(P,f)

4) Show that spikier distributions P always need a smaller number of measurement in order to achieve perfect reconstruction with the EP algorithm.

A 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
1) One need to have delta > delta_p in order to have a bounded noise-sensitivity.
2) That the MSE of the EP-algorithm verify when sigma -> 0:
   MSE(sigma) ~ Constant(delta,f) E_P[ 1 / lambda ] sigma^2

main_review: Strength:
This 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.

The 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: 
if $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.


Weaknesses:
In 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 ?
Also, 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.
limitations_and_societal_impact: Yes, the author brilliantly address these limitations. No issue here.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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$. 

Note that I could not check the calculations and proofs given in the supplementary material.

**I edited this review to modify my score, according to the comments below**
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.

Overall, 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. 

**Strengths of the paper**

- As I mentioned, the writing of the paper is good. Previous literature is cited quite thoroughly, with some minor misses, see below.

- 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).

- 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]).

[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. 

- 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.

**Main concerns and remarks**

- 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.

[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. 

- 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) ?

- 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. 
On 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.

- 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.

**Minor points and questions** 

- 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).

- 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). 

- 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]. 

- 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. 

[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. 
 
**Typos**

- Line 31: “has certain level” → “has a certain level”
- Line 101: “we define, enable” → “we define enable”
limitations_and_societal_impact: Yes, the authors addressed correctly the societal impact of their work.
review_title: null

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)