Source author record

Lekshmi Ramesh

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Information Theory math.IT Machine Learning

Catalog footprint

Research overview

2works

3topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Multiple Support Recovery Using Very Few Measurements Per Sample

In the problem of multiple support recovery, we are given access to linear measurements of multiple sparse samples in $\mathbb{R}^{d}$ . These samples can be partitioned into $\ell$ groups, with samples having the same support belonging to the same group. For a given budget of $m$ measurements per sample, the goal is to recover the $\ell$ underlying supports, in the absence of the knowledge of group labels. We study this problem with a focus on the measurement-constrained regime where $m$ is smaller than the support size $k$ of each sample. We design a two-step procedure that estimates the union of the underlying supports first, and then uses a spectral algorithm to estimate the individual supports. Our proposed estimator can recover the supports with $m<k$ measurements per sample, from $\tilde{O}(k^{4}\ell^{4}/m^{4})$ samples. Our guarantees hold for a general, generative model assumption on the samples and measurement matrices. We also provide results from experiments conducted on synthetic data and on the MNIST dataset.

preprint2020arXiv

Sample-Measurement Tradeoff in Support Recovery under a Subgaussian Prior

Data samples from $\mathbb{R}^{d}$ with a common support of size $k$ are accessed through $m$ random linear projections (measurements) per sample. It is well-known that roughly $k$ measurements from a single sample are sufficient to recover the support. In the multiple sample setting, do $k$ overall measurements still suffice when only $m$ measurements per sample are allowed, with $m<k$ ? We answer this question in the negative by considering a generative model setting with independent samples drawn from a subgaussian prior. We show that $n=Θ((k^2/m^2)\cdot\log k(d-k))$ samples are necessary and sufficient to recover the support exactly. In turn, this shows that when $m<k$ , $k$ overall measurements are insufficient for support recovery; instead we need about $m$ measurements each from $k^{2}/m^2$ samples, i.e., $k^{2}/m$ overall measurements are necessary.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.