One-Step Estimator for Permuted Sparse Recovery
Authors: Hang Zhang
Ping Li
Venue: Submitted to ICLR 2023 (2023)

Abstract: This paper considers the unlabeled sparse recovery under multiple measurements, i.e., ${\mathbf{Y}} = {\mathbf{\Pi}}^{\natural}{\mathbf{X}} {\mathbf{B}}^{\natural} + {\mathbf{W}}$, where ${\mathbf{Y}} \in \mathbb{R}^{n\times m}, {\mathbf{\Pi}}^{\natural}\in \mathbb{R}^{n\times n}, {\mathbf{X}} \in \mathbb{R}^{n\times p}, {\mathbf{B}}^{\natural}\in \mathbb{R}^{p\times m}, {\mathbf{W}}\in \mathbb{R}^{n\times m}$ represents the observations, missing (or incomplete) correspondence information, sensing matrix, sparse signals, and additive sensing noise, respectively. Different from the previous works on multiple measurements ($m > 1$) which all focus on the sufficient samples regime, namely, $n > p$, we consider a sparse matrix $\mathbf{B}^{\natural}$ and investigate the insufficient samples regime (i.e., $n \ll p$) for the first time. To begin with, we establish the lower bound on the sample number and \emph{signal-to-noise ratio} (${\mathsf{SNR}}$) for the correct permutation recovery. Moreover, we present a simple yet effective estimator. Under mild conditions, we show that our estimator can restore the correct correspondence information with high probability.  Numerical experiments are presented to corroborate our theoretical claims.

Under review as a conference paper at ICLR 2023
ONE-STEP ESTIMATOR FOR PERMUTED SPARSE RECOVERY
Anonymous authors Paper under double-blind review
ABSTRACT
This paper considers the unlabeled sparse recovery under multiple measurements, i.e., IIXB + W, where Y E TR If E RR X E RRUX,, B e IR W _axm represents the observations, missing (or incomplete) corre- spondence information, sensing matrix, sparse signals, and additive sensing noise, respectively. Different from the previous works on multiple measurements (m > 1) which all focus on the sufficient samples regime, namely, n > p. we consider a sparse matrix B and investigate the insufficient samples regime (i.e., n < p) for the first time. To begin with, we establish the lower bound on the sample number and signal-to-non -o-soe ratio (SNR) for the correct permutation recovery. Moreover, we present simple yet effective estimator. Under mild conditions, we show that our estimator can restore the correct correspondence information with high probability. Numerical experiments are presented to corroborate our theoretical claims.
INTRODUCTION
In recent years, linear regression with permuted correspondence has received increasing attention due to its wide applications in the field of machine learning, signal processing, and statistics. Among all these applications,
most prominent examples are (i) linkage record, which merges two datasets pertaining to the same objects into one comprehensive dataset; and (ii) data de-anonymization, which infers the hidden labels of private data with public datasets. Apart from these two applications, other applications include correspondence estimation between pose and estimation in graphics; time- domain sampling in the presence of clock jitter; nulti-target tracking: unsupervised data alignment, etc (Pananjady et al., 2018; Slawski & Ben- David, 2019; Slawski et al., 2020; Zhang et al., 2018).
In this paper, we consider the canonical model, i.e., a linear sensing relation with permuted labels:
Y = II + W.
where Y E BR is the sensing result, IT; E Raxx is an unknown permutation matrix, X E Bnxp the design (sensing) matrix, B E RR represents the sparse signals of interests, and W E R denotes the additive noise. Assuming the signal Ba is sparse signal, to put more specifically, each column of B is k-sparse, we would like to (i) study the statistical limits of the permutation recovery under this scenario, e.g., the minimum sample number n and hignal-to-noist ratio (SNR); and (ii) propose a practical estimator that can efficiently recover the permutation once the minimum requirements are met. To begin with, we briefly review the previous works.
The study of permuted linear regression has a long history that can at least date back to DeGroot & Goel (1976; 1980): Goel (1975); Bai & Hsing (2005). Recent interests on this area start from Unnikrishnan et al. (2015). Focusing on the noiseless case W = 0 with single measurement (m 1). Unnikrishman et al. (2015) establish the necessary condition n 2 2p for the permutation recovery if Bà is an arbitrary vector residing within the linear space R". Later, Pananjady et al. (2018) extend the analysis to the noisy scenario. They showed the minimum SNR should be at least the order of (2n"). where e > 0 is some positive constant. Numerical experiments suggest c is within the region [4, 5]. Other works such as Hsu et al. (2017); Abid et al. (2017); Slawski & Ben-David (2019); Tsakiris et al. (2020); Haghighatshoar & Caire (2018) also focus on this regime and obtain the same answer. In Emiya et al. (2014), the setting with a sparse signal B is first studied. However, only empirical investigation is conducted without rigorous theoretical analysis. In the first work with theoretical analysis (Zhang & Li. 2021), both the statistical limits and practical estimators with almost optimal performance presented for the permutation recovery. Peng et al. (2021) studies the
Related Works.

---

Under review as a conference paper at ICLR 2023
problem from the viewpoint of 'aleebraic geometry. All existing works suggest that SNR 2((n)) is inevitable for the permutation reconstruction if only one measurement is conducted, namely, m 1.
On the other hand, numerous works suggest multiple measurements. i.c., m 1, can greatly reduce the SNR requirement, even to some positive constant. This line of research starts from Zhang et al. (2022), where the information theoretic lower bounds and the maximum likelihood (ML) estimator are investigated. Later, Zhang & Li (2020) study this problem from the viewpoint of non-convex optimization and propose an optimal estimator for the permutation recovery. Independently, Slawski et al. (2020) investigate this problem from the viewpoint of denoising. Putting parsimonious con- straints on the number of permuted rows, they view (I - I as sparse outliers and design the permutation recovery algorithm accordingly. These works focus on the sufficient samples regime, namely, 2(()). In this paper, we focus on the insufficient samples regime. Assuming B to be sparse, we would like to show the correct permutation can be obtained with n < p and SNR O(1).
Our contributions are summarized as follows
We study the lower bounds w.r.t the number n and signal-to-noise ratio (SNR) for the correct reconstruction of both the permutation matrix IT and the signal B Assuming each column B (1 5 é < m) is k-sparse, we show that the sample number n should be at least of the order Q2k p) meanwhile the SNR should satisfy log det + B BTTB/ > log rt + log (2)
We propose a one-step estimator for the correspondence recovery, which consists of two sub-parts: one for II2 and another for B By formulating the correspondence recovery as linear assignment problem (LAP) (Kuhn, 1955; Bertsekas & Castañón, 1992; Burkard et al., 2012), the correct permutation matrix can be obtained when SNR is above certain positive constant.
On top of the above contributions, we would like to briefly mention our proof strategy, which based on a tailored version of the leave-one-out technique. Compared with the previous works that adopt the leave-out-out technique (Chen et al., 2020; Sur et al., 2019; El Karoui, 2013; 2018; Cai et al., 2021), I), our construction method bas the following characteristics
Our construction method is adaptive, which replaces multiple rows ranging from 2 to 4 depending on each permuted row. Meanwhile, previous works such as Chen et al. (2020); Sur et al. (2019); El Karoui (2013; 2018); Cai et al. (2021) replace a fixed number of rows (or columns).
We not only leave out the rows, but also modify the thresholding operator operated on the perturbed samples B(...) from thres(-) to (.)imax (its definition is deferred to Subsection 4.2). This step is essential in controlling the approximation error, since otherwise the non-zero elements matrices B (xx X YT) and B() may not share the same position and the approximation error can be considerably large. A thorough understanding is deferred the proof of Theorem 3.
Denote e, c G, as some positive constants, whose values are not necessarily the same even for those with the same notations. We denote a S b if there exists some positive constants co > such that a < cgb. Similarly, we define a 2 b provided a 2 ogb for some positive constant cg- We write x when
Notations.
and Z b hold simultancously.
For an arbitrary matrix M, we denote M., as its ith row, M., as its ith column, and M.; as its (tth element. Its Frobenius norm is defined as [M] while the operator norm is denoted [M] OP whose definitions can be found in Section 2.3 of Golub & Loan (2013). In addition, we define its stable rank as srank(-) & 1 (Section 2.1.15 in Tropp (2015)) and its support set supp(-) ) as ((i,)) : (c, * 0}. The inner product between matrices is denoted { while the inner product between vectors is denoted as (.
We define the set of all possible permutation matrices as P... which is defined as (II E {0, 10 1]mxm x
Hy = 1, クi I1; = 1}. Associate with each permutation matrix II, we define the operator (() that transforms index i to (i) under II. The Hamming distance dh [II, II. between two permutation matrices II, and II, is defined as dh (II, Hl) Σn= (m (1) o (i)).. The SNR
is defined as | 2 /mmm (2).
2

---

Under review as a conference paper at ICLR 2023
2 PROBLEM FORMULATION
We start this section with formal restatement of the considered problem reading as
Y XB + W,
where II E Pn denotes the (fixed but unknown) permutation matrix, X Ruxp is the sensing (design) matrix with its entries being i..dd standard normal random variables, i.e., Xij ~ N(O, 1), B E Rexm is a fixed sparse matrix awaiting to be reconstructed (corresponding to the sparse signal), and W E Raxm denote the noise with each entry Wij Lid N(0, Here we put the separate sparse constraints on each column of B namely, |B I A: (1 S S m)) In addition, we denote / as the number of permuted rows, or equivalently, the Hamming distance between the identify matrix and the permutation matrix IT, namely, _ II+)
Our goal is to reconstruct both the permutation matrix IT and sparse signal B from (1). Note that we do not assume that different columns of II share the same support set. Actually, we prefer each column be with a different support set, since otherwise rank(B*) will be bounded by k and will bring extra difficulties to the permutation recovery. A detailed explanation is deferred to Section 4.
Before proceeding, we briefly review the prior art. In Unnikrishnan et al. (2015), where B can reside within the entire linear space R", it is proved that n 2 2p is required for the correct permutation recovery. As a result, subsequent works such as Pananjady et al. (2018); Zhang al. (2022); Slawski & Ben-Davvid (2019); Slawski et al. (2020): Zhang & 1.i (2020) all focus on the sufficient sample regime, i.e., n st(p). Only until Zhang & Li (2021), the insufficient sample regime, i.e., n = o(p). receives its first theoretical investigation. Similar to our setting, they put sparsity assumption on B however focus on the single measurement scenario, namely, m 1. They show that the minimum SNR for correct (II², supp ()²) to be Q(n D(n///mm())) "=f/)) In the following context, we will show that the minimum SNR can be significantly reduced, to put more specifically, some positive constant provided multiple measurements are made (m >> 1).
INFORMATION THEORETIC LOWER BOUNDS
This section establishes the information theoretic lower bounds for the correct permutation recovery. Our goal is to ensure both II" and B can be reliably reconstructed. We investigate this problem from two perspectives: (2) the sample number n and (ti) the minimum SNR.
3.1 THE MINIMUM SAMPLE NUMBER 72
We obtain the minimum sample number such that sparse signal B can be reliably recovered with high probability. Here we consider the oracle situation where II2 is given prior. As each column in B does not necessarily share the same support set, we need to iteratively reconstruct each column B² .. a A k-sparse signal, from the corresponding readings Y.,e (1 < f < m). With the classical result in Donoho (2006); Candes et al. (2006); Candès et al. (2006), we obtain the lower bound on n, namely, n λ k loog p. Naturally, we can expect this bound applies to the non-oracle situation as well, since reliable estimation of B is hopeless provided it is out of reach in the oracle situation.
3.2 THE MINIMUM SNR
Then we turn to the minimum SNR requirement for the correct permutation recovery. To begin with, we restate the prior art in Zhang et al. (2022).
Theorem (Theorem in Zhang et al. (2022)). Consider the oracle case where Ba is given a prior.
Then there exists an integer no such that for an arbitrary estimator II, we have
inf sup Px.w A + à meE.
IT
1 2'
provided that (i) lot B BB/2) < log and (ii) nog-
"Exerimmnnts suggest that may relax this assumption to that X., are i.i.d. sub-Gaussian random variables.
3

