Perfect Recovery Conditions for Non-negative Sparse Modeling

DOI10.1109/TSP.2016.2613067MaRDI QIDQ4620510zbMATH OpenOpenAlexFDO

Authors Yuki Itoh, Marco F. Duarte, Mario Parente

Publication date 8 February 2019

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: Sparse modeling has been widely and successfully used in many applications such as computer vision, machine learning, and pattern recognition. Accompanied with those applications, significant research has studied the theoretical limits and algorithm design for convex relaxations in sparse modeling. However, theoretical analyses on non-negative versions of sparse modeling are limited in the literature either to a noiseless setting or a scenario with a specific statistical noise model such as Gaussian noise. This paper studies the performance of non-negative sparse modeling in a more general scenario where the observed signals have an unknown arbitrary distortion, especially focusing on non-negativity constrained and L1-penalized least squares, and gives an exact bound for which this problem can recover the correct signal elements. We pose two conditions to guarantee the correct signal recovery: minimum coefficient condition (MCC) and nonlinearity vs. subset coherence condition (NSCC). The former defines the minimum weight for each of the correct atoms present in the signal and the latter defines the tolerable deviation from the linear model relative to the positive subset coherence (PSC), a novel type of "coherence" metric. We provide rigorous performance guarantees based on these conditions and experimentally verify their precise predictive power in a hyperspectral data unmixing application.

Recommendations

• A class of null space conditions for sparse recovery via nonconvex, non-separable minimizations
• Exact Recovery Conditions for Sparse Representations With Partial Support Information
• Sparse Recovery of Nonnegative Signals With Minimal Expansion
• Robust Nonnegative Sparse Recovery and the Nullspace Property of 0/1 Measurements
• Sparse recovery by non-convex optimization - instance optimality
• A necessary and sufficient condition for exact sparse recovery by \(\ell_1\) minimization
• Non-negative least squares for high-dimensional linear models: consistency and sparse recovery without regularization
• Nearly Sharp Sufficient Conditions on Exact Sparsity Pattern Recovery
• Sparse recovery algorithms: sufficient conditions in terms of restricted isometry constants
• Recovery of Exact Sparse Representations in the Presence of Bounded Noise

Cited in

(7)

• High-dimensional sign-constrained feature selection and grouping
• Solving nonnegative sparsity-constrained optimization via DC quadratic-piecewise-linear approximations
• Non-negative least squares for high-dimensional linear models: consistency and sparse recovery without regularization
• Sparse Recovery of Nonnegative Signals With Minimal Expansion
• Solution uniqueness of convex piecewise affine functions based optimization with applications to constrained _1 minimization
• A survey on compressive sensing: classical results and recent advancements
• Matrix-wise _0-constrained sparse nonnegative least squares

This page was built for publication: Perfect Recovery Conditions for Non-negative Sparse Modeling

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