All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD4-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.