---

Under review as a conference paper at ICLR 2023
One drawback of this bound is the missing role of the sparsity number k. This is because Theorem 1 assumes B to be perfectly known while sparsity number only kicks in when B needs to be reconstructed. To handle such issue, take sBpp(B into account well. Then have
Theorem 2. There exists an integer no 2 0 such that for arbitrary estimators II and B, we have
1
inf f1
sup NEP B....p.m.
wIT, sup) + (II, su)) 2
hold for all n no, where Pn denotes the set of all permutation matrices, Bn.p.m. is defined
as the set reading as {B E IR log det(1 + B B/o²) < log n + mn log (?) and supp(-) & (i.j)) (uy + 0} denotes the support set.
This theorem suggests that for all possible estimators reconstruct II and (B), there exists least one pair (II, B) II E Pn, B E Bn.p.m. such that the reconstruction error rate will be at least 1/2. Hence, a reliable correspondence reconstruction requires B (a fixed but unknown matrix) to satisfy log det (I+ B B' /²)² > log n + m log (t)/n.
We leave the rigorous proof the supplementary material and only give intuitive interpretation, which comes from the coding theory. First, we assume each entry in B to be binary, i.e., Biy E [0, < p, 1 < m.) Thus, the information of B is fully incorporated in supp(B). In the following, we will use (B) and B interchangeably. as they are identical.
Afterwards, view the sensing relation in (1) the following transmission process: (i) pair (II, B) is encoded into the codeword IIXB; (ii) IIXB passes through a Gaussian additive channel; and (iii) one observes Y, from which one would like obtain (II, B).
Using the terminology from coding theory, we can compute the corresponding code rate and channel log log log (E) and log de T B/o²), respectively. Due to the Shannon theorem, we can expect non-negligible decoding error if the coding rate is greater than the channel capacity, which
capacity as
m log (E) the formula in Theorem 2.
leads to log det B B/o2) < log nl
Remark 1. Note that the minimum SNR requirements can be derived from Theorem 2 as log det B B/O²)) closely related to SNR. When B is of rank-one, we have log det + B BB/²)) be log(1 + m SNR). When B of full-rank and with identical singular values, we have log del be rank(B) log(1 + SNR).
B/o²)
Having obtained the information theoretic lower bounds, we will propose a computationally efficient estimator which matches the lower bounds thereof a good extent.
ESTIMATOR DESIGN
This section proposes computationally efficient estimator for the permutation recovery. Denote thres(-) as the operator which only keeps the element with the largest magnitude in each column, we reconstruct I with the linear assignment problem (LAP) (Kuhn, 1955; Bertsekas & Castañón, 1992; Burkard et al., 2012) reading as
I argmax ITEP, III, Y thres(X T xx)),
Once the permutation matrix oo is obtained, we can transform (1) to the previous setting and iteratively recover each k-sparse column B. A formal statement the algorithm Algorithm 1. Here we use Lasso estimator to reconstruct the signal B3, which can be replaced with other estimators, say Dantzig estimator, etc.
Design intuition. The design of (2) shares similar idea of the estimator in Zhang & Li (2020): we would like to approximate the direction B by the product X Y. However, due to insufficient samples, product X Y is poorly aligned with B", equivalently, large errors in approximating B with X Y and weak correlation (B², Y). To reduce the approximation errors, we apply thres(.) and set certain entries in X Y
4

---

