Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors provide theoretical guarantees for unlabeled sparse recovery with multiple measurements. They first establish the information-theoretic lower bounds with respect to the number of samples and signal-to-noise ratio (SNR) for the reconstruction of both the permutation and signal matrices. Then, they propose a one-step approach for reconstructing the permutation matrix (and the signal matrix can be easily reconstructed by using the estimated permutation matrix and standard compressed sensing techniques). Some experiments on synthetic data are provided to support the theoretical results. 
strength_and_weaknesses: Strength:

The studied problem is at least of sufficient theoretical interest, and the technical results seem to be novel. Besides, the proposed algorithm is sufficiently simple.

Weaknesses:

1. The theoretical results are not clearly interpreted. For example, the authors mentioned, "For the sample number $n$, the lower bound requires $n$ to be at least of order $O(k \log p)$; while Corollary 1 requires $n$ to be $k(\log n)(\log^2 m n p)$" on page 6. Where does the lower bound come from? I guess it is not derived from Theorem 2 in this paper but from the lower bounds established in standard compressed sensing literature. The authors mentioned on page 2 that the lower bound is established with respect to both the number of samples and SNR. But I cannot see it clearly from the statement of Theorem 2. In addition, it is fairer to compare the lower bound with the upper bound for the number of samples established in Theorem 3 (which has a quadratic dependence on $k$), rather than Corollary 1, which is based on a seemingly restrictive assumption. 

2. It is counter-intuitive to see that no matter how large $k$ is, the thresholding operator used in Eq. (2) that only keeps the element with the largest magnitude in each column works well. I hope that the authors can provide more intuitions/explanations for this, instead of only presenting Figure 1. The authors mentioned that "In the supplementary material, we give a rigorous explanation of this phenomenon" on page 5. But I cannot find where is a rigorous explanation. Please specify it. 

3. The authors claimed in the conclusion that "we considered the unlabeled sparse recovery with multiple measurements for the first time". Although the studied problem is interesting in theory. From the current submission, I cannot see how practically meaningful it is. I hope that the authors can provide some numerical experiments on real data to back up the theory. 
clarity,_quality,_novelty_and_reproducibility: This paper is generally well-written. But there is a lack of rigorous/intuitive interpretations of the main theoretical results. 

The technical results seem to be novel. 

Although this paper only involves synthetic experiments, it is better to upload the code for reproducibility.

Some minor problems:

(a) Page 2: provide a reference for the linear assignment problem (LAP).

(b) Eq. (3): provide clear definition of $\||\mathbf{B}\||_1$.  

Does it mean the sum of entries of $\mathbf{B}$ (in magnitude), or the operator norm $\||\mathbf{B}\||_{1\to 1}$?

(c)  Page 4: the definition of $\mathrm{supp}(\mathbf{B})$ should be given.
summary_of_the_review: Overall, I think that although this submission is interesting in theory, it is weak in both interpreting the main theoretical results and presenting the practical motivation. Therefore, I am inclined to rejection.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers the problem of unlabelled sparse recovery under multiple measurements. More formally, Given $(Y, X)$ such that $Y = \Pi^* X B^*+ W$, where $W \in \mathbb R^{n \times m}$, $W_{i, j} \sim N(0, \sigma^2)$, $X \in \mathbb R^{n \times p}$, $X_{i, j} \sim N(0, 1)$ and each column of $B^* \in \mathbb R^{p \times m}$ is $k$-sparse, the goal is to recover $B^*$ and the unknown permutation matrix $\Pi^*$. 

They show the following: 

1. The sample complexity $n$ should be at least of the order $\Omega(k \log p)$ where $k$ is the sparsity of the signal vectors and $p$ is the ambient dimension. Also, the SNR is lower bounded by $\log det(I + ({B^*}{B^*}^T)/\sigma^2) \geq \log(n) + (m/n) \log(C(p,k))$.  
2. By formulating the correspondence recovery as a linear assignment problem (LAP), they show that the correct permutation matrix
can be obtained when SNR is above certain positive constant.

