On the Fundamental Limits of Recovering Tree Sparse Vectors From Noisy Linear Measurements

DOI10.1109/TIT.2013.2287496MaRDI QIDQ5346147zbMATH OpenOpenAlexFDO

Authors Akshay Soni, Jarvis D. Haupt

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.4391

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Recent breakthrough results in compressive sensing (CS) have established that many high dimensional signals can be accurately recovered from a relatively small number of non-adaptive linear observations, provided that the signals possess a sparse representation in some basis. Subsequent efforts have shown that the performance of CS can be improved by exploiting additional structure in the locations of the nonzero signal coefficients during inference, or by utilizing some form of data-dependent adaptive measurement focusing during the sensing process. To our knowledge, our own previous work was the first to establish the potential benefits that can be achieved when fusing the notions of adaptive sensing and structured sparsity -- that work examined the task of support recovery from noisy linear measurements, and established that an adaptive sensing strategy specifically tailored to signals that are tree-sparse can significantly outperform adaptive and non-adaptive sensing strategies that are agnostic to the underlying structure. In this work we establish fundamental performance limits for the task of support recovery of tree-sparse signals from noisy measurements, in settings where measurements may be obtained either non-adaptively (using a randomized Gaussian measurement strategy motivated by initial CS investigations) or by any adaptive sensing strategy. Our main results here imply that the adaptive tree sensing procedure analyzed in our previous work is nearly optimal, in the sense that no other sensing and estimation strategy can perform fundamentally better for identifying the support of tree-sparse signals.

Recommendations

• On exact recovery of sparse vectors from linear measurements
• Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting
• Lower bounds for sparse recovery
• Recovery of Exact Sparse Representations in the Presence of Bounded Noise
• Quantitative Recovery Conditions for Tree-Based Compressed Sensing
• Computable Performance Bounds on Sparse Recovery
• Reconstruction of sparse vectors in white Gaussian noise
• Recovery of sparse integer vectors from linear measurements
• Typical \(l_1\)-recovery limit of sparse vectors represented by concatenations of random orthogonal matrices
• Information-Theoretic Limits on Sparse Signal Recovery: Dense versus Sparse Measurement Matrices

This page was built for publication: On the Fundamental Limits of Recovering Tree Sparse Vectors From Noisy Linear Measurements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5346147)