Multiple Support Recovery Using Very Few Measurements Per Sample

We study the problem of multiple support recovery from linear measurements, where a set of samples  are observed through random linear measurements. Each sample has a support that is drawn from a small unknown set of allowed supports. Our goal is to recover the underlying supports in the absence of knowledge of support labels. We design a two-step procedure that first estimates the union of the underlying supports, and then uses a spectral algorithm to estimate the individual supports. We characterize the resulting trade-off between the two resources of interest—the number of samples and the number of measurements per sample. A key observation that we use in designing our algorithm is that the linear measurements preserve pairwise affinities between coordinates of the samples, and one can therefore use techniques like spectral clustering to partition the coordinates into different supports.

This work was one of the recipients of the Jack Keil Wolf student paper award at ISIT 2021.

References

Lekshmi Ramesh, Chandra R. Murthy, and Himanshu Tyagi, “Multiple Support Recovery Using Very Few Measurements Per Sample”, IEEE International Symposium on Information Theory (ISIT), Melbourne, Jul. 2021.

Lekshmi Ramesh, Chandra R. Murthy, and Himanshu Tyagi, “Multiple Support Recovery Using Very Few Measurements Per Sample”, https://arxiv.org/abs/ 2105.09855 [cs.IT], May 2021.