Under review as a conference paper at ICLR 2023
Algorithm 1: One-step estimator.
Input: observation and sensing matrix X.
Output: pair (IToR, B which is written
IT argmaxneP., (II. Y thres (X Y) x xx),
B argmin (2n) O Y XB Am B||
where thres(-) applies to each column and thresholds all entries zero except the one with the largest magnitude, P. denotes the set of all possible permutation matrices, |1-111 - Ex 10yl
denotes the absolute sum of all entries, and Xn is some regularizer coefficient.
Note that we always keep one nonzero entry in the operation thres(-) regardless of the sparsity number k. This operation is different from almost all the pre- vious works, which ranges from Blumensath Davies (2009); Foucart (201 1) in the literature of compressive sensing to Jain et al. (2013); Yuan et al. (2014); et al. (2016) in the literature of optimization, since all these works suggest keeping at least (k) non-zero elements for s-sparse signal.
Fout-seto elemanls
gnot- neno elemnnnts
0.8
# moo--acro
Heeovery Prob.
#rve- elennntt
0.6
0 0.5
More surprisingly, our numerical experiments suggest keeping more non-zero elements are detrimental the permutation recovery. An illustration is put in Figure 1, from which we observe the SNR required for correct correspondence recovery increases with the number of non-zero elements kept X YYY
1.5
2.5
3
3.5
4.5
Figure 1: Keeping more non-zero elements
in Y deteriorates permutation recov- ery.
500. h 25, srank (B²) = 100. # #non-zero elements refers to the number of non-zero elements kept in each column of Y
100,
We apply the operator thres(-) to Y to better approximate B 's direction, or equivalently. increase the correlation (thres Y), B²). Due the insufficient sample number n. X Y is poorly aligned with B Thus, keeping more non-zero elements thres(-) leads a potential decrease of (thres(X Y). B*) and less satisfactory performance.
Remark 2.
4.1
MAIN RESULTS
This subsection formally presents main results.
4.1.1 RESULTS RECOVERING IT;
First, we study the correspondence recovery. The formal statement is given as Theorem 3. Suppose that 2 no and p Po- where no, Po 0 are some positive constants. Provided that (i) >> k:log n) (log² mmp)) (ti) sBank(B²) > k2 log 2(1+60) n, (iii) h I co n, and (iv) SNR 2 0₁, we have (II II'} with probability at least 1 C2 n n where Eo > is an arbitrary positive constant and h a dH. IT²) denotes the number of permuted rows.
If assume that for each column its maximum entry's energy is at least constant proportion of the total energy, i.e., inf, max, // fla 2 e (1 S sis S p. S S we can further relax the requirements stable rank sBank(B*). Here
0 is an arbitrarily small positive constant.
Discussion. Comparison with previous work is put in Table 1, from which we conclude that our work gives the first affirmative answer such that SNR > ?(() is sufficient to obtain the correct permutation matrix with insufficient samples, i.e., n < p.
In addition, would like to compare it with the lower bound. To begin with, discuss the SNR requirement, which the top priority of our analysis. From Theorem 3, we can see that the correct permutation matrix can be obtained provided that SNR is above some positive constant; meanwhile
5

---

Under review as a conference paper at ICLR 2023
Table I: Comparison with previous works. All results presented in their best orders, which only hold true in certain regimes, Here SNR Mmin and Amax denotes the minimum SNR required for correct permutation recovery, the minimum required sample number and maximum allowed number of permuted rows, respectively. Moreover, the logarithmic term is omitted Ω(-).
SNRmin (2)
nuk/p (2)
hus/n (5)
m = 1 m >
m
m >
m7
m >
(Pananjady et al., 2018)
D(x²)
2(1)
22(1)
(Slawski Ben-David. 2019)
12(1))
((1))
(2(1og n1)
(Zhang el al., 2022)
(2(1)
90(1)
5 (log r(B))
(Slawski et al., 2020)
9((1)
9((p)
Ailog n)
(Zhang Li, 2020)
D(n")
(2(1)
Q(1)
((vP)
((1))
2(11
(Zhang & Li, 2021)
Q(19))
o(1)
((1))
Our Estimator
2211)
o(1)
S1(1)
Theorem 2 requires SNR > O. This means our SNR requirement has at most gap of some positive constant with the statistical lower bound.
For the sample number the lower bound requires to be at least of order S2(k log p): while Theorem 3 requires π to be [(k(log n)) (log" mmp)), which means the lower bound is matched up to some multiplicative logarithmic terms. We conjecture that the required sample number n in Theorem can be further optimized, i.e., the logarithmic terms, with more delicate analysis.
Moreover, our estimator allows the maximum number of permuted rows to be linearly proportional to the sample number, i.c., Amax X n, which is order-optimal.
0.8
Remark 3. Compared with Zhang & Li (2020) which only requires Srank(B²) to be above certain positive constant, our estimator requires a larger stable rank (B²) Although we cannot claim that srank(Bb) must lower bounded by some non-decreasing func- have numerical evidence such that
Recovery Prob.
0.6
0.4
0.2
00
tions of log stank(B') may have to increase with sample number n. in other words, its lower bound may not be reduced be some positive constant. Fixing the parameters p, h. and srank(B (B study the impact of sample number on the permutation recovery and put the results in Fig- ure We observe that a larger has negative impact on the permutation reconstruction once exceeds certain threshold. One possible reason that the stable rank srank(B)) is fixed a constant and violates the requirement srank (B²) >>> log"
srank:113)
(33))
50
850
1650
2450
3250
4050
Figure Illustration the dual role of sample number n. We consider the noise- less case (infinite SNR); and set p 200 (signal length), k = 5 (sparsity number), and 25 (number of permuted rows).
4.1.2 RESULTS IN RECOVERING B
Once the ground-truth IIA is obtained, we restore (1) the traditional model in compressive ing/sparse recovery (Candès et al., 2006; Candes et al., 2006; Donoho, 2006; Wainwright, 2019). One corollary is given as follows.
Corollary 1. Suppose that n 2 no and 2 po, where no. > 0 are some positive constants. Provided that (1) >> k(llog ()log" 'mmp), (fi) srank(B*) > 1.2 log 2(1+e), (iti) h Co n, and (iv) SNR 2 C1- Setting X, in (3) as 020 Vlog we conclude
mk log p
B B
holds with probability exceeding 1 -cgn csp

---

Under review as a conference paper at ICLR 2023
Its proof is simple combination of Theorem and the previous results in Candès et al. (2006); Candes et al. (2006); Donoho (2006); Wainwright (2019). However, we observe a new phenomenon:
the reconstruction error Buu Ba F is affected by the signal energy B || top of the sensing noise o². Moreover, we should mention that the above difference will still exist even when we replace (3) with other estimators, say, Dantzig estimator.
4.2 PROOF OUTLINE
Due to the space limit, we only give a sketch of our proof ideas and leave the technical details to the supplementary material. Denote B = (n -)-1X" YY our goal is to show
(Y thres (B)) (Y, IIX (Br)s A + II
(4)
holds with high probability under the settings in Theorem 3.
Same as Zhang & Li (2020), our analysis faces the difficulties brought by (i) combinatorial nature of the problem and (it) high-order moments of sub-Gaussiaa random variables. On top of these challenges, we are subject to insufficient samples, i.e., n < p. These issues are tackled by a combination of relaxation and a tailored leave-one-out analysis, which can be roughly divided into the following three stages.
Stage I. We consider the sufficient condition of (4), which reads
YY three (B) T (0))) 2 (Y.,, thressB)) T X,.),, A +
Re-arranging the terms, we obtain an equivalent form reading as
( ( thres BB X ( 2 (B* Xxt thres (B) Xx,))
(W 5.s TBT (X,)))) - x,,)).
(5)
Informally speaking, we first assume that thres (B) almost parallel to B²; and the dependence of thres(()) B) on (1) Xjz is negligible. Then, we can approximate (5)'s left-hand side as | and its right-hand side as a sum of 2 Ba BB and /2z || [ up to some normalization constant, Lid iid N(O,Ipxe and z ~ Im0.I are Gaussian random vectors. Easily, we can
Il
where 21, Z2 ~
see that (5) holds with high probability provided the SNR sufficiently large. In the following two stages, we will verify the above two assumptions, that is, (i) <(thres(B), Bt) is small and (ii) the dependence between (Br and (1).)) X3: is negligible.
Stage We would like to lower-bound the inner product (B*, thr)s(B)). Denote as the corre- sponding column in B, we can express (B4, thres(B)) as heess (B9, thres( From
the definition of thres(-), we notice that thres( only has one non-zero entry. W.l.o.g. we assume its index is one and hence have
(B), (Br) = 37,, = + - 34) 2 (B))² - max |B ||B3 -l
We (i) upper-bound max; | and ||,30 - -Blooc: and (ii) lower-bound | Part (1) is quite standard and part (ii) lies in analyzing the event |3,11 2 max, |رر|| which is due the definition of thres(-).
Stage HI. We would like to show the dependence between thres (B) and rows X x and X,,; is negligible. This is accomplished by a tailored leave-one-out analysis. For each row indices pair (i),,, we construct a perturbed matrix (())) by replacing the rows X X Xj, with their i..dd. substitutes. Easily, we can verify that (() independent from the rows ( Xj, as the latter are not involved in (=(()))) Meanwhile, we have ((,)) exhibit similar behavior as B as they share almost identical components. Actually, this is the basic idea of leave-one-out technique (Chen et al., 2020; Sur et al., 2019; El Karoui, 2013; 2018; Cai et al., 2021). Compared with these works, our construction method has the following characteristies
This corollary has one requirement SNR, which is affected by both B || and o² In addition, we may have n Bill| be directly linked to || B || as wrong correspondence can be obtained with low SNR.
7

---

Under review as a conference paper at ICLR 2023
The number of replaced rows in method varies for different pair of row indices. Meanwhile, the replacement number fixed in the above mentioned works. For a better explanation, we refer the readers to our constructed leave-one-out samples (.) in the appendix.
We modify the operator thres(-) in approximating ( While the previous works usually keep the operator (-res(-) intact, approximate it with the operator (-)imax> which denotes the positions of non-zero elements thres(B). other words, the positions of the non-zero elements we keep in the leave-one-oul samples B are determined by thres B) rather than thres ( In see this step is essential in controlling the approximation errors. Otherwise, the approximation error can be considerably large, since thres B may not share the same support set with thres B ))), let alone their lz differences.
analysis,
The explanation thereof is simplified version of our proof technique. The technical details, which are put in the supplementary material, can be different from the above however follow the same spirit.
Moreover, we want to discuss our algorithm's computational complexity: in the first step for permuta- tion recovery, our estimator only requires one matrix multiplication and thresholding operation on top of the operations in the oracle estimator; the second step for sparse signal recovery, our estimator needs one additional matrix multiplication when compared with the work without permutation.
5 NUMERICAL RESULTS
This section presents the numerical experiments to verify our main theorem, to put more specifically, Theorem 3: we would like to prove the correct permutation can be obtained, i.e., [IT = II with < p and SNR c. We only present the numerical results the synthetic data here and defer those on the real-world data to the supplementary material.
Experiment setting with Gaussian distribution. We let X,, Lid N(O, 1) and pick the sample number n to be {100, 150) and set h = 7/4. We vary the signal length to be (500, 600). Then we set the sparsity number within the region {10, 15, 20). And the stable rank srank (B) is within the range (150, 200, 250]. The corresponding simulation results can be found in Figure 3.
Gaussian
Gaussian
Gaussian
boogooog
0.8
0.8
Recovery Prob.
Recovery Prob.
0.8
Recovery
-10
0.4
krenk
0.4
(B
krakk [8)
-200
sreak BB
200
A (BP) -200
0.2
9 krnkk
-250
0.2
-250
0.2
(unk((B)))) -250
100, p 500,
100,
100, p 500, k
08
0.6
0.8
1.2
1.4
1.6
1.8
2
0.8
1.2
1.6
2
2.4
2.8
3.2
0.8
1.6
2.4
3.2
4.8
6.6
SM
SNR
Gaussian
Gaussian
Gaussian
Recovery Prob.
0.8
Recowery Prob.
Recovery Prob.
0.8
0.6
0.6
amank
maak:
-200
saok(DD)) -200
0.2
mank (B5) -20
0.2
-
wwwnle B3
-50
0.2
stok((D)) -25
150,
p= 600,
10
150, p 600, k=
150, p 600, 20
06
04
0.2
0.4
0.5
0.8
12
1.4
1.6
0.4
0.6
0.8
1.2
1.4
1.6
1.8
0.6
0.8
1.2
1.4 1.6 1.8
22 24
SNR
Figure 3: Simulated recovery rate P(i = I with {100, 150), (500, 600), h E (25,37}.
and X. iid
N(O, 1). with respect to SNR.
Discussion w.n.t "/p. First, confirm theory such that correct permutation can be obtained with insufficient samples, ie., n & p. In addition, we notice that the permutation recovery becomes easy with larger n/p: the first row in Figure is with r/p 0.2 while the second row is with 2/p 0.25.
8

---

Under review as a conference paper at ICLR 2023
We verify the SNR for the correct permutation recovery is smaller in the second row than that for the first row. However, we should stress that this conclusion may not hold provided that srank is not sufficiently large. More details referred to Figure 2.
Discussion w.r.t. sparsity number k. We vary the sparsity number l to be within {10, 15, 20). We conclude large sparsity number & can make the permutation recovery more difficult. For example, consider the case when (n, p, srank = (100, 500, 200). When & = 10, correct permutation requires SNR 2 1.4; when l 15, correct permutation needs SNR 2 2.2; and when 20, correct permutation requires SNR 2 4. The same conclusion holds for other cases well.
Experiment setting with sub-Gaussian distribution. In addition to the Gaussian setting, we also evaluate estimator's performance when X,y being sub- Gaub-Gassiin. Here, pick X;, to be i.i.d. Rademacher random variables such that P(x,j = +1) = 1/2. The corresponding results are put in Figure 4, from which observe similar pattern as that of the Gaussian setting.
Rademacher
Rademacher
Rademacher
Recovery Prob.
Recovery Proh.
Recovery Prois.
0.6
0.8
0.6
0.4
+ [ -150
0.4
sranal (-
1150
0.4
stonk(D)) -150
A Braak( -20
sranae sranin
A
maak( -250
100, p 500, k= 10
100,
500,
k= 15
100, p 500, k 20
04
06-
SNR
S00
SNR
Rademacher
Rademacher
Rademacher
0.8
0.9
0.8
Recovery Prob.
Recovery Prob.
Recovery
0.4
mank(
0.4
srenk
0.4
sBok((B))
(B3)
-00
stenk (3-)
2200
- (BP) -200
0.2
arank/ (3
-250
0.2
-200
0.2
(-onknk( -250
150, p
600,
k
10
150,
600,
150, p
08
0.2
0.4
0.5
0.8
1.2
1.4
0.4
0.6
0.8
1.2
1.4
1.6
1.8
0.6
0.8
1.2
1.4
1.6
1.8
2 22 24
SNR
Figure 4: Simulated recovery rate P(î I with {100, 150). E (500, 600). h E (25,37},
and X; Rademacher, i.e., PXX,j = 1) = P(; = 1) = 1/2, w.r.t. SNR.
Lid
6 CONCLUSION
In this paper, studied the unlabeled sparse recovery with multiple measurements (i.e., 1) for the first time. To begin with, we investigated the lower bounds on the sample number n and the SNR. Furthermore, we proposed simple yet effective estimator, which restores the permutation matrix via a linear assignment problem. We proved that our estimator can obtain the correct correspondence information when SNR is above certain positive constant and required sample number n in linear dependence with sparsity number k. In addition, we discovered multiple phenomena that are seldom encountered before: (i) keeping more non-zen zero elements thres(-) deteriorates permutation recovery; and (di) increasing sample number plays a dual role in reconstructing the permutation. In the course of analyzing our estimator's performance and explaining the above phenomena, we developed tailored version of the leave-one-out technique, which involves an adaptive number of replaced elements and simultaneous modification of the threshold operator. Moreover, we provided numerical experiments to corroborate our claims and showed our estimator can reliably reconstruct the permutation matrix even when the entries Xij are sub- Gaussian random variables.
This result is consistent with Theorem 2 as Br.p.m, covers a broader class of matrices B when & increases from 15 20, which implies larger SNR is required for correct permutation recovery.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Abubakar Abid, Ada Poon, and James Zou. Linear regression with shuffled labels. arXiv preprint 170.01/70 2017.
Zhidong Bai and Tailen Hsing, The broken sample problem. Probab. Theory Relat. Fields, 131(4): 528 528-552, 2005.
Dimitri P. Bertsekas and David A. Castañón. A forward/reverse auction algorithm for asymmetric assignment problems. Comp. Opt. and Appl., 1(3):277-297, 1992.
Thomas Blumensath and Mike E. Davies. Iterative hard thresholding for compressed sensing. Applied and computational harmonic analysis, 27(3):265-274, 2009.
Rainer Burkard, Mauro Dell' Amico, and Silvano Martello. Assignment problems, revised reprint, volume 106. SIAM, 2012.
Changxiao Cai, Gen Li, Yuejie Chi, H Vincent Poor, and Yuxin Chen. Subspace estimation from unbalanced and incomplete data matrices: 82,0 statistical guarantees. The Annals of Statistics, 49 227:944-667, 2021.
Emmanuel J. Candès, Justin K. Romberg, and Terence Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory, 52 (2):489-500) -098999599000 2006.
Emmanuel J Candes, Justin K Romberg, and Terence Tao. Stable signal recovery from incomplete and inaceurate measurements. Communications Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 1077)122771 2006.
Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, and Yuling Yan. Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization. SIAM journal optimization, 30(4):3098-31) -1288, 2020.
Thomas M. Cover and Joy A. Thomas. Elements of information theory. John Wiley & Sons, 2nd edition, 2012.
Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of johnson and lindenstrauss. Random Struct. Algorithms, 22(1):60-65, 2003.
Morris H. DeGroot and Prem K. Goel. The matching problem for multivariate normal data, Sankhya: The Indian Journal of Statistics, Series B (1960-2002), 38(1):14-29, 1976.
Morris H. DeGroot and Prem Goel. Estimation the correlation coefficient from a broken random sample. The Annals of Statistics, 8(2):264-27) 03 1980.
David L. Donoho. Compressed sensing. IEEE Trans. Inf. Theory, 52(4): 2006.
Noureddine El Karoui. Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators: rigorous results. arXiv preprint arXiv:1311.22455.000 2013.
Noureddine Karoui. On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators. Probab. Theory Relat. Fields, 170(1-2): 95-175, 2018.
Valentin Emiya, Antoine Bonnefoy, Laurent Daudet, and Rémi Gribonval. Compressed sensing with unknown sensor permutation. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1040-1044, Florence, Italy, 2014.
Simon Foucart. Hard thresholding pursuit: an algorithm for compressive sensing. SIAM Journal on numerical analysis, 49(6):2533-256)
2011. 2011.
Prem K. Goel. On re-pairing observations in broken random sample. The Annals of Statistics, 3(6): 1369-1369, 11 1975.
10

---

Under review as a conference paper at ICLR 2023
Gene H. Golub and Charles F. Van Loan. Matrix computations. Johns Hopkins University Press Baltimore, 4th edition, 2013.
Saeid Haghighatshoar and Giuseppe Caire. Signal recovery from unlabeled samples. IEEE Trans. Signal Process., (6(5):1242211) 1257, 2018.
Daniel J. Hsu, Kevin Shi, and Xiaorui Sun. Linear regression without correspondence. In Advances in Neural Information Processing Systems (NIPS), pp. 1531-1540, Long Beach, CA, 2017.
Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. In Symposium Theory of Computing Conference (STOC), pp. 665-674, Palo Alto, CA, 2013.
Harold W Kuhn. The Hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97) 97, 1955.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2324 1998.
Xingguo Li, Tuo Zhao, Raman Arora, Han Liu, and Jarvis D. Haupt. Stochastic variance reduced optimization for nonconvex sparse learning. In Proceedings of the 33nd International Conference on Machine Learning (ICML), pp. 917-925, New York City, NY, 2016.
Ashwin Pananjady, Martin J. Wainwright, and Thomas A. Courtade. Linear regression with shuffled data: Statistical and computational limits of permutation recovery. IEEE Trans. Inf. Theory, 64(5): 3286-3300, 2018
Liangzu Peng, Boshi Wang, and Manolis Tsakiris. Homomorphic sensing: Sparsity and noise. In International Conference Machine Learning, pp. 8464 8475. PMLR, 2021.
Martin Slawski and Emanuel Ben-David. Linear regression with sparsely permuted data. Electron. J. Statist., 13(1):1-36, 2019.
Martin Slawski, Emanuel Ben-David, and Ping Li. Two-stage approach to multivariate linear regression with sparsely mismatched data. J. Mach. Learn. Res., 21(204):1-42, 2020.
Pragya Sur, Yuxin Chen, and Emmanuel J Candès. The likelihood ratio test in high-dimensional logistic regression asymptotically a rescaled chi-square. Probab. Theory Relat. Fields, 175((-2): 487-558, 2019.
Joel A. Tropp. An introduction matrix concentration inequalities. Found. Trends Mach. Learn., 8 (1-2):1-230, 2015.
Manolis C. Tsakiris, Liangzu Peng, Aldo Conca, Laurent Kneip, Yuanming Shi, and Hayoung Choi. An gegeberai-geommeriic approach for linear regression without correspondences. IEEE Trans. Inf. Theory, 66(8)55130-5144 2020.
Jayakrishnan Unnikrishnan, Saeid Haghighatshoar, and Martin Vetterli. Unlabeled sensing: Solving linear system with unordered measurements. In Proceedings of the 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 786-793, Monticello, IL, 2015.
Roman Vershynin. High- Digeeniimnsooaal Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
Martin J. Wainwright. Biggh-Dimessooall Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
Xiaotong Yuan, Ping Li, and Tong Zhang. Gradient hard thresholding pursuit for pparsity-constrain optimization. In Proceedings of the 31th International Conference on Machine Learning (ICML), pp. 127-135, Beijing, China, 2014.
Hang Zhang and Ping Li. Optimal estimator for unlabeled linear regression. In Proceedings of the 37th International Conference on Machine Learning (ICML), pp. 11153-11161 1662, Virtual Event, 2020.
11

---

Under review as a conference paper at ICLR 2023
Hang Zhang and Ping Li. Sparse recovery with shuffled labels: Statistical limits and practical estimators. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), pp. 1760-1765, Mclbourne, Australia, 2021.
Hang Zhang, Martin Slawski, and Ping Li. The benefits of diversity: Permutation recovery in unlabeled sensing from multiple measurement vectors. IEEE Trans. Inf. Theory, 68(4):2509-2529, 2022.
Huishuai Zhang, Yuejie Chi, and Yingbin Liang. retrieval with outliers. IEEE Transactions on information Theory, 64(11):7287-7310, 2018.
nonconvex approach for phase
12

---

Under review as a conference paper at ICLR 2023
A PROOF OF THEOREM 2
Proof. The proof technique is a combination of that in Zhang al. (2022) and Zhang & Li (2021).
First we put uniform distribution as the prior of II, i.e., P II smpp |Px1- 1-11 where sup is an arbitrary fixed permutation matrix and Pn denotes the set of all possible permutation matrices. In addition, we introduce distributions for the support set of B. For an arbitrary column B, we assume its support set to be uniformly distributed among (%) possible patterns. Easily, we can verify the relation
sup Px.w supp(()) & (Ii, supp(B))] 2 P......B (II supp(B)) * (II, supp(()))
(6)
Since inf fi,8 can be safely added to the left-hand side of (6), our goal becomes lower-bounding Ex.w.I.B' [TI, supp(B)) & (fI, supp(B)) (B))] Adopting the proof technique used in Theorem 2. 10.1 in Cover & Thomas (2012), we consider the entropy H(II, supp(B)). which can be computed as
H(TI, supp B))
H(TT) + H(supp
log n! + m log
(7)
1:
where in ! we use the independent among and supp (B), and @ we use the fact [Pnl = n! and [B = (P) k
Meanwhile, we have the relation
IIII (B)
IIII (B) X)
H(II, (B) B) X, I1 supp(B)) B)) + supp(B) îI, supp(B) x).
(8)
where ② is due the independence between X and II, B; and is because of the definition of the conditional entropy and mutual information. The proof is thus complete by separately bounding ! and 1/2.
Analysis of (1. We upper-bound (1 with Fano's 's inequality (Cover & Thomas, 2012, Theorem 2. 10.. which proceeds
<1 S H(II, supp(B) î, (B))
< 1 + log (IIII, supp(B)))) Px.W.IL (II, (B)) + (î,, (B))
(9)
Analysis of Cz. Due to the Markov property of (II, supp(B)) + + (Î. supp(B)), we invoke the datc-psog inequality (Cover & Thomas, 2012, Thm. 2.8.1) and conclude
S IIII, supp(B::::: Y X).
Invoking the definition of conditional mutual information, we have
I(II, supp((); Y [X) Ex,wi[hh(X X = xxx))= h(Y II, supp(B), X = x)]
log del (Ex.w.YYYT))
mi
logo?
2
where in 4 we use the property (Cover & Thomas, 2012, Theorem 8.6.5)
h h(Z) 2
log det Cov(Z) s log det E (ZZT)
for random vector Z with finite covariance matrix Cov (Z), and the entropy for Gaussian random
vector. Following the same procedure as in (Zhang et al., 2022, Lemma 11), we have
log det Ex, W YY nm logoa + log det + B B/o)))
which further yields to
n log det (I+ B BB/O2).
IIII, supp(():: Y
X
2
13

---

Under review as a conference paper at ICLR 2023
Summary. Combing (7), (8), and (9) then leads lower-bound on Fx.W.IIB [II, supp(B)) * supp(())) reading as
FX, (II, (B)) * supp log n! + mlog({) - (n/2) log det (I+ B B/o2)
log (III, supp(B)))
Easily, we can verify Px.w w.I.I.B (II, supp(B)) * supp( is lower bounded by 1/2 given the assumptions in Theorem and thus complete the proof.
B PROOF OF THEOREM 3
We define B (n h) 1x
-x Y and define operator imax(i) argmax, [B (1 S m) for each column in B, which returns the index of the entry with the largest magnitude. With slight abuse of notation, denote Bimax thres(B). (B). The benefits of this notation will be seen shortly.
In addition, we define the error Eerr as
Eeer M., s.t. (Y, IIX Bimax
Y. II-X Bimax)
}}-
(10)
According to the sensing relation such that Y = II + W, we rewrite (10) as
XI' + W. B
II + W. W.I 1-X--imai Bimax)
and would like to show it holds with probability near zero. The major technical difficulties come from the fact that is correlated with sensing matrix X, which introduces order moments. The solution of such challenge is broadly divided into the following two parts.
Part I: Relaxation of error event. We first relax the eтrоr event E
Exr S {(XE,) x+(.))
1. (Y.:: Bm.
Xy:). 3 3j++(1))
(11)
Earedax
which means (( S P(Eemrrellx).
Part II: Decoupling dependence via modified leave-one-out technique. decompose the dependence between B and the rows X x0); and Xj.: we modify the leave-one-out technique and
construct perturbed matrix (())), which shares almost identical statistical behaviors as B. Before delving into the technical details, we first provide a glimpse of the construction idea. Recalling the definition of B, which is written as
X
W
B
Σ X X
B
T1
h
we construct the perturbed matrix (())) by replacing the corresponding rows with their i.i.d. samples. The detailed construction method is stated as follows.
To begin with, we draw i.i.d. samples for each rows of X,,; and denote as X,, (1 S S n). Similarly draw samples W,. for each row in W, 1 S j S For arbitrary indices <²(i) and such that j * n (i), we create the samples (() as (assume * (1) and j * 7 r²)))
(0.)) (n h1
Σ
X
XT (0),
B
(
-1
X
Xx X + X
a00 X,x (-0-16),2 X, Ba
+ (n -1
Σ
X.: + X 71)),; W (0) X.W.
(12)
14

---

Under review as a conference paper at ICLR 2023
Provided that i (i), can simplify the summaries X (00. X (1). X (+)(())) and (o), WT ri(i,; + X,, W in the above construction the terms X, X and x. respec- tively. Similarly, we will simplify x X + xx,, as x X)) when j = π (j).
With the above construction method, easily we can verify that ( independent of the rows (0)) X3: and W.,; as they are not involved in ((* Before delving into the technical details, we first collect all required notations.
B. NOTATIONS
Define the following events
Et=r(() X & =
41 visisp log(np)
coo/ h
h E(=r(()) Xe.1 ( (x))11(e)) log(mmp)
(3)
113 4I3i5p
n
n
E(er())) Xe. ( (x.000 1) n n-
vh Vllog(mnp)
Es(
|| visisp
n
Di=l X Wess o Vollog(mmp)
Σ
E, A
yisispissj
h
&s A
(Biax
D (()))
log 3/2 (mp)
B
a (log np) v m(og mn) h
v1 +1) (I
where B E Rº is arbitrary column of B asses m) R denotes its copy with the ith entry being set to be zero, and E I2 denotes arbitrary row in matrix X, which follows Gaussian distribution N(O, Ipxp). Note that æ is not necessarily independent from and B (+))))))
For an arbitrary event E, we denote its complement as E. In addition, we define matrix (()()) as B B (1)3)) For the notational simplicity, we drop the superscript 71) and y in (+) when Imax there no ambiguity. The following context provides the technical details and diagram representing the dependence among all lemmas is put in Figure 5.
Analysis of Fi Equation (13)
Analysis of Fo Equation (18)
Analysis of Fs Equation (15)
Analysis of Fs Equation (17)
Lemma 13
Lower bound on (B', ((rA())))
Lemma 11
Lemma 12
Lower baund on 18mmac
Upper bound on || , 1|x0
Lemma (Es)
Condition on (Lemma 7, 8, 9, and 10) E (2) (s)
(Bioxe 8 (r)
Upper bound
26
Figure 5: Dependence diagram of lemmas.
15

---

Under review as a conference paper at ICLR 2023
B.2 PROOF OF THEOREM 3
Proof. The proof can be broadly divided into three stages,
Stage I. To begin with, we prove the relation Eeer S Eerr-relax whose definition can be found in (11).
Conditional on err-relax, we have
Y X X3:) 4 # + (1). Y 1.5 B Binax X X
Thus we conclude
Y, III Bimax)
Y IIX Bimax) A II + IT;
which suggests Eer-relax will automatically lead Earr in other words, Een-relax Eerr Hence, could upper bound P. (Eerr by IP (Eer-velax).
Stage II. Regarding the relation (Yi., 1,:3 B imax X (
(Y 1,:3 B Biaax X recast it
B (1). (+))))
X xx)())) S (B X (i).:
(+(()))))
imax
(1)))
(T2())))
112
B
B Bimax
B(T
(Xi: - x
x2 (1),
imax
%/ (12(0))))
WW.,, (0,0T
(X,+ - x+))))))
Imax
ni (1.6))
B B(Tl( (X,::
W 1.:1 Bimax
We should emphasize that the subscript imax solely determined by B rather than its perturbed partner (())) This is to ensure B and (s) share the same support set. the following analysis, we will see this property plays an important role in bounding the difference between B Bimax (1) and 7/5 (ar2 (K)))) The following context separately studies
and B. (t) which is contained in 7/3
imax (7)()) i 5). First we define quantities A ((* ()))) (1 < E 5)
each term M7
(1(())
B 2
ma² (log mmp)3
Vma log(mmp) vn
B
Co log srank
B
||| B(=+00)))
n
A (7(0)))) A
log m B
B
())
srank(Ba);
imax
B Moo n (log np)
3/2
B
o / log (log m/ (log np))
( (((()))
A
A (m(()))
a (logn)
B max ()))
Vmllgr loo 3/2 np
A (7(())) A
mo² (log np) (log n (log mn)
o
h
h
16

---

Under review as a conference paper at ICLR 2023
In addition, we define the events o)
Fi (+:) 2 (+
(13)
{In (1)))))))))
|F (0,) |13+()iip)
J2
(14)
Fs _
{In
(1)))
$ $ (5 (0.) {1
(15)
F1 _
{InA |
مA. ( (1)))
(16)
Fs _
{1n6 (0.5))
$ A
(
(17)
F6 _
{11
B ( imax
log(mnp)
B ||
o olog(mmp) v
AA & (1) #
imax
(18)
In Lemma 1, Lemma 2, Lemma Lemma 4, Lemma 5, and Lemma 12, we will show all the above events, namely, Fe (1 $ & 6), hold with probability approaching one.
Stage III. Given the assumptions in Theorem 3, we will verify the relation Nē_ Fe S Ecn-relax- Considering the difference A (i))))
2==2 4 (1),)) we can lower bound it as
A (F (0,5)
(1).)
1
Vlogn log (np)
2 log
SNR
ma²
m
n
srank B*)
Mlgn(lloggp
(Vlog vnn + Vlog np)
log mnp
log
2(log m) (log mnp) n srank
VNR
+
mm +
n
n
G1y2
log n(log mmp)
log" (mmp) + v log n(log mn)
Vmn
n
Under the assumptions in Theorem 3, we have
S1 x k b;
S1/2 log mnp
log
vn
Vm
log n(log mnep)
log log2(mpp) (map)
Co x
/mn
which leads 4 (1,)
5
(7))))
2 G1 SNR G/V - So
mg22
m
!
0, k2 logn
k kvlogm
k log n 122 +1/2 n
where in ① we use the relation m 2 rBt) 2 srank(B)) > 12 log 21++e)
n. Then we conclude
5
Σ
In
(())))))
< (((00))) < (+ I <m (1,))) AIS 7i) # jssp.
2=2
2=2
which means we will automatically obtain Earrdlax when assuming Ne= Fr. in other words. D Fz C Eer-relax- Hence, we can complete the proof by P (Eer) < IP (Eemvelax) S >i= P(Fx).
17

