Ada-JSR: SAMPLE EFFICIENT ADAPTIVE JOINT SUPPORT RECOVERY FROM EXTREMELY COMPRESSED MEASUREMENT VECTORS

This paper considers the problem of recovering the joint support (of size K) of a set of unknown sparse vectors in R^d, each of which can be sensed using a different measurement matrix. Such models have wide applicability ranging from communication to multi-task learning. We develop an adaptive strategy called Adaptive Joint Support Recovery (Ada-JSR) that enables exact support recovery in the extreme compression regime with only m=1 measurement per unknown vector while requiring a total complexity of no more than K log_2(d) measurements. Unlike existing support recovery techniques which require suitable assumptions on the correlation structure or distribution of the unknown signals in order to operate in the regime m