Unlabelled Compressive Sensing under Sparse Permutation and Prior Information
Authors: Garweet Sresth
Satish Mulleti
Ajit Rajwade
Venue: Accepted by TMLR ()

Abstract: In this paper, we study the problem of unlabelled compressed sensing, where the correspondence between the measurement values and the rows of the sensing matrix is lost, the number of measurements is less than the dimension of the regression vector, and the regression vector is sparse in the identity basis. Additionally, motivated by practical situations, we assume that we accurately know a small number of correspondences between the rows of the measurement matrix and the measurement vector. We propose a tractable estimator, based on a modified form of the \textsc{Lasso}, to estimate the regression vector, and we derive theoretical error bounds for the estimate. This is unlike previous approaches to unlabelled compressed sensing, which either do not produce theoretical bounds or which produce bounds for intractable estimators. We show that our algorithm outperforms a hard thresholding pursuit (\textsc{Htp}) approach and an $\ell_1$-norm estimator used to solve a similar problem across diverse regimes. We also propose a modified \textsc{Htp} based estimator which has superior properties to the baseline \textsc{Htp} estimator. Lastly, we show an application of unlabelled compressed sensing in image registration, demonstrating the utility of a few known point correspondences.

Published in Transactions on Machine Learning Research (MM/YYYY)
Unlabeled Compressive Sensing under Sparse Permutation and Prior Information
Garweet Sresth
gorweetaresthh@gaall.o com
Deportment of Electrical Engineering
II Bombay
Satish Mullcti
matish.
Department Electrical Engineering
IIT Bomboy
Ajit Rajwade
ajilur@cse.itb...o ac..ba..... in
Department of Computer Science and Engineering
IIT Bombay
Reviewed on OpenReview: /ttps://openreeee opwnrevieee.e.eee...mmm net/ forum? id- HaAg9RN7Hs
Abstract
In this paper, we study the problem of unlabeled compressed sensing, where the corre- spondence between the measurement values and the rows of the sensing matrix is lost, the number of measurements is less than the dimension of the regression vector, and the regres- sion vector is sparse in the identity basis. Additionally, motivated by practical situations, we assume that we accurately know a small number of correspondences between the rows of the measurement matrix and the measurement vector. We propose a tractable estimator, based on modified form of the LASSO, estimate the regression vector, and we derive thcorctical error bounds for the estimate. This is unlike previous approaches unlabeled compressed sensing, which either do not produce theoretical bounds which produce bounds for in- tractable estimators. We show that algorithm outperforms hard thresholding pursuit (HTP) approach and an f--norm estimator used to solve similar problem across diverse regimes. We also propose a modified HTP based estimator which has superior properties to the bascline HTP estimator. Lastly, we show an application of unlabeled compressed sensing image registration, demonstrating the utility few known point correspondences.
1 Introduction
Estimation of an unknown vector 3" E RRP from its (possibly noisy) linear measurements A,8 E TRN, where E RNXx the measurement matrix, is a well-studied problem that naturally arises numerous fields. However, in some scenarios, the correspondences between the rows of the measurement matrix and the measurements get partially or entirely lost due errors made during the measurement process. Specifically, the permuted and noisy measurements given
y = PAA'" + w.
(1)
where N is the measurement noise vector and P E NxN denotes unknown permutation ma- trix. Hence, the problem reduces to that of estimating the unknown regression vector from an unknown permutation of its measurements. This problem, known as unlabeled sensing, appears in applications such as simultaneous localization and mapping in robotics (Thrun & Leonard 2008), record linkage (Lahiri & Larsen 2005), image or point cloud registration (Pan & Zhang, 2005 Li et al., 2021), sccurity and privacy Narayanan & Shmatikov 2008), and simultancous pose and correspondence determination in computer
vision (Marques et al. 2009).

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Unlabeled sensing is well studied theoretically in the over-determined regime where N > p and typically, under the assumption that the entries of A are drawn i.i.d. from an arbitrary continuous probability distribution. Within these settings and without measurement noise, Unnikrishnan et al. (2018) and Han
itt al. (2018) state that every 8 E IP can be uniquely recovered with probability one from its measurements PAB it N 2 2p. Under some more assumptions on 3 the condition N 2 2p can be relaxed to N 2 p+1 1 Tsakiris Peng 2019). The over-determined unlabeled sensing problem is challenging in the presence of noise. In Pananjady et al. (2018): ; Hsu al. 2017), the authors have derived lower bounds on the signal-to- noise ratio (SNR) for approximate recovery of 8 Algorithms to solve the problem for different values of p are suggested in Peng & Tsakiris (2200); Tsakiris & Peng (201)) Candes & Tao (2005) Slawski & Ben-David p Sresth et al. (2024) extends the approach in Sllaski & -ee- Ben-David (2019) by assuming that some correspondences between the rows of the measurement matrix and measurement vector are known.
An under-determined unlabeled sensing problem, where N < p, can be solved with some additional priors on 3 To the best of our knowledge, Peng et al. (2021) is the only work in the context of unlabeled compressive sensing. In Peng et. al. (2021), the authors assumed that 8 is k-sparse (i.e., it has at most. k non-zero elements) and showed that N 2k measurements noise. Interestingly, the result is analogous to that proved for the over-determined unlabeled sensing problem from Unnikrishnan et al. (2018). On the algorithmic side, a bard-thresholding pursuit- based approach is proposed for unlabeled compressive sensing in Peng et al. (2021). However, no theoretical error bounds on the performance of their algorithm are established in Peng et al. (2021). and moreover, their algorithm involves a computationally expensive fı-norm optimization step to determine the unknown vector 8 Also, Peng et al. 2 employs subgradient method in their algorithm where the function value may not always decrease across the iterations of the algorithm, as mentioned in their paper.
sufficient for unique recovery in the absence of
In several unlabeled sensing applications, such as image aligmment, record- linkage, etc., we encounter sparse permutation scenarios, that is, the correspondence between the measure- ments in y and the rows of A is incorrect for only a small fraction of measurements. Equivalently, we have that |A A < N. Moreover, in many applications, some of the correspondences between the rows of A and the rows of y are known a priori. For example, in the image aligument problem, many point correspondences in the two images being matched are obtained via feature point matching methods such Lowe (2004), with permutations often occurring due factors such image self-similarity (i.e., similarity of patches in distant image regions). However, domain expert can manually mark a few corresponding point pairs in the fixed and moving images, thus yielding some measurements with correspondences known in advance.
Possible Prior Information:
Nguyen & Tran 2012) propose robust form of least absolute shrinkage and selection operator (LAssO)) which can estimate the sparse regression vector from its grossly corrupted linear measurements. Treating the permuted measurements gross corruptions, robust LASSO can be employed to solve unlabeled compressed sensing problems. However, motivated previously, if there is a prior knowledge of some correspondences between the rows of A and the rows of y, robust LASSO is not able to make use of it. A natural question is how the prior knowledge of some correspondences would improve the estimation of 3 Such questions are answered in an over-determined setup in (rrett et al. (0024). However, these questions are still open to under-determined, unlabeled sensing problems.
1.1 Our Contribution
Our paper presents the following contributions:
1.
We propose two algorithms to solve the unlabeled compressed sensing problem which can make use of known correspondences is available:
Augmented Robust LASSO (AR-LASS)), modification of the standard least absolute shrinkage and selection operator (LASSO).
(ii) Augmented Hard Thresholding Pursuit (A-HTP) which involves a gradient-descent step and computationally cheaper fg-norm optimization step, rather than subgradient-mette and f1- norm optimization required in the earlier approach proposed in Peng al. (2021).
2

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Symbol
Mcaning
N
total number of measurements
m
number of labeled measurements
71 = N
m
number of potentially unlabeled mcasurements
p
signal dimension
E R
vector of compressive mcasurements
8* E Rº
unknown sparse signal vector
A E N
sensing matrix
e" E IR"
unknown sparse permutation corruption vector fg norm of 3" tn norm of ex sub-vector of measurements with known correspondences
k
8
1/1 E Rm
1/2 IR"
sub-vector of measurements with potentially unknown correspondences measurement noise vector
w E R-
Table Glossary of symbols used in this paper.
AR-LASSO is suitable for both compressible and perfectly sparse regression vectors, unlike the earlier approach in Peng et al.] (2021), which works only for perfectly sparse regression vectors. However, A-HTP can work only in the case of perfectly sparse regression vectors. Note that AR-LASSO and A-HTP algorithms are applicable even when there are no correspondences known. Moreover, apart from the unlabeled sensing problem, our algorithms are applicable in any regression problem where some measurements grossly corrupted, and the measurements can be separated into two disjoint sets: (i) measurements without any gross corruption and (ii measurements with possible gross corruption.
2. For both AR-LASSO and A-HTP algorithms, we derive thcoretical upper bounds on the estimation error of the unknown vector in terms of the number of measurements N, number of permutations s, dimension of the unknown vector p, sparsity of the unknown vector k, number of known correspon- dences m, the number of measurements n == N - m with potentially unknown correspondences, and mcasurement noise variance a². Specifically, for AR-LASSO, we characterize the notion of a generalized, extended, restricted eigenvalue condition (GEREC), which enables to prove perfor- mance guarantees for the algorithm. GEREC is generalization of the extended, restricted eigenvalue condition studied in Nguyen & Tran 20012) to a scenario where some of the correspondences are (possibly) known in advance. We show that the family of Gaussian measurement matrices obeys GEREC with a high probability. We compare our error bounds to those obtained in Nguyen & Tran (012) and demonstrate that the information of known correspondences allows us to tolerate a larger number of permutations and also results in a lower estimation error.
3. Further, we demonstrate a geometric convergence result for НTH under the condition that the sensing matrix obeys some form of restricted isometry property. A-HIP involves joint-estimation of xt, which is a row concatenation of 8 and the permutation corruption vector, through an 0 Omx(N-m)
augmented matrix A
In order to exploit the distribution of non-zero entries
[(N-m)x(N-m)
in x", we introduce a notion of daructured-sparsityy restricted isometry property. Following this, we demonstrate that N 2 C(k log (p/3k) + s slog (n/3s)) (where C > is a constant) is sufficient condition for an accurate recovery via A-HTP, which is more relaxed requirement than N > c((k+5) log ptn)) which is what obtains from naive analysis without exploiting the specific sparsity structure of x*
Next, we compare our algorithms the nnnrrm hard-thresholding pursuit approach from Peng et al. (2021) and to another f--norm-base based estimator motivated from Candes & Tao (2005). across diverse regimes. We demonstrate that algorithms outperform them across all the regimes examined.
3

---

Published in Transactions on Machine Learning Research (MM/YYYY)
5. Lastly, demonstrate the impact of utilizing known correspondences in image registration task. For this task, the problem of unlabeled compressed sensing with sparse permutations and a set of priors is especially relevant in the following manner: (i) In many image registration tasks, a domain expert can mark out a few point correspondences accurately. This provides prior information for the regression problem. (ii) In image registration, the underlying motion vector fields are sparse or compressible in universal dictionaries such as the discrete Fourier transform or discrete cosine transform (James et al. 2019). If salient feature point tracking is used for obtaining point corre- spondences, then the motion vectors at only small set of points (in the image domain) are observed. This is therefore a compressed sensing sparse recovery problem. (Mi) A fraction of the computed point correspondence pairs suffer from permutation effects due to factors like self-similarity. This is therefore an unlabeled sensing problem where the permutation set is sparse. For more details on this, please refer to Section and Figure of the supplemental material.
Summarily, techniques presented in this paper are simple, but this is the first piece work to present a thcoretical analysis of unlabeled compressed sensing (a topic with very limited literaturo) for any Iraclable estimator. The key contributions in the proof techniques used include: (1) the proposition of generalized, extended, restricted eigenvalue condition (GEREC) and its use within the AR-LASSO bounds; (2) concept of structured-spansity,, restricted isometric property (Ss-RIP) and the use of the specific form of structured sparsity in the (p + n))dimensionnal vector x := [3 e e'T]" being recovered namely that the sub-vector corresponding to 8 E R' contains k non-zero elements, and the sub-vector corresponding to e* E IR. contains 8 non-zero elements. The use of such structure to obtain requirement on the minimum number of measurements for an accurate recovery of x* via A-HTP is novel, and is not found in classic papers model based compressive sensing such Baraniuk et al. (2010).
2 Problem Formulation and Notations
Consider a set of linear measurements as in equation with N < p and the following assumptions:
(C1) w N/0, ((O,o0IN) and A' (O, Σ) where A E R2 is the i-th row of the measurement matrix A, and IN stands for the N x N identity matrix. We denote the smallest eigenvalue of Σ by Cmial (E), the largest eigenvalue of Σ by Cmax (E) and the largest entry on the diagonal of E by {(E).
(C2) The regression vector 8 is k-sparse where & need not be known in advance. We denote the support of non-zero entries of 3 by the set T.
(C3) Any m out of N measurements have accurate correspondences where m < p. Without loss of generality, we assume that the correspondences of the top m measurements are accurate, that is, y: = A'3* + wi for i = 1.2,...,m..
(C4) In the remaining n = N m < p measurements, at most s & n measurements have incorrect correspondences. However, we do not know the value of and which s measurements have incorrect correspondences.
With assumptions (C1)-(C4), we decompose in equation I as
(2) where y1 E RT denotes the sub-vector of measurements with known correspondences, y/2 E R" is the sub- vector of remaining measurements (with m + n N) and Pa Raxa an unknown permutation matrix. We denote == TrT - A == [AT AT]² and w = [wo w T For further analysis, define the permutation corruption vector as
y A,8* + wi and y2 3 + W2.
z' === (P2A2 A²3") R..
(3)
4

---

Published in Transactions on Machine Learning Research (MM/YYYY)
The assumption (C4) implies that e* is s-sparse. We denote the support of non-zero entries of e* by the set S. Using equation 3 we can write equation 2 as
y2 = A28 + Vne" W2.
(4)
The goal is to estimate 8 under assumptions (CI)-(C4.. To this end, we provide the formulations for AR-LASSO and A-HTP algorithms the next sections.
3 Augmented Robust LASSO
With the introduction of e", the objective of estimating 8 from y under assumptions (C1)-(C4) is posed as convex optimization problem. Specifically, we propose to minimize an augmented, robust, least-absolute shrinkage and selection operator (AR-LASSO)- based objective function, given by:
L(3,e) = 2m yy A,3112 + 2n
1ly2 - A2 - Vnellă + >all@l1 + Aelle|11-
(5)
Here, the first two terms are data-fit fit terms, and ||3]11. |ell are the sparsity-promotin terms in the regression vector and corruption vector, respectively weighted by regularization parameters X3 and Xe > Next, we formulate the optimization problem as
(B, = arg min L(B, e).
(6)
BER",eER"
The question remains, under what conditions AR-LASSO is able to estimate 8 with low error? In the next subsection, we discuss the generalized, extended, restricted eigenvalue condition based on which we present theoretical guarantees for AR-LASSO to answer such questions.
3.1 Theoretical Guarantees for AR-LASSO
First, define the following set:
C== (ha, f) (RP x R²) such that || I11 + Al s 3///r]11 3A[sfsli).
(7)
where A dz. It can be shown that the error term (B 3r ē e*) belongs the set C (see the proof of Xg
Theorem 1 in the supplemental material, especially the part from equations (S3) to (S13)). The set C is a natural restriction the error vectors h 3 3² and f = ē e that emerges from the optimization problem in equation 0 Hence expectedly, the theoretical guarantees for AR-LASSO rely the following two key properties of sensing matrix A over the restricted set C:
(1) Generalized, extended, restricted eigenvalue condition (GEREC): We say that the mea- surement matrix A obeys the gencralized, extended, restricted cigenvalue condition on the restricted set C if there exists h > 0 such that the following holds:
he + 11 < N |
T Iffl A (h.f)EC. N
(8)
The GEREC essentially stating that the sum of the squared magnitudes of the vectors Ah. and f is lower-bounded by constant factor times ||ll2 + |! for any (h, E C. Recall that n < N. The above condition is a generalization of the extended, restricted eigenvalue condition studied in Nguyen & Tran (2012), to the scenario where some of the correspondences give more context, we use the above condition with (h, == (Ø - --, -- e-) for thcoretical analysis of AR-LASSO. Essentially, f plays the role of error in estimation of the permutation corruption vector x := P24.3" A2.3*. Note the difference between GEREC and the extended, restricted eigenvalue condition Nguyen Tran (2012). In Nguyen & Tran (2012), the authors assume that cach of the N measurements can undergo gross corruption and the aim is to lower-bound the term ( |h]/ [[
known, that is when < N. To
where A Nxp, h RRP and f R.N (see comment 3(a) after Lemma in Nguyen & Tran (2022)) On
5

---

Published in Transactions on Machine Learning Research (MM/YYYY)
the other hand, we have assumed knowlodge of m correspondences, and hence, we only concerned with permutation errors in the remaining = N m measurements. Due to this, we have f E R as opposed to f E RN as in Nguyen & Tran (2012). Alternatively, our f can be thought of as an N-dimensional vector whose top m entries are zero. When none of the correspondences are known, that is, when m = 0, n = N, the generalized, extended, restricted eigenvalue condition reduces to the exlended, restricted eigenvalue condition defined in Nguyen & Tran 2012
(2) Mutual incoherence condition (Mic) Nguuyn & Tran 2012 We require that there exists
km > 0 such that
1 (Azh, f)l S km (1hll2 + (1f12)2 v (h EC.
(9)
We refer to km > 0 as the mutual incoherence constant. The mutual incoherence condition allows decoupling the two error terms || - -3112 and l/ - ea given that we use f) := (3 8", ē e²) for theoretical analysis of AR-LASsO. Also, the mutual coherence condition states that the column vectors of A are sufficiently dissimilar compared to columns of the identity matrix. This ensures that there is clear separation between the signal vectors 8 and e* during compressive recovery.
Next, the question arises: Under what conditions does measurement matrix obey GEREC and MIC? It can be shown that the family of Gaussian sensing matrices satisfies GEREC with suitable assumptions on (N, m, 8, k). To this end, we state the following lemma (proof in supplemental material):
Lemma 1 CeaaaaiGGennnn (Generalized, extended, restricted eigenvalue condition). Consider the Gaussian sens- ing matrir A NN whose rous are i.i.d. E). We have the set C == {(h. E (R" x TR)) such that |hyell Allfgell S 3/|brl1a + fxllfslli with [T] = k and |S| = as defined earlier.
Select X
= x=
E(E) k logp, then E(EE logp' where p E (0,1) is constant. If S 01 7e Tog and N C2 Craia(E)
logn
N
the following inequality holds with probability at least C2 exp N): min
(mum(E) 128
8N (1 1
1/ AhIB + I (I E C, where 0ı, C2 c3 C4 are positive constants.
We make the following observations: (i) We reiterate that the knowledge of correspondences requires to only consider f E I² opposed to considering f E BNN As a result, the sensing matrix A obeys GEREC with a larger tolerance on s, that is, s S plg
C1 p= p= (N-m) As m increases, a larger mumber of permutations can be tolerated. (Hi) In the absence of known correspondences, that is, when n N, the requirement becomes s S C1 pa N which is consistent with that obtained in Lemma 1 of Nguyen & Tran 2012). (Mii) The choice of follows from Theorem 1 in the next section.
N
N
Moreover, Nguyen & Tran (0122) prove that the family of Gaussian sensing matrices also satisfies the mutual incoherence condition, again with some suitable assumptions on (n, k). For the sake of completeness, we state the following lemma:
Lemma 2 (Mutual incoherence condition (Nguyen & Tran, 2012)): ). Consider the Gaussian sens- ing matria Ag E gaxp whose rows are i.idd. NO,, We have the set C = f(h,f) E (R" x TR2) such that ||yyalli + f lli S 33lhrll + 3XIfflll1 +
with [T|= k and |S| = s defined eartier. Select
5(>) Alogp Cmac (L) A PV Top) where p (0,1) is constant. Assume that s min Can(22) p² log CB Craz (2)
logn
and n 2 coE(E)
Com k llogp for some sufficiently small positive constant and sufficiently large con- (E)
stant Co. then the following inequality holds with probubility greater than 1 - exp (-c7)): (A,h, f < km (|1l) () E C, where c7, km are positive constants. We refer to km as the mutual incokerence constant.
We pick the above lemma from Nguyen & Tran 2012 with a slight change in the expression for X to suit our problem. Note that the expression for X naturally follows from the theoretical analysis of AR-LASSO (see Theorem Consequently, to obey the mutual incoherence condition, the requirement on s gets relaxed, As increases, more permutations can be tolerated.
that is, N {(2) &logg N ((2) & logg,
Cmn( log N-m Caua (Σ) Flog
6

---

Published in Transactions on Machine Learning Research (MM/YYYY)
For consistency check, setting m 0 gives the same upper limit as obtained in Lemma 2 in Nguyen & Tran (2012).
Now, since we have established that the family of Gaussian sensing matrices obey GEREC and MIC with a high probability, we move on to state the theoretical guarantees for AR-LASSO. Given the optimization problem equation 6 we present an upper bound on the estimation error || theorem:
1 8 + ||ē - e Il2 in the following
Theorem 1. Consider the optimization problem in equation 6 and the observation model in equation 7
under the assumplions (C1)-(C4)- Select X3 = 2 11A7 urll and de = N | Assume that 8
2/m
N
N min (A, (1 n Cma((2) 2) pa log C5 Craca (2)) and that N 2 C2
E(E) & klogg,
Cum( logp, n 2 coE(Z)
((E)
Caurt (E) k klogr CaalE)
that A2 satisfies MIC with sufficiently small mutual incoherence constant kim such that kim
min
Cminn))
32 and A satisfies GEREC with constant ke O. Then there exists positive constant
512
ky such that the following inequality holds with probability greater than -2/p 2/n2
33 l|ē c'1l2 S 6or, max (
E E
(E))koop
logp
slog
(10)
N
N
N
A few insights on the thcorem are in order:
1. In the noiseless scenario (a 0), the error term turns out to be zero. And hence, exact recovery of e0* is possible with high probability, In the case of noisy measurements, note that the estimation error scales linearly with the measurement noise standard deviation σ.
2. For fixed p, m and n, the error term scales max( Vk, v8), Le. sparser 8 and e* yield more accurate reconstructions.
3. As pointed out carlier, the m known correspondences allow A to obey GEREC and MIC with higher tolerance on s. These are sufficient conditions for error bounds for AR-LASSO in Theorem to hold. Moreover, note that the term v a sog in equation 10 decreases as more correspondences N N
are known. The higher the value of m for a fixed or a fixed N, the lower is the estimation error.
4. P a positive constant that controls the sparsity level in the regression vector and sparse error vector. If there are large number of permutations expected, then larger value of p should be used for specifying Äg and vico-versa.
5. The choice of X in Lemma and Lemma 2 follows from the expressions for A3 and de in Theorem From the Gaussian concentration results, we know that [ S (EVEE log with probability at least 1 2/p and ||wa]| < 2o 2ollo with probability at least 1- 2/n. Plugging the expressions in À Ag/de gives us X = PV logp'
logn
On the other hand, Nguyen & Tran (2012)
selects PV
log N which same when we put m = in our expression for A. log?
When no correspondences are known in advance, that is, m = 0 and n N, we get the same error bound as obtained in Corollary in Nguyen & Tran (2012).
Our approach casts unlabeled sensing with sparse permutations in a structured sparsity framework. This theorem presents performance bounds for it. The particular form of structured sparsity consid- ered here is different from forms such as trec-structured and block-structured sparsity as analyzed in previous works like Baraniuk el al. (2010).
8. If m is large enough that the matrix A₂ obeys the restricted eigenvalue condition, then we may not even require the permuted measurements, iee. we can consider N = In such case, the problem just reduces to simple LASSO and the error bound would be as follows:
||3 B O(a Soloo/llog logg//m)
(11)

---

Published in Transactions on Machine Learning Research (MM/YYY)
Algorithm Augmented Hard-Thresholdingg Pursuit
Input: Measurement vector y, augmented matrix H, sparsity level l and number of permutations (both
l and can be estimated via cross-validation see Sec. 5 under 'Choice of parameters')
Parameter: Learning rate 1
Output: Estimate of 3
1: (0))) = 0, = 0.
while not converged do ((+1) (0 1H (H=l") (Ha(1)
g(++)) (indices of largest entries of (1=1(1 p)} U (indices of largest entries of ((+)(pp (p
p+n)}
5:
x(++))=
arg min =E (mpoot(a)
Hæ - vll
1=1+1
7: end while
8: return (000 (1:
Sensing matrices randomly generated by Rademacher or Gaussian distributions would need to con- tain at least Ok l) rows order to recover k-sparse vectors in successfully. Then the error bounds in Theorem ! will reduce the LASSO bounds in equation [1 since N m. However such large will generally not be available in applications. Tf is smaller than O log p); then successful recovery will not be achievable, and hence using the sparsely permuted measurements will be inevitable.
4 Augmented Hard- Thresholngg Pursuit
Note that under assumptions (C1)-(C4), y can be re-written as
AA
0 0mxa
y == Hæ + w, where H ==
A2
I Iaxa
is the augmented matrix and x² [w] wp]] T the problem of estimation of x" be posed as
[ 2T Recalling the notation
354 and
arg min ly Hælla s.l. |181|o S k, 3=11=11o <
(12)
== [ 2T/TT SER² #ER"
using modified form of the hard thresholding pursuil approach Foucart 2011 to suit the specific sparsity structure of our problem. The complete procedure is presented in Alg, I to this approach as Augmented Hard Thresholding Pursuit or A-HTP, as it involves sparse recovery of an unknown vector (that x here) using the augmented matrix H. In Alg. [ we note the following: (f) Line 3 is a standard gradient descent step where μ the specified learning rate; (Mi) Line determines the support of / by selecting the indices corresponding to the largest absolute-value entries in æ(1 p), and the support of by selecting the indices corresponding to the largest absolute-valus entries in x(p 1 : +)). The two support sets are combined to obtain the support set of æ; (ii) Line 5 is the debiasing step, and it re-estimates a over the support obtained in the previous step. This step involves computing the Moore- Penrose pseudo inverse of a submatrix of H containing all and only those columns appearing at indices in g(++1), This step is computationally less expensive than the fi-nor optimization step required in Peng et al. (2021p. Morcover, [Png et al. (2021) employs the subgradient method in their algorithm where the function value may even increase, whereas our А-HTP gradient-descent based method. In the next subsection, provide theoretical convergence analysis for A-HrP.
We solve equation 12
We refer
8

---

Published in Transactions on Machine Learning Research (MM/YYY)
4.1 Convergence Analysis for A-HTP
In the compressed sensing framework, a condition for an accurale recovery of the unknown vector is typically based on the restricted isometry property (RIP) of the measurement matrix (Candes & Tao 2005). A-HTP is inherently a compressed sensing algorithm. In this subsection, we state thcoretical guarantee on the recovery of x* via A-HTP using some form of the restricted isometry constant (RIC) of the augmented measurement matrix H. First, we recall the definition of RTC of matrix. A matrix E Rxx said to satisfy the RIP of order t if there exists constant E (0, 1) such that
(13) holds for every t-sparse y E 12. The smallest constant & for which this holds is called the order-t RIC of the matrix A. In other words, the application of A on any t-sparse vector approximately preserves the vector's norm.
(1 - loll - Ay 2 S (1 6
Interestingly, in our problem, there is some structure in the distribution of non-zero entries in x", that is, || pollo I & and ||= (p + 1: :.:p n)llo I s. To exploit this structured sparsity, we characterizo a notion of structureedsparrsity, restricted isometric property (SS-RIP) in the following definition.
Definition 1. We say that the matrie H obeys the structured-sparsity, restrieted isometric properly (SS- RIP) of order [(p, k), (n. s)] if there erists restricted isometry constant 8 858
(p..k) E (0, 1) such that
(1 61-l) & Aggl S (1 + 11
(14)
holds for every g RR+* with llg(1: p)llo S k and (p 1: 1::ppp n) S.
With this, we state geometric convergence result on A-HTP:
Theorem 2. Consider the Gaussian sensing matria A whose entries are i.i.d. N 1/N). Suppose that 858 (n.3)) of the augmented measurement matriz H satisfies 558
(p.3k). S 1 v3'
Then the sequence x(t)
defined by A-HTP satisfies the following inequality v it 0:
||x(1)) x0112 S 10)) 201 ll2 +
|00
(15)
21
558 (p.2k), (m,,s)
+ / + 588
2855
((,,)),(n,s))
(n.33)
where T
and w denotes the ((p.2)) (n,
1
88
8SS
(t.2a)
measurement noise vector from equation
The proof of the above theorem follows along the lines of the work in Foucart 2011 Theorem 3.8). The following lemma (proved in the supplemental material) outlines under what scenarios the augmented matrix H satisfies the critcrion 655 (1.33) S V3*
Lemma 3. Consider the Gaussian sensing matrices A E mm and A E Raxp with i.i.d. NN 1/N)
entries. There erist positive constants cs, Cy such that the augmented matrir H [A 0mxn satisfies the
A2 Inxn
struclured-spane sparssslyy restricted isometry properly (SS-RIP) of order [(p,k) (n, provided that ls log (p/k) + log (n/s) S cgN, with probability at least 1 - 3 exp (-cgN). The constants cs, co depend the RIC 8. Equivalently, we have the following result for all æ E R with ||æ[1 p)llo I k and | n)llo s s:
P (1110))
H
< (1 11) 2 1 -3exp (-cyN).
(16)
Remarks on Theorem 2 and Lemma
As expected, the error bound (spocifically, the second term) in Theorem 2 increases with the noise standard deviation. As y 1, the first term of the bound decreases with the number of iterations,
ie.. t.
9

---

Published in Transactions on Machine Learning Research (MM/YYYY)
2. From Lemma 3 we require that N 2 Clklog (p/3k) + log (n/3s)) for H to obey SS-RIP of order (p,, (k), (n, 3s) J. And hence, from Theorem 2 it follows that N 2 C(k log (p/3k) + s log (n/3s)) is sufficient for an accurate recovery of x² via A-HTP.
3. Since N-m, m, the requirement N > C(k log (p/3k) + log (n/3s)) relaxes more correspondences are known.
4. In the scenario n 0, that is, when all the correspondences are known, the problem simplifies to the standard compressed sensing problem. Consequently, require N 2 Clklog (p/3k)) mcasurements for an accurate recovery of 8", which is consistent with the well-known requirement for compressed sensing via HTP.
Comparison with the standard RIP condition. Note that if we do not exploit the specific sparsity structure in x², condition on accurate recovery of x* via A-HIP is that the matrix H should satisfy RIP of order 3(k + s) Foucart (2011). which requires N 2 C(k + s) log (p + n3/(3k + s)). On the other hand, by exploiting the sparsity structure x², we demonstrate that 2 C(k log (p/3k) + 8 log (n/3s)) is sufficient for an accurate recovery of x" via our A-HTP algorithm. This is less than C(k + s) log [p + (3((((k + s)]].
5 Numerical Experiments
In order to assess the impact made by knowledge of known correspondences, we compare AR-LASSO from equation 0 and A-HTP from Alg. I to the following estimators, none of which use the prior information of known correspondences.
(1) The robust LASSO (R-LAssO) estimator given by argmin 1 lly - A------ /nellž + Assl + Aelle|l. 2N BEBreeRR" which is effectively AR-LASSO with m 0 and N =n.
(di) The f-norm hard thresholding pursuit approach in Peng et al. 2021 that minimizes w.r.t. B E IRP such that || S k. We refer to this approach as HTHHP.
I1y- - AB81I
(mi) The L - l estimator motivated from Candes & Tao 2005 Candes et al. 2005 that is posed
arg min ABI|1 + \د 1 BerP
(iv) The sparse Bayesian learning approach (SBL) approach Wipf & Rao (2004), which an expectation- maximization (EM) based Bayesian method for compressod sensing. This algorithm has been shown to outperform several other non-learning based compressed sensing algorithms in Marques et al. (2018), and hence not been used in the literature in the context of unlabeled sensing, to our best knowledge. In this method, given knowledge of Gaussian noise in we model the following probabilities, taking into account the definition of H and x* from Sec.
it in this paper to estimate both 3 and e*. Note that. this approach has
p(ya=*)= exp 11 H 122/ (20²))
(17)
σN (2T) N/2
Vj E (n p): exp
(18)
/2ma,
where the latter is a Gaussian prior on the elements of xt with unknown variances {az) pttp that are inferred on the fly from y, H. The details of the EM algorithm to jointly infer the signal vectors and their unknown element-wise variances, via maximizing the posterior probability p(** can be found in Wipf & Rao (2004).
We refer to our algorithm A-HTP henceforth as HTP distinguish it from HTP. We use CVXPY (Diamond & Boyd, 2016) solve all the optimization problems, except for SEL which is implemented via FMM Also, note that by definition of the concept of permutation, have zero-sum constraint (referred to
10

---

Published in Transactions on Machine Learning Research (MM/YYYY)
as ZSC henceforth) on given by Σi=1 e; = It is worth investigating whether this information helps to improve the estimate of f To this end, we incorporate this additional hard constraint in the AR-LASSO and R-LASSO estimators, yielding two additional variants.
Data generation: In all the experiments, the entries of A and the non-zero values of 3 are sampled from (( 1). P2 is generated by randomly sampling from the family of 8-sparse permutation matrices. The entries of w are independently sampled from (V o²) where a := f,x the mean absolute value of the entries of the noiscless measurement vector PA8 with fraction fr E (0, 1).
Choice of parameters: The regularization parameters As and de in AR-LASSO, R-LAssO, LASSO and 11 algorithms are chosen through cross-validation on a held-out set of measurements. The unknown e are reconstructed using (say) 95% of the available measurements (in a set R) using different values of (Ag, de) from a set A. Let the signal reconstruction using regularization parameters (21,2) E A be called ,2; ,22- For each such estimate, the validation error E(1,12) is computed over the remaining 5% of the measurements forming a set V. Here VE(H, == Evev (w: A dr ). Note that the set V contains only those measurements with known correspondences. The parameters 4 which yield the least validation error are then selected. After this, the vectors (8", ee") are re-estimated using all measurements using the selected (2) as regularization parameters. This technique is very effective because the validation error acts as a data-driven proxy for the immeasurable mean-squared error (MSE) as shown via confidence intervals in Zhang et al. (2014): Chetverikov et al. (202I). Note that our cross-validation approach does not require any prior "training phase' on a class of similar signals to determine the optimal hyperparameters. Moreover Fig. f() demonstrates that the RRMSE values remain stable over a decent range of values of (Ap,Ae) as compared to those chosen by cross-validation.
vectors f e*
Also note that HTH and Hz-HTP require the knowledge of (k, s), which are typically unknown in practice but can be chosen via cross-validation. In our experiments, we observe that cross-validation overestimates (k, s) by a factor of 2. Hence, we directly set (k, to twice of their true value in the 4-HTP and 4--HTP algorithms. We select the learning rate in 4-HHTP and 42-HTP through cross-validation. The number of iterations in H-HFT is set to 200, and that 4--HrP is set to 100. We always observed convergence within these iteration counts.
Evaluation metric: The evaluation metric used for all simulations is the relative root mean squared error [18-8"11a where 3 is an estimate of 3r. We report the RRMSE averaged over 50 randomly chosen (RRMSE) || la instances of P2, with each permutation instance averaged over 50 random instances of measurement noise W.
Results: In Fig. [a), we have plotted the RRMSE as a function of the number of measurements N for p == 240, k 14, m 32, s 16, and 2% noise (i.e. f. = 0.02). We note that the approaches AR-LASSO and bg-HTP, which utilize the information of known correspondences, result in lower errors. 42-HTP results in the least errors, followed by AR-LASSO. l l clearly produces much higher errors. Incorporation of ZSC in AR-LAASSO and R-TASSO only marginally improves the estimate of B². As N increases, H- starts performing better than AR-LASSO, indicating diminishing utility of known correspondences at a sufficiently large N.
In Fig. 2 histograms of the RRMSE values are displayed for Hi-HTP and HrP Note that the estimation error depends on the specific (randomly chosen) instance of P2. We observe that 4-TH results in large errors many times. Moreover, we note that by using known correspondences in 42HHTP, the variance of the RRMSE distribution significantly decreases for given N. This is particularly prominent given fewer measurements, as seen in the case of N E (80, 90).
In Fig. 3 we display the scatter plot of the errors obtained on the randomly chosen permutation matrices averaged over 50 random noise instances as a function of ||e*|] for AR-LaSSO and R-LASSo. Observe that for N = 100, the term 1|y: A in AR-LASSO ensures that the errors do not depend much on the permutation error magnitude ||e* 111 On the other hand, without the information of known correspondences in R-LASSO, the scatter plot shows a clear positive correlation with ||e*|] This correlation however, dies down as we get more measurements, seen in the case N 120.
11

---

Published in Transactions on Machine Learning Research (MM MYYY)
Relabve ROOIIERATIIO CTror
Salntive westtttuutenn
AN-LASSO without 25C
B-LASSO 250C
AR-LASSO with 25C
ARLAASSO without ZSC
ARIAASOO with ESC
ARCLASSO WEROUE ZSC
RA 25C
AR AR-LASSO Wibh ZSC
L34
SBL
L2HTP
L2-HTP
SBL
11-11
SBL
12-HTP
540
Number of messurements
Number messurements
Percentage of messuummeett nobe
Rebotive reconstruction arcyr
17
AlB-ASSO without
LE
R-LASSO with ZSC
Robbbie recin COOO CNO
R LASSO without 25C
L1-ITP
AR-LASSO with
L2 HTP
AR-LASSO WENOUEZ5C
LI-11
BAASSO with 2512
RASSO without 25C
LI-HTP
03-
6/-
01-
(4)
Figure 1: A comparison of the algorithms for unlabeled compressive sensing problem: The error plots as function of (a) the number of measurements N for = 240, k = 14, m = 32, = 16, fr = 0.02; (b) the number of measurements N in very high dimensions, iec. p = 1200, = 70, = 60, = 80, fr = 0.02 (the errors with & - & are much higher than for other estimators, and are not shown here) (c) the noise level in
terms of fr for p = 240, N 110, 14, m 32, s 16: (d) the permutation level for p p= 240, N 90, 14, m 32, fr 0.02; and (e) the sparsity level for p 240, . 110, m 32, 16, fr 0.02. These plots show that using known correspondences as in H2-HTP and AR-LASSO, results in lower reconstruction error. In plots (b), (c) and (e), the errors for some pairs of algorilhms nearly overlap: AR-LASSO with and without the ZSC, R-LASSO with and without the ZSC, L2-HTP and SBL. Plot (f) shows that the RRMSE is not significantly impacted by varying λe, Àg over a decent range of values as compared to the values chosen by vrlsavvali (see dark regions of the sub-figure).
N 80
90
2500
LI-HTP
2500
LI-HTP
12-HTP
2000
Fequency
requeency
1500
1500
1000
500
500
80 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.9
80 0.1 0.7 0.3 0.4 0.5 0.8 1.0
Relative monnstruccionn error
Relative meanstaictoon erfor
Figure 2: Distribution of the relative root mean squared error (RRMSE) values obtained using 41HHTP and 42HTPP for different instances of permutation matrix and measurement noise for N - 80 (left) and N 90 (right) measurements. Utilizing the prior known correspondences (as done by E2-HTP results in much lower standard deviation of the errors.
12

---

Published in Transactions on Machine Learning Research
N 100
N 120
1.0
1.0
AR-LASSO with ZSC
AR-LASSO with ZSC
Relative rec reconstruction error
Relative reconstruction error
R-LASSO with ZSC
R-LASSO with Z5C
0.6
0.6
0.4
0.4
0.2
0.2
0.0
40
60
80
100
120
140
0.0
60
80
100
120
140
||e|||
||e|||
Figure 3: Scatter plots of RRMSE and permutation error magnitude ||e* for N 100 (left) and 120 (right) measurements. For N 100, note the strong correlation of the estimation error with ||e*|| when known correspondences are not utilized in R-LASSO.
In Fig. [b), we compare the algorithms for different N higher dimensions, that is, for p = 1200, 70, m 60, 80, and 2% measurement noise (i.e. fr 0.02).
Next, in Fig. c), compare the algorithms for different noise levels (i.e., different values of fr) for p 240, N = 110, k 14, = 32, and 16. We observe that for the LASSO-based approaches and 4--HTP, the estimation error scales linearly with as we expect from the upper bounds in Theorem [ and Theorem 2
In Fig. dd), we show errors for different permutation levels for = 240, = 90, = 14, m = 32 and 2% measurement noise. Recall that the error upper bound for AR-LASSO scales as vs. We note that the algorithms that utilize known correspondences are more robust in terms of the number of permutations in the measurements.
In Fig, e(e,, show errors for different sparsity levels for p 240, N 110, 32, 16 and 2% measurement noise. During data generation for this experiment, we maintain that 48 S ||e* < 52 for all the 50 permutation instances, so that the results reflect the effect of changing sparsity level only. Note that the reconstruction error greatly depends on the permutation error ||e*|[.-
The plots demonstrate that though SBI. has shown excellent empirical performance in compressed sensing (Marques al.) 2018),, it generally did not outperform AR-LASSO or AR-HTP for the unlabeled compressed sensing problem. A possible reason for this could be the assumption of zero-mean Gaussian priors on the elements of both 8 and e*, even though the elements of e* can attain significantly large values.
Performance of SBL:
Performance of the 4 - l estimator: In the results in Fig. I we notice that the 4--4 algorithm performs significantly worse than other methods. This is because, uses an & data fidelity term which assumes a Laplacian distribution on the noise y. However the noise in y contains a Gaussian component and the component e* due to permutations. The & fidelity term ignores the Gaussian distribution of w. Moreover, e* does not necessarily follow the Laplacian distribution. The AR-LASSO or R- estimators use the Gaussian distribution of the noise w and instead apply an & permutation error e* It is important to note that the error bounds for LASSO and AR-LASSO do not require that ex follows a Laplacian distribution.
penalty on the
Use of only permutation-free measurements: Another natural bascline is a technique that uses only the m permutation-fre measurements for the sparse regression. This baseline is nothing but the regular LASSO and typically requires to be Oll Having such large number of permutation-free measurements
13

---

Published in Transactions on Machine Learning Research (MM/YYY)
112358
112358
112358 112358
112358 112358
Figure 4: Row Two refracted versions (left) and R (right) generated synthetically by warping reference image 7 using a displacement vector field created using sparse random lincar combination of 2D-DCT basis vectors. Row The reconstruction of R using R-LASSo, i.e. RR-LASSO (left.) and the overlap between I and RR-LASSO (right). Row 3: The reconstruction of R using AR-LASSO, i.e. RAR-LASSO (left) and the overlap between R and RAR-LASSO (right). Notice the significantly better overlap for AR-LASSO than for R-LASSO. For casier visualization, we highlight the regions of inaccurate overlap between R and RI-LASSO (row 2, right) and the more accurate overlap between R and RAR-LASSO (row 3, right), using black boxes. The convention followed for display overlaps is described under 'Visualization Results' Sec. 5.1
may however be unrealistie. Our experimental results show that the RRMSE values with such a baseline can more than 0.7 for small m, and hence are not included here.
Average compute time values of our algorithms for unlabeled compressive sensing with known correspon- dences presented in the supplemental material.
14

---

Published in Transactions on Machine Learning Research (MM/YYYY)
5.1 Application of Unlabeled Compressive Sensing in Image Registration
Consider a scene submerged under a wavy waler surface when imaged using camera. in air. The images of such a scene contains distinct non-rigid deformations when compared to an image Z of the same scene if the scene were located in air. Consider two such refracted images denoted by I and R, corresponding to different positions of the wavy water surface. It is known that the deformation vector field between images and R can be expressed as sparse linear combination of the 2D discrete cosine transform (DCT) basis vectors (see James et al. (2019); Wulff & Black] (2015)). Let both I and R be of size h1 x h2- Define u1 Ra and U2 E RA1a to be the vectorized displacement fields from I to R in the horizontal and vertical directions respectively. Let B E Baihaxhaha denote the 2D DCT matrix. Then, we can represent the displacement fields as follows:
U1 = B0,, u2 = B02.
(19)
where 0,,02 E TRA are unknown sparse coefficient vectors. In a similar work, Sresth et al. (2024) assumes that the displacement vector field is band-limited, that is, they assume that B consists of only some d < h2 low-frequency 2D DCT basis column vectors. This assumption may not always hold and hence in our work, the matrix B consists of all h2 2D DCT basis vectors, and accordingly, (01, 02) are sparse vectors whose support is not restricted to just the low-frequency 2D DCT coefficients.
Obtaining the displacement vector fields from observed images is a difficult problem. Conventional optical flow algorithms do not leverage the property of bandlimiteduess or sparsity of the unknown U1 U2 in the 2D DCT basis. However, we can obtain the displacement vector information at a subset of pixcls H in I uusing salient feature point matching techniques such as SIFT (scale invariant feature transform) (Lowe 2004)
Harris corner detectors Harris & Stephens [1988) or SURF (speeded up robust features) Bay et al. (2006)
11 Given corresponding point pairs {PI,, (PI,,.PRRA)) k=1 in images and R, the displacement at the 1tth point can be computed as (Wis; u2x)) == PR.* - PI,K- Note that each Pr, and PR.k is a 2D vector. The topic of salient feature point matching is well researched in the computer vision literature, and so such point pairs provide useful information. Given this set H. we have U1HH = Bx01, U22 = Bx02. Here, Bx E the rows from B corresponding to only those pixel locations which belong to H. and U1 U2 R are sub-vectors of u1, U2 respectively containing displacement values only from locations in H. The task now is to estimate 0,, 02 given H and U1 U2 It is clear that this is a compressive sensing problem. However it is also an unlabeled compressive sensing problem, because it is well known that salient feature point matching algorithms can produce a small number of erroneous point matches, especially if the images contain self-similarity. That is, if the images contain structurally similar patches in different locations, then some points from one region can be erroneously matched to those in other regions because the point matching techniques leverage mostly local information. Hence, we can write the following:
R Bill contains
U1 = Bx0 + 8, + 77, U2 Bx02 + 82 7/2,7.
(20)
where 71H E RIH) 72.H E R(H] represent small errors in the point coordinates modeled as zero-mean Gaussian random variables with small variance, and 81 E RIHI, 82 E R represent sparse vectors whose non-zero elements represents the permutation errors. Furthermore, in motion estimation problems such as the one under consideration, we can also use a small number of expert (accurate) point-pair annotations as side information. Let us denote this set of accurate point-pair matches by S. Using notation similar to that in equation 20 we have:
u1,5 BsQ1 + 11 U2,5 B502 + 1725--
(21)
Note that there are no terms for permutation errors in equation 21 as these are expert annotations.
Motion Estimator: Considering both equation 21 and equation 20 we have an AR-LASSO based estimator
which minimizes the following cost functions with respect to (01, 8,) and (02, 82) respectively:
(0,, : |1,H - Bx0, 01 + || - 0s 11 + A 0 ||| + Aa 11,11
(22)
Jz(02, 52) := || Bx02 82112 ||u,s Bs02112 + A 1 l12 + > 62111,
(23)
where \1 0, A2 > 0 are regularization parameters. Given 02 and 02. the displacement vector fields can be obtained using equation 19 and then applied to / in order to align it with R.
15

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Experiment: Consider two grayscale images I and R. from row of Fig. respectively. The image I was chosen arbitrarily as the reference image. Image R was generated synthetically by warping I using a displacement vector field that was sparse in the 2D-DCT basis (for both X and Y components of the motion) following the model in equation 19 To obtain ,1, 0₂ and thus determinc the motion from to R, we obtain a set H of n = 452 salient, feature poinl-pairs in the images and R by combining the oulputs of SIFT (Lowe, 2004), SURF (Bay al., 2006) and Harris descriptors (Harris & Stephens] 1988). Furthermore, we accurately annotate a set S of m 18 corresponding point-pairs in the images / and R. The correspondences of the m point-pairs in S are known accurately, whereas small number of correspondences in the point-paite in H may be incorrect due to errors in point matching algorithms. For example, the different grid corners from the two images (where vertical and horizontal lines of the grid intersect) in row of Fig. can be incorrectly matched with each other, as point matching algorithms rely on local similarity feat ures. Note that the indices of the erroneous point-pairs in H are unknown. We can use the AR-LASSO algorithm to estimate 01, O2 given H, S and thus reconstruct by warping the image using displacement fields u1 == B01. U2 == B02. To show the utility of m known correspondences, we also perform the reconstruction of R using 02 obtained from R-LASSO. We refer to the reconstructions of R using AR-LASSO and R-LASSO as LASSO and RR-LASSO respectively.
Visualization of Results: We display the reference image I, its underwater refraction R, the reconstruc- tions of R, i.c. LASSO and Lasso,,, and the overlap between R and their reconstructions (i.e., RAR-LASSO and R in Fig, [ To display the overlap between two images R and its estimate RAR-LASSO: we create a color (RGB) image, and set the Red channel to R. the Green channel to RAa-LASSO and the Blue channel to all zeros. Tf the images R and LAs-L are well aligned, the resulting RGB image will appear mostly gray. In casc, there is misalignment, the RGB image will show green magenta shades in different places. Simi- larly, the overlap between R and PR-LASS is also displayed. Clearly, the overlap between I and RAR-LASso is more accurate than that between R and RR-LASSO as evidenced by the larger proportion of green or magenta regions in the latter (eg: clephant's ' head). Note that RA-LOS also looks noisy. The relative reconstruction error of the reconstructed image R using AR-LASSO is 0.141 while that using R-LASSO 0.167. The relative reconstruction error of the displacement field (u, u2) using AR-LASSO is 0.243 while that using R-LAASO is 0.343.
These results show proof of concept of the utility of AR-LASSO in image alignment.
6 Conclusion
We studied the problem of unlabeled compressive sensing with the assumption that the regression vector is sparse and given additional knowledge of few correspondences. We proposed a tractable Lasso-based estimator and derived thcoretical performance bounds for our algorithm. We also presented another estimator based on a modified form of Hard Thresholding Pursuit, with theoretical analysis. We verified the theoretical findings through mumerical experiments. We compared our algorithm with hard thresholding approach and an l norm formulation and demonstrated that our algorithm outperforms them. Additionally, we illustrated that having information about a small number of accurate correspondences reduces the sensitivity of estimation error on the severity of permutation corruption. Lastly, we demonstrated a practical application of our framework in image registration.
References
Richard G Baraniuk, Volkan Cevher, Marco F Duarte, and Chinmay Hegde. Model-based compressive sensing. IEEE Transactions Information Theory, 56(4):1982-200) 20009 2010.
Herbert Bay, Tinne Tuytelaars, and Lue Van Gool. Surf: Speeded up robust features. In IEEE/CVF Int. Conf. Comput. Vis., pp. 404-417, 2006. ISBN 978-3-540-83833-8.
E.J. Candes and T. Tao. Decoding by linear programming. JEEE Trans. Inf. Theory, 51((2):4203 4215, 2005. doi: 10.1109/TITT 85879.
16

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Emmanuel Candes, Mark Rudelson, Terence Tao, and Roman Vershynin. Error correction via linear program- ming- In 46th Annual TEFE Symposium on Foundalions of Computer Science (FOCS'03) pp. 668-666888 681. LEEE, 2005.
Denis Chetverikov, Zhipeng Liao, and Victor Chernozhukov. On valss-aalidated lasso in high dimensions. The Annals of Statistics, 19(33:1300-3117, 2021.
Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimiza- tion. J. Mach. Learn. Res., 17(83):1-5, 2016.
Simon Foucart. Hard thresholding pursuit: An algorithm for compressive sensing. STAM Numer. Anal., 49(6))2543 2563, 2011. doi: (0.1137/1008062))
Deguang Han, Fusheng Lv, and Wenchang Sun. Recovery of signals from unordered partial frame coefficients. Appl. Comput. Harmon. Anal., 44(1):38 58, 2018. ISSN 1063-5203. doi: https://doi.org// 10. 1o..1016/j..aalee 2016.04.002.
Chris Harris and Mike Stephens. A combined corner and edge detector. In Alvey vision conference, volume 15, pp. 10 (0-5244, 1988.
Daniel J Hsu, Kevin Shi, and Xiaorui Sun. Linear regression without correspondence. In Adv. Newral Inf. Process. Syst., volume 30. Curran Associates, Tnc., 2017.
Jerin Geo James, Pranay Agrawal, and Ajil. Rajwade. Restoration of non-rigidly distorted underwater images using combination of compressive sensing and local polynomial image representations. In IEEE/CE /CVF Int. Conf. Comput. Vis., 2019.
P. Lahiri and Michael D. Larsen. Regression analysis with linked data. J. Am. Stat. Assoc., 100(469): 222-230, 2005. ISSN 01621459.
Feiran Li, Kent Fujiwara, Fumio Okura, and Yasuyuki Matsushita. Generalized shuffled linear regression. In IEEE/CVP Int. Conf. Comput. Vis., pp. 6454 6463, 2021. doi: N0.1109/ICCV44892.22 2001222022000000
David G Lowe, Distinctive image features from scale-invariant keypoints. Int. J. Comput. Vis., 60:91 110, 2004.
Elaine Crespo Marques, Nilson Maciel, Lirida Naviner, Hao Cai, and Jun Yang. A review of sparse recovery algorithms. IEEE access, 7:1300-1322, 2018
Manuel Marques, Marko Stošić, and João Costcira. Subspace matching: Unique solution to point matching with geometric constraints. IEEE/CVF Inl. Conf. Comput. Vis., pp. 1288 1294, 2009. doi: 10.1109/ ICCV 24599145
Arvind Narayanan and Vitaly Shmatikov. Robust de-anonymization of large sparse datasets. Tn IEFE Symp. Secur. Priv., pp. 111-1111101111 125, 2008. doi: 10.1109/SPP.008...
Nam H Nguyen and Trac D Tran. Robust LASSO with missing and grossly corrupted observations. IEEE Trans. Inf. Theory, 59(4):2036-2) 2058, 2012.
Jun-Jun Pan and Yan-Ning Zhang. A new point matching method based on position similarity. In Tnt. Conf.
Mach. Learn. Cybern., pp. 5154-5158 Vol. 8, 2005. doi:
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. doi: 10.1109 TIT 2017.2776217.
Liangzu Peng and Manolis C. Tsakiris. Linear regression without correspondences via concave minimization. IEEE Signal Process. Lett., 27:1580- 1584, 2020. doi: 1111009/LSPP2022.301990
Liangzu Peng, Boshi Wang, and Manolis Tsakiiis. Homomorphic sensing: Sparsity and noise. In Int. Conf. Mach. Learn., volume 139 of Proc. Mach. Learn. Res,, pp. 0664-8475. PML.R 2021.
17

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Martin Slawski and Emanuel Ben- Linear regression with sparsely permuted data. Electron. J. Stat., 13(1):1 36, 2019. doi: 10.1214/18-FJ81499.
Garweet Sresth, Ajit Rajwade, and Satish Mulleti. Unlabelled sensing with priors: Algorithm and bounds. Tn IEEE Tnl. Conf. Acoust. Speech Signal Process., pp- 9551-9555, 2024. doi: 10.109//CAASP4445552222 10445886.
Sebastian Thrun and John J. Leonard. Simultaneous Localization and Mapping, pp. 871 889. Springer Berlin Heidelberg, 2008. ISBN 978-3-540-30301-5 doi: 1110077977-3-550-0000---- 38.
Manolis Tsakiris and Liangzu Peng. Homomorphic sensing. In Kamalika Chaudhuri and Ruslan Salakhut- dinov (eds.); Inl. Conf. Mach. Learn., volume 97, pp. 6335 6344. PMLR, 09 15 Jun 2019.
Jayakrishnan Unnikrishnan, Sacid Haghighatshoar, and Martin Vetterli. Unlabeled sensing with random linear measurements. IEEE Trans. Inf. Theory, 64(5):3237-322) 3253, 2018. doi: 10. 10.1109/TIT 20.110/TTT.2018.2805 2018.28090022
D. Wipf and B. D. Rao. Sparse bayesian learning for basis selection. IEEE Trans. Signal Process., 52(8): 2153 2164, 2004.
Jonas Wulff and Michael J. Black. Efficient sparse-to-dense optical flow estimation using a learned basis and layers. In JEEE Comput. Soc. Conf. Comput. Vis. Pattern Recognit,, pp. 120-130-300 2015. doi: 10.1109/ CVPR.2015.729861
Jinye Zhang, Laming Chen, Petros T Boufounos, and Yuantao Gu. On the thcoretical analysis of cross validation in compressive sensing. In 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3370 3374. IEEE, 2014.
A Appendix
Please refer to supplemental material for additional experiments and the proofs lemmas and theorems.
18


Reviews:
[{"review_id": "z3sb6K3xHe", "reviewer": "Reviewer_HVAM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n* Clear problem setting and problem statement\n\n* Earlier literature on unlabeled compressed sensing has been reviewed\n\nWeakness\n* The organization of the paper can be improved. It took me a lot of time to get what \"n\" is the third contribution item on page 3  before reading on and finding the definition of n later in that section.\n\n* I am slightly confused by the bound in contribution item #3 on page 3. N is lower bounded by C log(n) and n = N -m. Is that correct. It would be great to have a table of notation and state which veriable is constant and which variable is growing with what rate. \n\n* The paper talks about image registration as an application but needs to provide complete empirical evidence in the main text. I suggest bringing those results from the appendix to the main text and expanding on it. \n\n* Figure 2 seems to miss the left panel and is incomplete\n\n* Overall, the contribution of the paper is limited given the body of the work done in the area of shuffled regression and unlabelled compressed sensing", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the compressed sensing problem under the assumption that labels are partially shuffled. The problem has been extensively studied in both overparametrized settings and underparametrized settings. The innovation here is considering a middle ground where some labels are aligned. The paper's main result is the sample complexity of the proposed hard thresholding algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In addition to the changes requested in the previous section:\n\n* In the introduction, please clarify the contribution of the Suresh et al. 2024 paper and how this paper improves them.\n* Focus on three key applications of unlabeled CS and demonstrate performance against benchmarks stated in the introduction\n* In the contribution section, summarize the contribution of the proof techniques used.", "broader_impact_concerns": "No concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "48o8xOOmao", "reviewer": "Reviewer_s3kr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1- The paper proposes practical algorithms with theoretical guarantees for cases where some correspondences between measurements and the rows of the sensing matrix are known, which is critical in certain applications.\n\n2- The paper includes a comprehensive literature review of related works and effectively positions its contributions within the existing body of knowledge.\n\nWeaknesses:\n\n1- The experiments are limited, as the effects of varying sparsity parameters and the dimensions of the sensing matrix have not been thoroughly evaluated. Additionally, the practical example provided is insufficiently detailed. More extensive results are needed to fully understand the behavior of the proposed algorithms across different dimensions, particularly in highly underdetermined cases.\n\n2- While numerous powerful compressive sensing algorithms exist for this well-established problem, these algorithms are missing from the experimental comparisons. This omission makes it difficult to accurately assess the significance of the proposed methods.\n\n3- The discussion of results is insufficient. For example, there is no explanation for why the performance of the L1-L1 algorithm is significantly worse than others.\n\n4- The proposed algorithms involve several important hyperparameters, but no computationally efficient or robust method is provided for tuning them apart from standard cross-validation. Furthermore, the sensitivity of the algorithms to these hyperparameters has not been investigated.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the problem of unlabelled compressive sensing, which involves estimating an unknown sparse vector from underdetermined linear measurements where the correspondence between some measurements and the rows of the sensing matrix is unknown. Two optimization approaches are proposed to estimate the sparse vector: the first adapts the LASSO problem to incorporate known correspondences, while the second employs a hard-thresholding pursuit method. Theoretical guarantees are provided for both algorithms. Through simulations, the proposed methods demonstrate superior performance compared to previous algorithms and highlight the advantage of leveraging known correspondences.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I suggest that the authors provide a more comprehensive set of experiments, including comparisons with state-of-the-art compressive sensing algorithms and evaluations on more practical applications. Additionally, the performance of the proposed methods should be tested across different dimensionalities and sparsity levels to better understand their behavior in various scenarios.\n\nIt would also be beneficial to include a computational comparison of the proposed algorithms against other methods to highlight their efficiency.\n\nFinally, Figure 1 in the Supplementary Material is difficult to interpret. I recommend improving the caption for clarity or adding direct labels to each image for better readability.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "FoCOkDmGMo", "reviewer": "Reviewer_9Gpt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The paper is easy to follow, and the writing is clear;\n- Related works are clearly explained. E.g., the comparison and relation to prior work (Nguyen & Tran 2012) are discussed in detail;\n- The paper has solid contributions that cover theory, algorithms, and applications.\n\nWeaknesses:\n- While the paper provides wide coverage, the technical contributions are a little bit incremental, as the results appear to be natural extensions of prior works.\n- The style and technical presentation could be improved (see \"Requested Changes\").\n- Compared to prior works, and my knowledge, the paper introduces an unconventional assumption (C3), which requires $m$ correspondences given. While the justification is that in some image applications, there could be a few hand-calibrated correspondences available, I personally find this assumption needs more interrogations from both theoretical and empirical perspectives. Specifically,  consider the formulation/algorithm: minimize the $\\ell\\_1$ norm of $\\beta$ subject to the constraints $A\\_1 \\beta=y_1$ (or formulate it as a LASSO problem). The rationale is that, if $m$ is large enough, then we could potentially recover $\\beta^*$ just from the $m$ correspondences (and if so, we could ignore the potentially permuted measurements). This leads to two questions:\n    - In theory, I would assume recovery guarantees would exist for this baseline. The paper should compare Theorem 1 with this guarantee, as this would give us an idea about the usefulness of learning from permuted measurements. We would expect that Theorem 1 would indeed be better, as the extreme case $m=0$ suggests this baseline would fail.\n    - For experiments, this baseline could have been included in the comparison. This is a different one, compared to R-LASSO.\n\nQuestions:\n- is there a typo in the definition of the R-LASSO baseline? That is, should $e$ be an optimization variable as well? Should it be $A\\_2$ and $y\\_2$?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the problem of unlabelled compressed sensing, where the correspondences between the measurements and the rows of the sensing matrix are unknown, and the number of measurements is smaller than the variable dimension. While the problem is difficult, it is made tractable via a few assumptions. The assumptions are that the ground truth vector is sparse and that some correspondences are given. Under these assumptions, the paper makes several contributions:\n- it formulates a LASSO-type robust recovery problem and provides recovery guarantees (Theorem 1);\n- it proposes an algorithm based on hard-thresholding pursuit and proves its convergence (Theorem 2);\n- it has experimental validations on synthetic data and for image registration (in the appendix).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Besides the baseline mentioned above, here are a few suggestions on style and technical presentation:\n\nSome citations hurt the readability of the corresponding sentences. For example, in the first page, it was written:\n> *Unnikrishnan et al. Unnikrishnan et al. (2018) and Han et al. Han et al. (2018) state that ...*\n\nThis is not readable, as the author names are repeated. I would recommend using \\citet and \\citep rather than \\cite, and use the common practice for in-text citations, see, e.g.,:\n> https://tex.stackexchange.com/questions/480040/citation-for-an-addendum-in-brackets-citet-vs-citep \n> https://blog.apastyle.org/apastyle/2011/01/writing-in-text-citations-in-apa-style.html\n\nSimilarly, \n\n- The definition of set $C$ at the beginning of Section 3.1 should have an independent equation number, so that in latter lemmas it can be referenced. Currently, the definitions are repeating.\n- To make the paper more readable and friendly to novice readers, the definition of a mathematical notation should be followed by a sentence that explains it in words. This is currently missing in many definitions:\n    - the set $C$\n    - the GEREC condition (it should have an independent equation number)\n    - the mutual coherence condition (it should have an independent equation number)\n- Please unify the use of *generalized* (*generalization*) and *generalised* (*generalisation).\n- The first sentence of Theorem 1, shown below is not readable, as it writes Eq. 5 rather than (5), and it is not comfortable to read * the optimization problem Eq. 5*\n> *Consider the optimization problem Eq. 5 and the observation model Eq. 1 under the assumptions (C1)-(C4).*\n- In Line 4 of Algorithm 1, $k$ and $s$ are not in math fonts. Also, in many places, $\\max$ and $\\min$ are not in math fonts. \n- The explanation of Algorithm 1 could be made better. Specifically, the texts should explain the algorithm line by line, rather than step by step (the step number in use does not match the line number).\n- In Definition 1, the phrases *for every $(k+s)$-sparse $g$* could be removed as the latter conditions on its $\\ell\\_0$ norm makes sure that $g$ is $(k+s)$-sparse\n- In equations (8) and (9), the commas are unnecessary and they actually interrupt the flow.\n- Equation (11) should be rearranged as it is too long.\n- The name *RRMSE* is weird, as MSE typically represents *mean squared error*, while the actual definition is not the $\\ell\\_2$ norm squared.\n\nWhat is $w$ in equation (10)? Did I miss its definition? Some discussion on the error term of equation (10) is needed, as the algorithm might not converge if the error term is too large.", "broader_impact_concerns": "I do not see any concerns on the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Apologies for the unusual reviewing cycle.  The authors have now provided a revision, and 2 of 3 reviewers are happy with that (the 3rd reviewer did not respond). The authors did a good job engaging in the rebuttal and making changes. I think the review process has done its job and improved the paper.

Thus I'm happy to recommend acceptance. However, reviewer `s3kr` mentions a few new minor comments (see the bottom of their original thread) that should be addressed before the final camera-ready version.
Decision: Accept (poster)