---

Under review as a conference paper at ICLR 2023
Lemma 1. Conditional on the intersection of events & f ( n== (B.
N we have
P(Fi) 2 1 cyn provided n > Alog"(mm))
Proof. Recalling the definition of M, i.e., M 2 B (0,5)) Imax
we divide the proof procedure as
Step Condition on M, we have
(0,)) 2 Tr(M) 1/1
Co log n /srank
B(+ imax
AA S (1) + j S n,
F
hold with probability exceeding n
Step II. Provided n > k +log"(mmp) we have
Tr(M) 2 | mo² mlog)
/in log(mmp)
B
n
condition on & n (B n (BB))
For the clarify of presentation, we defer the proof of Step II to Lemma 13 and focus on Step I. Due to the construction of ((= in (12), we conclude (rr is independent with row X x Hence first condition M and rewrite term 7n in terms of quadratic product xc Max where E IR' is a random vector satisfying x E N(0, Ipxp).
With Hanson-Wright inequality (c.f. Theorem 6.2.1 in Vershynin (2018)), have
PP (In (b,.)) Emy (0,0 2 4. F1 < Fis
S n² IP (|x Mæ Tr(M) 21 S n². 2exp (-c0
[M
Or
M
Setting / = log Mp we have
(+)))) > Eni" (1)-)) co log r M F
Tr(M) co log |M v1 71() # fjsn. S
holds with probability - - Then we complete the proof by showing
|M]| < B O
(())))
1
B
B (w,)
V (rank(Bt)
where ① is due the definition of stable rank.
Lemma 2. We have P(F2) 2 4n -c where event F2 is defined in (14).
Proof. First we fix the indices xT(i)) and j such that n r²i)) * j. Due to the independence across the rows of X, we conclude
P (1x Myl λ log MlIp) < P [x Myl 2 log
|Myll2 S Vlogn||M|p)
+ TP [lMyll2 2 /logn||[]
1
My R TP |z
ž / Tog Myllz) + 2n < 4n
where M is defined as B B ((),)) and in ! we have the rotation invariance of Gaussian random vector. Regarding the event Fz, we invoke the union bound and complete the proof as P(F2) S
imax
n2 c 4e
18

