| Paper ID | D4-S2-T3.1 |
| Paper Title |
Phase Transitions for Support Recovery from Gaussian Linear Measurements |
| Authors |
Lekshmi Ramesh, Chandra R. Murthy, Himanshu Tyagi, Indian Institute of Science, Bangalore, India |
| Session |
D4-S2-T3: Phase Transitions in Sparse Recovery |
| Chaired Session: |
Thursday, 15 July, 22:20 - 22:40 |
| Engagement Session: |
Thursday, 15 July, 22:40 - 23:00 |
| Abstract |
We study the problem of recovering the common $k$-sized support of a set of $n$ samples of dimension $d$, using $m$ noisy linear measurements per sample. Most prior work has focused on the case when $m$ exceeds $k$, in which case $n$ of the order $(k/m)\log(d/k)$ is both necessary and sufficient. Thus, in this regime, only the total number of measurements across the samples matter, and there is not much benefit in getting more than $k$ measurements per sample. In the measurement-constrained regime where we have access to fewer than $k$ measurements per sample, we show an upper bound of $O((k^{2}/m^{2})\log d)$ on the sample complexity for successful support recovery when $m\ge 2\log d$. Along with the lower bound from our previous work, this shows a phase transition for the sample complexity of this problem around $k/m=1$. In fact, our proposed algorithm is sample-optimal in both the regimes. It follows that, in the $m\ll k$ regime, multiple measurements from the same sample are more valuable than measurements from different samples.
|
