2013/06/18 by Akshay Soni, Soni, Akshay, Jarvis Haupt +1
Computer Science · Engineering · #Distributed Sensor Networks and Detection Algorithms #Electrical and Bioimpedance Tomography #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.1306.4391
openalex publication_date 2013/06/18 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
Recent breakthrough results in compressive sensing (CS) have established that\nmany high dimensional signals can be accurately recovered from a relatively\nsmall number of non-adaptive linear observations, provided that the signals\npossess a sparse representation in some basis. Subsequent efforts have shown\nthat the performance of CS can be improved by exploiting additional structure\nin the locations of the nonzero signal coefficients during inference, or by\nutilizing some form of data-dependent adaptive measurement focusing during the\nsensing process. To our knowledge, our own previous work was the first to\nestablish the potential benefits that can be achieved when fusing the notions\nof adaptive sensing and structured sparsity -- that work examined the task of\nsupport recovery from noisy linear measurements, and established that an\nadaptive sensing strategy specifically tailored to signals that are tree-sparse\ncan significantly outperform adaptive and non-adaptive sensing strategies that\nare agnostic to the underlying structure. In this work we establish fundamental\nperformance limits for the task of support recovery of tree-sparse signals from\nnoisy measurements, in settings where measurements may be obtained either\nnon-adaptively (using a randomized Gaussian measurement strategy motivated by\ninitial CS investigations) or by any adaptive sensing strategy. Our main\nresults here imply that the adaptive tree sensing procedure analyzed in our\nprevious work is nearly optimal, in the sense that no other sensing and\nestimation strategy can perform fundamentally better for identifying the\nsupport of tree-sparse signals.\n