---

Under review as a conference paper at ICLR 2023
Lemma 3. Condition on Es, we conclude I (Fales) 2 1 1-2n where Fi is defined in (15).
Proof.
First we recall the definition of 173, which is written as
1/3 - (BaT Xi.! (Bimax
T (X,+ - X..)). B B imax
We begin the proof as
P (FFl(s) IP | x1 11. 2 log n BI
2 F
31 S mlEs)
IP
F3,
|Ba X < log
B
J 1A
visisnnEs)
For the first term, invoke the Hanson- which leads to
Hanson-Wright Wright inequality (c.f. Theorem 6.2.1 in Vershynin (2018)),
P |BaT |
X1.1l2
2 log
B
E1 sisia iis m/Es)
I n P
(IIIB:
X,, -
X
log B (1
log² n BIIl IF
log n
B
2n exp
-c
s 2n -0
B
B
lo
For the second term, we will prove it to be zero. This is because
(+,5))
|B X xxt()).l22
(Bimax
B ((:) imax
(X,.: - X X
log 3/2 (mp)
(log np) v mm)
log n
B+Il
B 11l1
n- h
n - h
for all 1 1 (1) # S n, where in ! we condition on E, and
B X S Vlogn B
Lemma 4. We have P(FF))
4n
Proof. First we fix the indices n (i) and j such that (") + Invoke the definition of B (i).) imax
we conclude W.... i... B imax complete the proof as
(1).))
X Xj and (,) are independent with each other. Hence we can
IP 114 (11))))))
2 a(logn)
B ((+)())>))|
11]
imax
P
B (()))
imax
(X,::
X 11, Vlog
B (1))) 1t)
(Inal 2 (logn)
B (1))))
(X,; X xx+(0>>) 1// 2 Vlog n
((
||]
imax
imax
imax
2n + P (Iaal 2 /lolog
B (1))T) imax
(X
xx 11,)
1
4n
where in ! we use the tail bound for Gaussian random variable. The proof is then completed with the union bound such that
P (F4) S TP (1n5+)(0))) (1)())))) 2 a (log n)
(0)()))))))) imax
||. < 4n²
4n
19

