Phase Transition for Support Recovery from Gaussian Linear Measurements

01/30/2021
by   Lekshmi Ramesh, et al.
0

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≥ 2log d. Along with the lower bound from our previous work, this shows a sharp 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≪ k regime, multiple measurements from the same sample are more valuable than measurements from different samples.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset