On model-based RIP-1 matrices

DOI10.1007/978-3-642-39206-1_48MaRDI QIDQ5326592zbMATH OpenOpenAlexFDO

Authors Ilya Razenshteyn, Piotr Indyk

Publication date 6 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: The Restricted Isometry Property (RIP) is a fundamental property of a matrix enabling sparse recovery. Informally, an m x n matrix satisfies RIP of order k in the l_p norm if ||Ax||_p approx ||x||_p for any vector x that is k-sparse, i.e., that has at most k non-zeros. The minimal number of rows m necessary for the property to hold has been extensively investigated, and tight bounds are known. Motivated by signal processing models, a recent work of Baraniuk et al has generalized this notion to the case where the support of x must belong to a given model, i.e., a given family of supports. This more general notion is much less understood, especially for norms other than l_2. In this paper we present tight bounds for the model-based RIP property in the l_1 norm. Our bounds hold for the two most frequently investigated models: tree-sparsity and block-sparsity. We also show implications of our results to sparse recovery problems.

Recommendations

• Restricted isometry property for general p-norms
• Sharp RIP bound for sparse signal and low-rank matrix recovery
• Compressed sensing with restricted isometry property
• Generalized notions of sparsity and restricted isometry property. II: Applications
• The restricted isometry property and its implications for compressed sensing

Cited in

(9)

• Discrete optimization methods for group model selection in compressed sensing
• Sharp RIP bound for sparse signal and low-rank matrix recovery
• Generalized notions of sparsity and restricted isometry property. II: Applications
• Computational complexity of certifying restricted isometry property
• Structured sparsity: discrete and convex approaches
• Generalized notions of sparsity and restricted isometry property. I: A unified framework
• Restricted isometry property for general p-norms
• Model-based sketching and recovery with expanders
• On support sizes of restricted isometry constants

This page was built for publication: On model-based RIP-1 matrices

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