---

Under review as a conference paper at ICLR 2023
Lemma 5. Condition on Es, we conclude P(Fss Es) -
Proof. The proof in a similar form of that for Lemma 3. First we decompose the probability P(Fo(et) as
P(F ([Fs(8)) (6)) & KllWa.ll 2 ov mlggn Sisisn nl + Fs. Wa,ll2 & mlloog n, visis (
< 2n n
Fs. WW,ll22 S Lov logn, AA S S n|
where the last inequality is due to the tail bound for the Gaussian random variable. We complete the proof by showing the second probability zero. This is because
Inb
(1:))) <
||aalll2
|
( maxx
B
((-))) imax
Vm log 3/2 np
log
mo² (log np) v (log n (log mn)
B o +
n n-
n -
Lemma 6. Conditional on the intersection of events & n & (B). P(Fs)= =1
(BBB) we have
Proof. We complete the proof by
B ((),)))))
B
Σ
B
(a(())))
3
Blmx
2
3
Bimax
(r)()))
B
B
2
Imax
Imax
1
2
2ND
log" 2 (mmp)
|
mo²
log" (mmp)
where ! is due to the fact such that 3 (1),)))) Lemma 12.
B has only one non-zero element, and @ due to
B.3 SUPPORTING LEMMAS
Lemma 7. We have PP(E) 2 2n p when h >> log np, and n,p are sufficiently large.
Proof. Due to the Hanson-Writ Wright inequality (c.f. Theorem 6.2.1 in Vershynin (2018)), we have
P (EE) < 2pexp exp [-c (n log(np)
2 A ((n-h) h) log(np) (| (
!
2p n nppp"
=2n 2 02
[[-
ooo
where in ① we use the fact n - h > log(np).
Lemma 8. For fixed B E RR, we have (3)) 2 pe co -1 m2p
Proof. To begin with, we construct the sensing matrix Xs by concatenating all rows X such that f = ((). With union bound, we can upper bound (E2(33) as
(E2( < pP (Ix 2 22(m h)ll h)ll
カーZ Σ X x Xe.. Bi,) 2 v(n h) (mlp))mmp))))) 11 |x < /2(n h311B E=1
+ plP
20

---

Under review as a conference paper at ICLR 2023
Since X are with i.idd Gaussian entries, have each row in X be Gaussian random vector with and variance (,, Hence, have |Xs IB/ 2 be x² random variable with freedom n h, which leads
! G S pexp
(log 2 -1) S pe -0.65(n-)),
where 1 is due Lemma 15.
For (2, we notice that X is independent of the inner product (Xe,;, (k.)) Hence, we can view the
product Et= Xe, (X.,, (ir) as a Gaussian random variable N(0, |X (11)), which leads to
n-h
C S pP
Σ Xx, (.e....)) 2 [x 2n "mnm5mmm "p p
where in @ we use the tail bound of Gaussian random vectors.
Lemma 9, For a fixed 3 E IR?, we have (33) 2 cpn -on -m
Proof. According to Lemma 16, we can decompose the index set {e: L * (2) into three disjoint
sets I such that (i) indices l and x² (C) do not fall into the same set Zy; and (fi) the cardinality of each set satisfies h, & It N 1. (1$j$3)
Then decompose product E0))(() X (X (())
Σ
X (X (X=:(.1)
Σ X (x (x.10))..
(())(()
f=1
With the union bound, we have
((Es(()) S p
ΣP
Σ Xes Xe, ( (x) 3t) 2 (logmp) v hy |+
(19)
1=1
NET
Due to the properties of Iy, we have Xe, and (X (X (3)) be independent and hence
P
Σ X (x.(()..
log(mmp) Vhy |
FEI,
P
X XIEZZ,
log(mmp)\1)|110911
801 ||3 log(mmpp)) 1h
Σ Xes X (xM10) 2 log(mmp) / ||
+ P
EET,
1
exp
h4
(log(co log co log mmp + 1) 2
IP Σ Xe, (X 2 v log mopplplle X
FET
n
m
cop
c0 +
n
m -pp pc x n 5m "mpppp c
where ① due Lemma and ② is due to the Gaussian tail bound. Plugging it in (19) then completes the proof.
21

---

Under review as a conference paper at ICLR 2023
Lemma 10. We have P(E.) 2 on m mpp9
Proof. We complete the proof as
! P
P(E.)
mp-
x Wes 2 o oviloo(mmp))
mp
PP
(|xxil 2 v vn /lgg(mmp)) +
Σ 1=1
Wes 2 Lovalog(mpp) ||x 2 / /nlog(mmp))
(log(co log(mnp)) - co log(mmp) + +1] +P (
n
Σ p=1
X Wes 2 lovllogmmy X.sil2
mp
exp
mp (n 00 cop co
5 p p- x n
50 m pp-
where ① and @ are due the union bound, @ is due to Lemma 15, and 4 is due the tail bound for Gaussian random variable.
Lemma 11. Conditional on the intersection of events & 0 ( n Ea, we have
Vlo(mmpp)
a log(mmp)
|8
1B maxx
||3
imax
Vni
vn
where imax and max are defined as the indices of 3 and 3 with the largest magnitude, i.e. imax A argmax,13, |3, and max & argmax, (8)), respectively.
Proof. To begin with, we define (10) (()) and (1)
as
x2. 1.8 B
h
8=1
(0
(e..1 BQ,);
Xe,
(0)
X1. X (x))())::))))
f=n-h+1
(
Weji
respectively. Then can write 3, Σj Due to the definition of imax, conclude [mmaxl 18 maxl where max is defined the index of 3 with the largest magnitude, i.e., max و
argmax, |.71. With triangle inequality, we obtain
ks (imax)
Blmaxl
maxx 2 ||| (max)
|s| (max))
(20)
j=2
The following context separately discusses each term. First, we consider |s| (imax) and Conditional on ε,, we have
|c| (max)
log(np)
Si (mmax)
5
1 + Co
1,3 13thaxl
1.3h A
(max)
1 1- co
log(np)
|.3 maxl
| mmax
(21)
22

---

Under review as a conference paper at ICLR 2023
Then turn study the rest of terms. Conditional on E2( N (39 E
have
122
(imax)
152
(max)
log(mmp)
|
log (og(mmp) v
[3
(imax)
(max)
| 22
Isa
(imax)
1.4
(max)
2/
σ v n (mm(p)
(22)
h Combining (20), (21), and (22) then yields the lower-bound for | imax
1 10mmxx
(max)
|s
(max)
Σ
(Is)imax)
+ 15, (s/mmax))
J=2
log(mmp)
cg log(mmp) Vh
CLTV Cnoy/loo log(mmp) n h
1 maxl
||
11:0
c2V n1
n
which concludes the proof 2 h.
Lemma 12. Conditional on the intersection events & 0 (2(3))
n E we have
log(mmp)
o log(mmp)
- 10 S
| +
Vn
Vn
Proof. For an arbitrary index i, we consider the difference B B which can be written as
B, - g
Σ
X - 1) |
Σ
X
n1
(
(()
n Wes
Xes (x)(0)
x
71
n
Conditional on the intersection of events & ( E we can bound 0; (L 4).
as
log(np)
IG S V h 1.81;
log (mmp)
152| S
||
n
log(mmp) vh.
ISal
| 12:
h 0 / n log(mmp)
Isal S
n h
respectively, and complete the proof as
|41 + 162 log(map) n
||0 and h < n.
Lemma 13, Conditional on the intersection of events El m Eg ( have
(B) we
((+))))) B
|B
mo² mnp)
Vmo log (mmp)
B
imax
provided >> k(log mmp)).
23

---

Under review as a conference paper at ICLR 2023
Proof. First, pick one arbitrary column 3 of BA. W.l.o.g. assume that @ 0. Then obtain
|B (1(()))))))
B imax
B imax
100
where 3 (1:()) denotes the corresponding column in ((,)) Then we obtain the following lower bound on 3imax
B iimax
3 imax
(Bitma)2 -18
t (1).))))
1000
(23)
Similarly, show (23) holds well when B O. Recalling the definition of Mmax to put more specifically | max 2 |33| (1 S i S p), we can further lower bound 3imax 3
Imax by
(max)) 1, max (1)
100
For | we can lower bounded it by Lemma 11. While for ||3 ( 1 cannot directly use Lemma 12 since, strictly speaking, concerns X with rows ( x,, rather than
(0) Xj. However since they follow the same distributions, we can follow the same procedure
and show
13 - -Ba 1801 S
log(mnp)
a log(mmp)
||3 12
n
nn
Then we obtain
2
Bimax Fmax
[
v Alg(mmpp
||
12
o log(mnp)
vn
vn
(log(mmp) vn
log(mmp))
/
11,3
/n
[log(mmp))
log(mmp)
maxl
- 1,3
||,3
12
+
Vni
V
log(mmp)
[1,31113 [ + 0² log(mmp))
where in ① we use the relation (a- b)2 > a²/2 b² Under the assumption 2 k:log mmp)?,
have haal 2 llat >> log log(map) (10222/((2 and thus
log(mmp) Vn
log(mmp)
18t 1
3
||
Vnk
where in @ we use the fact that x:2 2ax is monotonically increasing in the region (a, oo); and the equality is achieved when 1/8 l|s la/vR. Hence, obtain
log(mmp) log(mnp)
a ollogmmp
o² (log mmp)
3t imax
||
||03||2
Vnk
Vn
Having obtained the lower bound for one single column of B we complete the proof as
(+)(()) imax
BB)
Σ
3
B
=
.90
log (og(mmp) log(mmp)
Vina log(mmp)
mo² mmp)?
|B
k
nk
/n
n
x k-1 since ni log (map))
where 3 comes from reorganization of the terms and the inequality E.r 11,3112 5 vm
B ||
24

---

Under review as a conference paper at ICLR 2023
Lemma 14. We have P(Es) 2 4n "p c.
2n
m
Proof. We begin the proof with the union bound
PP (85) $ P |mai 2 v log np, 31sisp) +P (KKr 9'> 2 Vlog np mppl(3112)
$ 2mp-n Sp-p--
+ PP | 2 o Ioogogmm nm, 1 isism
< 2mm-n sm ==2n c' c'm=" d'
+ P EEs: || S vlo np, ((, | S
Vlog np | |10l S o /lg nm
where w() and (.)) denote the corresponding entries from W and W.
Then we would prove that 8 is zero. The technical details are attached the following. Due to the fact that B (+-j) shares the same support set as Bimax; we have
imax
Biimax
B((.3) imax
T
2
Dimax
Bimax
3 (((2)
(log np)
Σ
3
imax
3
Bimax
(o.j)
(log np)
Σ
Bimax
B
((,1)) Pimax
g
where in I we condition on the relation
|| S Vlognp.
(llitn 11o0 S |13 -
113-3\(60) 3\1i0)
Regarding 1maaxxxxx
3 Bimax lloo, we have |13 |mxm
1100 Again, this fact
relies heavily on the fact such that B(tai) shares the same support set as Bimax- Otherwise, the best
((6.2)
113 ((x))) llxe). Afterwards, we obtain
result we can have is |1@3
B 3imax
10 S max
|13 Imax
(0,))
3
10 S (n - 11) -1
X
8i
+ (n h)
X (1). 7 (1) x X (1). .1) X i
2AQ 2A 5
(n h)
|, B loc + (n - h) -1 | 100
(n h) 1 || (z B + (n h) | 0a 1
(n h) - (log mp) 1| + (n - h)-
o (p) mm)
where in @ we use the condition || |0= x npg [ | x v Vlog rip e ||,, and ||o|oo x Vlog nem.
Iterating over all columns B can show &g holds with probability one provided || S vlog np, (a, | S Vlog npll,55112, and ||w|llo S Vollog nm, in other words, & is zero
25

---

Under review as a conference paper at ICLR 2023
C ADDITIONAL NUMERICAL EXPERIMENTS WITH REAL-WORLD DATA
This subsection evaluates our algorithm on the MNIST dataset (LeCun et al., 1998). We first create the sparse matrix as block-diagonal matrix diag (image)) Irain image test immaee train ... imageg where image: train 28 (resp. image; test 222222 represents arbitrary image of digit i (0 i < 9) in the training (resp. test) set. Then, we create a Gaussian sensing matrix X and noise matrix W. Afterwards,
permute the sensing results and apply our algorithm in Algorithm to reconstruct the images. As the benchmark, we ignore the missing correspondence and directly estimate B with Lasso estimator. In other words, let I in (3) be the identity matrix and use estimate the images. An illustration of the reconstructed images is put in Figure 6.
Ground- Truth
w
2
P
Permutation
1
2
0
Correction
No-Permutation
Correction
Figure 6: We set the sample number as 100 and the sensing noise variance o² as 1. (Top) The ground-truth images. (Middle) The reconstructed images with our algorithm using both (2) and (3). (Bottom) The reconstructed images only using (3), where II is simply set as I.
D USEFUL FACTS
This section collects some useful facts about probability for the sake of self-containing. Lemma 15 (Dasguuta & Gupta, 2003)). For -random variable Z, which with freedom f, we conclude
E
t
t
P S t) S exp
+1
t<t:
2
{
[
P P 2 1) < exp
{ + 1>
x11]
E
Lemma 16 ((Pananjady et al., 2018)). Suppose the permulation matrix II with Hamming distance from the identity matrix I, namely, dh (I, II) = h. We can decompose the index set {i: i T T(i) into
3 independent sets I, (1 < 3) such that the cardinality of each set satisfies [I 2 [h/3] 2 h/5.
26


Reviews:
[{"review_id": "gOnMhxcZA0A", "reviewer": "Reviewer_7u4U", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "This work considers the problem of reconstructing sparse vectors from an underdetermined system of equations when the measurements are commuted.\nFirst, it gives a lower bound on the required number of measurements given a certain SNR.\nThen, it analyses an estimator which gives corresponding upper bounds (depending on the number of measurements, signal-noise-ratio, sparsity level, ambient dimension, etc.)\nThe 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.\nNumerical experiments corroborate the theoretical findings.", "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.", "strength_and_weaknesses": "Strengths:\nTo 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.\n\nWeaknesses:\n1.The dependence of the number of measurements on the sparsity level is quadratic instead of linear. \n2. 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.\n3. In general, the presentation of the material can be improved; see some of the comments below.\n\nFurther comments:\n1. 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!\n2. page 3: \"let $n$ approach infinity\". Consider replacing this statement with something more rigorous. Is this an asymptotic or non-asymptotic statement?\n3. 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.\n4. 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!)\n5. page 5, Corollary 1: \"where $n$ and $p$ are sufficiently large. Consider replacing this by a more rigorous statement.\n6. page 5, Theorem 3: Has $h$ been already properly introduced? If yes, it might be a good idea to recall its definition!\n7. page 7: Why does $ \\Vert B^{\\sharp} \\Vert_F $ affect the reconstruction error? I do not understand this statement.\n8. 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.\n\nTypos:\n1. page 5 sin(c)e all these works", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "evCfc3IycV", "reviewer": "Reviewer_KfQu", "summary": "", "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": "", "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. ", "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.", "strength_and_weaknesses": "Strength:\n\nThe studied problem is at least of sufficient theoretical interest, and the technical results seem to be novel. Besides, the proposed algorithm is sufficiently simple.\n\nWeaknesses:\n\n1. 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 \u0000$k(\\log n)(\\log^2 m n p)$\u0000\" 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. \n\n2. 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. \n\n3. 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. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ZGZKBnQo6n", "reviewer": "Reviewer_BXq7", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "The paper considers the problem of unlabeled sparse recovery under\nmultiple linear measurements. Statistical theorems are derived for\nunderstanding the proposed estimator.", "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.)", "strength_and_weaknesses": "*STRENGTH*:\n- The paper derives two solid theorems about permutation recovery:\n  - Theorem 2 states that exact permutation recovery is impossible for\n  fixed $m$ and $p$, as long as $n$ approaches infinity. The condition\n  is very simple and the theorem is very clean.\n  - Theorem 3 states that the ground-truth permutation can be recovered\n  exactly with high probability by solving the linear assignment\n  problem (2), as long as (iv) SNR is larger than some constant,\n  (iii) the number of permuted rows is small enough, (ii) the stable\n  rank of the ground-truth matrix is larger than some logarithm of the number\n  of samples, and (i) we have sufficiently many samples. Once the\n  permutation is correctly recovered, the recovery of the ground-truth\n  matrix ensues, based on the results in compressed sensing.\n\n- Figure 2 presents an interesting phenomenon where\n  the number of samples is actually a double-edged quantity in this\n  problem. As Remark 2 discussed, larger $n$ violates the stable rank\n  condition (ii). Another perspective might be found in Theorem 2 and\n  Theorem 3: With $m$ and $p$ fixed and $n$ approaching infinity, the\n  recovery of the permutation becomes impossible. All these suggest\n  that, in order for exact recovery, the parameters $m,p,n,h$ might\n  have a more sophisticated dependency than the theorems reveal. It\n  would be interesting future work to discover such dependency.\n\n- The proof outline (Sec 4.2) is great as it helps the reader to better\n  appreciate the technical challenge and thus the contribution of the\n  paper.\n\n- I found Table 1 informative. It positions the paper in the\n  literature very well. From it, one can also find that the paper\n  advances our theoretical understanding of the problem.\n\n*WEAKNESS AND QUESTIONS*:\n- In Theorem 2, the supremum is taken over $B_{p,m}$. Why this is\n  required? I thought that, since $n$ approaches infinity, this set\n  would eventually be the entire set of $p\\times m$ matrices.\n  Furthermore, should it be stated in Theorem 2 that the ground-truth\n  matrix is given as in Theorem 1? Or this is actually not needed for\n  the sparse case?\n- Personally, I think that, if possible, it would be greater if an\n  explanation is given regarding the phenomenon discussed in Remark 1\n  and Figure 1. I guess the authors have an answer as to keeping more\n  entries might break down the proof. This discussion is important as\n  the situation is very different from what is commonly known.\n- Sec 4.3 looks a little bit mysterious to me. It seems not very\n  rigorous to claim that the proposed estimator is computationally\n  optimal. For example, despite being incorrect, the estimator that\n  returns an identity permutation and a zero matrix is computationally\n  optimal, as it does not require any computation, let alone matrix\n  multiplication which is needed by the proposed method. The\n  point is, to make such a claim, one needs to prove that (informally\n  speaking) there is no estimator that takes fewer operations\n  (constrained to its correctness).\n- Why is the paper titled *one-step estimator*? The proposed algorithm takes\n  two steps, first recovering the permutation and then the sparse matrix.\n\n*MINOR COMMENTS*:\n- Typos or grammar problems at:\n  - the first line of page 5 (sine -> since)\n  - footnote 4 (extend -> extent)\n  - the line below Equation 5 (accomplish -> accomplished)\n  - the last line of page 7 (is -> are)\n\n- There seems to be some citation issue at the transition of page 4\n  and page 5. Please fix it.\n\n- In the abstract, it is claimed that the case of the sparse unknown\n  matrix in the *insufficient samples regime* is considered for the\n  first time. This might be an overclaim. See for example\n  - [1] Compressed sensing with unknown sensor permutation (ICASSP\n    2014). There, the *insufficient samples regime* is studied\n    computationally (Sec 3).\n  - [2] Sparse recovery with shuffled labels: statistical limits and\n    practical estimators. There, the *insufficient samples regime* is\n    studied theoretically and computationally (as the paper noted).\n  - [3] Homomorphic sensing: sparsity and noise (ICML 2021). There, the\n    *insufficient samples regime* is studied theoretically and\n    computationally (Sec 3).\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6SMNSo-IEo", "reviewer": "Reviewer_Q6i9", "summary": "", "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": "", "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^*$. \n\nThey show the following: \n\n1. 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))$.  \n2. By formulating the correspondence recovery as a linear assignment problem (LAP), they show that the correct permutation matrix\ncan be obtained when SNR is above certain positive constant.\n\nTheir results are the first ones s.t. SNR $\\geq \\tilde \\Omega(1)$ is sufficient to obtain the correct permutation matrix with insufficient samples.  ", "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. ", "strength_and_weaknesses": "Strengths: \n1. The paper provides new lower bounds on SNR and sample complexity required for recovery for the problem of unlabelled sparse recovery under multiple measurements. \n2. 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. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject