Robust Nonnegative Sparse Recovery and the Nullspace Property of 0/1 Measurements

DOI10.1109/TIT.2017.2746620MaRDI QIDQ4566660zbMATH OpenOpenAlexFDO

Authors Richard Kueng, Peter Jung

Publication date 27 June 2018

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

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

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: We investigate recovery of nonnegative vectors from non-adaptive compressive measurements in the presence of noise of unknown power. In the absence of noise, existing results in the literature identify properties of the measurement that assure uniqueness in the non-negative orthant. By linking such uniqueness results to nullspace properties, we deduce uniform and robust compressed sensing guarantees for nonnegative least squares. No l1-regularization is required. As an important proof of principle, we establish that m x n random i.i.d. 0/1-valued Bernoulli matrices obey the required conditions with overwhelming probability provided that m=O(slog(n/s)). We achieve this by establishing the robust nullspace property for random 0/1-matrices - a novel result in its own right. Our analysis is motivated by applications in wireless network activity detection.

Cited in

(13)

• Proof methods for robust low-rank matrix recovery
• Real-valued group testing for quantitative molecular assays
• Stability of 1-bit compressed sensing in sparse data reconstruction
• On a unified view of nullspace-type conditions for recoveries associated with general sparsity structures
• Robustness of Sparse Recovery via <inline-formula> <tex-math notation="LaTeX">$F$ </tex-math></inline-formula>-Minimization: A Topological Viewpoint
• Reconstruction methods in THz single-pixel imaging
• Robust analysis ℓ₁-recovery from Gaussian measurements and total variation minimization
• Perfect Recovery Conditions for Non-negative Sparse Modeling
• Hyperbolic wavelet frames and multiresolution in the weighted Bergman spaces
• Robust sparse recovery with sparse Bernoulli matrices via expanders
• Non-negative sparse recovery at minimal sampling rate
• Random matrices acting on sets: independent columns
• Real versus complex null space properties for sparse vector recovery

This page was built for publication: Robust Nonnegative Sparse Recovery and the Nullspace Property of 0/1 Measurements

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