Their results are the first ones s.t. SNR $\geq \tilde \Omega(1)$ is sufficient to obtain the correct permutation matrix with insufficient samples.  
strength_and_weaknesses: Strengths: 
1. The paper provides new lower bounds on SNR and sample complexity required for recovery for the problem of unlabelled sparse recovery under multiple measurements. 
2. It demonstrates a simple estimator which requires much lower SNR than prior works, in the regime where the number of samples is much smaller than the ambient dimension. 


clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is clearly written. 
Quality: I think this is a good paper and vote to accept it. 
Novelty: The paper has some technical novelty involved in extending and modifying prior proof techniques to the setting that they consider. 
Reproducibility: As far as I could tell, the authors do not provide the code for their experiments. However, there is a detailed description of the method and so they are probably reproducible.  
summary_of_the_review: I think this is a good paper and vote to accept it. The paper seems to provide a concrete improvement over the prior work and the estimator is simple. I have not read the proof in the appendix.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work considers the problem of reconstructing sparse vectors from an underdetermined system of equations when the measurements are commuted.
First, it gives a lower bound on the required number of measurements given a certain SNR.
Then, it analyses an estimator which gives corresponding upper bounds (depending on the number of measurements, signal-noise-ratio, sparsity level, ambient dimension, etc.)
The paper shows that one can reconstruct the sparse signals, even when the noise level is constant and when the number of measurements is quadratic in the sparsity level.
Numerical experiments corroborate the theoretical findings.
strength_and_weaknesses: Strengths:
To the best of my knowledge, the novel results go clearly beyond existing work (constant SNR in the undersampled regime) and should be interesting to people working on these topics.

Weaknesses:
1.The dependence of the number of measurements on the sparsity level is quadratic instead of linear. 
2. Also, I don't really understand Section 4.2. Why does the Theorem follow form inequality (4)? I also don't understand why the inequality on page 8 is true. I am also not sure whether I understand how $()_{\imax}$ is defined.
3. In general, the presentation of the material can be improved; see some of the comments below.

Further comments:
1. page 3: It might be good to explain how the expression $ \log \det \left( I + \frac{B^T B}{\sigma^2}  \right) $ relates to the SNR!
2. page 3: "let $n$ approach infinity". Consider replacing this statement with something more rigorous. Is this an asymptotic or non-asymptotic statement?
3. page 4: It seems to me that $\mathcal{B}_{p,m}$ also depends on $k$. It would be good to make this dependence explicit, for example, by adding $k$ as a subscript.
4. page 5, Theorem 3 and Corollary: Consider replacing "Consider the large-system limit..." by something more rigorous. (It is not clear whether this is an asymptotic or non-asymptotic statement!)
5. page 5, Corollary 1: "where $n$ and $p$ are sufficiently large. Consider replacing this by a more rigorous statement.
6. page 5, Theorem 3: Has $h$ been already properly introduced? If yes, it might be a good idea to recall its definition!
7. page 7: Why does $ \Vert B^{\sharp} \Vert_F $ affect the reconstruction error? I do not understand this statement.
8. page 8, Discussion w.r.t. sparsity number $k$: In contrast to your experiments, Theorem 2 does not say that one needs to increase the SNR when one increases the sparsity level $k$. Please add an explanation why this is not a contradiction.

Typos:
1. page 5 sin(c)e all these works
clarity,_quality,_novelty_and_reproducibility: As mentioned above, the clarity of writing can be improved. The results are novel and are clearly interesting. I was not able to check the proofs in detail.
summary_of_the_review: The paper has novel and interesting results, but I feel that the presentation can be significantly improved. I would recommend (borderline) acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considers the problem of unlabeled sparse recovery under
multiple linear measurements. Statistical theorems are derived for
understanding the proposed estimator.
strength_and_weaknesses: *STRENGTH*:
- The paper derives two solid theorems about permutation recovery:
  - Theorem 2 states that exact permutation recovery is impossible for
  fixed $m$ and $p$, as long as $n$ approaches infinity. The condition
  is very simple and the theorem is very clean.
  - Theorem 3 states that the ground-truth permutation can be recovered
  exactly with high probability by solving the linear assignment
  problem (2), as long as (iv) SNR is larger than some constant,
  (iii) the number of permuted rows is small enough, (ii) the stable
  rank of the ground-truth matrix is larger than some logarithm of the number
  of samples, and (i) we have sufficiently many samples. Once the
  permutation is correctly recovered, the recovery of the ground-truth
  matrix ensues, based on the results in compressed sensing.

- Figure 2 presents an interesting phenomenon where
  the number of samples is actually a double-edged quantity in this
  problem. As Remark 2 discussed, larger $n$ violates the stable rank
  condition (ii). Another perspective might be found in Theorem 2 and
  Theorem 3: With $m$ and $p$ fixed and $n$ approaching infinity, the
  recovery of the permutation becomes impossible. All these suggest
  that, in order for exact recovery, the parameters $m,p,n,h$ might
  have a more sophisticated dependency than the theorems reveal. It
  would be interesting future work to discover such dependency.

- The proof outline (Sec 4.2) is great as it helps the reader to better
  appreciate the technical challenge and thus the contribution of the
  paper.

- I found Table 1 informative. It positions the paper in the
  literature very well. From it, one can also find that the paper
  advances our theoretical understanding of the problem.

*WEAKNESS AND QUESTIONS*:
- In Theorem 2, the supremum is taken over $B_{p,m}$. Why this is
  required? I thought that, since $n$ approaches infinity, this set
  would eventually be the entire set of $p\times m$ matrices.
  Furthermore, should it be stated in Theorem 2 that the ground-truth
  matrix is given as in Theorem 1? Or this is actually not needed for
  the sparse case?
- Personally, I think that, if possible, it would be greater if an
  explanation is given regarding the phenomenon discussed in Remark 1
  and Figure 1. I guess the authors have an answer as to keeping more
  entries might break down the proof. This discussion is important as
  the situation is very different from what is commonly known.
- Sec 4.3 looks a little bit mysterious to me. It seems not very
  rigorous to claim that the proposed estimator is computationally
  optimal. For example, despite being incorrect, the estimator that
  returns an identity permutation and a zero matrix is computationally
  optimal, as it does not require any computation, let alone matrix
  multiplication which is needed by the proposed method. The
  point is, to make such a claim, one needs to prove that (informally
  speaking) there is no estimator that takes fewer operations
  (constrained to its correctness).
- Why is the paper titled *one-step estimator*? The proposed algorithm takes
  two steps, first recovering the permutation and then the sparse matrix.

*MINOR COMMENTS*:
- Typos or grammar problems at:
  - the first line of page 5 (sine -> since)
  - footnote 4 (extend -> extent)
  - the line below Equation 5 (accomplish -> accomplished)
  - the last line of page 7 (is -> are)

- There seems to be some citation issue at the transition of page 4
  and page 5. Please fix it.

- In the abstract, it is claimed that the case of the sparse unknown
  matrix in the *insufficient samples regime* is considered for the
  first time. This might be an overclaim. See for example
  - [1] Compressed sensing with unknown sensor permutation (ICASSP
    2014). There, the *insufficient samples regime* is studied
    computationally (Sec 3).
  - [2] Sparse recovery with shuffled labels: statistical limits and
    practical estimators. There, the *insufficient samples regime* is
    studied theoretically and computationally (as the paper noted).
  - [3] Homomorphic sensing: sparsity and noise (ICML 2021). There, the
    *insufficient samples regime* is studied theoretically and
    computationally (Sec 3).


clarity,_quality,_novelty_and_reproducibility: The paper is written clearly, while there are a few typos as mentioned above.

To the best of my knowledge, the result is novel, despite the fact that it is built upon the analysis framework of several prior works.
summary_of_the_review: The paper provides some solid theoretical results, and reports and explains some intriguing phenomena for the problem of unlabeled permutation recovery. While I have a few questions and comments, they are somewhat minor and can be easily addressed. In summary, I think this is an interesting paper and I vote for accept. (I did not check the proof in the appendix.)
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: We carefully discussed this paper and we think the improvement from n at least quadratic in k to n at least linear in k is interesting, but ultimately decided not to base our decision on this as it seemed like a substantial change from the submitted version and potentially unfair to allow for this extra result late in the process. The fact that the stable rank has to be at least k^2 was also quite worrisome, as it required the ground-truth matrix to be extremely sparse and of limited use in practice. We think the paper would benefit from a serious revision.  
justification_for_why_not_higher_score: see above
Decision: Reject