Effective Sparsity: A Unified Framework via Normalized Entropy and the Effective Number of Nonzeros
Haoyu He [email protected], Hao Wang [email protected], Jiashan Wang [email protected], Hao Zeng [email protected] · 2026
Read Effective Sparsity: A Unified Framework via Normalized Entropy and the Effective Number of Nonzeros by Haoyu He [email protected], Hao Wang [email protected], Jiashan Wang [email protected], Hao Zeng [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-13826.txt.
Introduction
He and co-authors define a new way to count how sparse a signal really is. Standard counts treat every nonzero entry alike, yet noise leaves long tails of tiny values. Their effective number of nonzeros comes from the Shannon entropy of the normalized magnitudes. It splits into the support size times an efficiency factor. The authors prove a stability bound and build a practical regularizer from the idea. Tests on signal recovery and image denoising show robust, competitive results.
Catalog record
| CREATOR | Haoyu He [email protected], Hao Wang [email protected], Jiashan Wang [email protected], Hao Zeng [email protected] |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69461 |
| LICENSE | http://creativecommons.org/publicdomain/zero/1.0/ |
| RIGHTS | CC0 |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.13826
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Effective Sparsity: A Unified Framework via Normalized Entropy and the Effective Number of Nonzeros Haoyu He [email protected], Hao Wang [email protected], Jiashan Wang [email protected], Hao Zeng [email protected] Abstract Classical sparsity-promoting methods rely on the ℓ 0 \ell_{0} norm, which treats all nonzero components as equally significant. In practical inverse problems, however, solutions often exhibit numerous small-amplitude components that minimally affect reconstruction but lead to an over-estimation of the signal’s complexity. We address this limitation by shifting the paradigm from discrete cardinality to effective sparsity. Central to our approach is the introduction of the effective number of nonzeros (ENZ), a unified class of normalized entropy-based regularizers—including Shannon and Rényi forms—that robustly quantifies the concentration of significant coefficients. We show that while the classical ℓ 0 \ell_{0} norm is brittle, the ENZ provides a stable and continuous measure of effective sparsity that is invariant to negligible perturbations. For noisy linear inverse problems, we establish theoretical guarantees under the Restricted Isometry Property (RIP), proving that ENZ-based recovery is both unique and stable. Furthermore, we derive a fundamental decomposition that identifies the ENZ as a product of the support cardinality and a distributional efficiency term, explicitly bridging entropy with ℓ 0 \ell_{0} regularization. Numerical experiments demonstrate that our effective sparsity framework significantly outperforms traditional cardinality-based methods in both robustness and accuracy. † † firstpage: 1 † † editor: My editor keywords Effective Sparsity, Effective Number of Nonzeros (ENZ), Normalized Entropy, \ell_{0} Minimization, Inverse Problems, Restricted Isometry Property. 1 Introduction Recovering sparse signals from underdetermined linear systems is a cornerstone problem in machine learning, high-dimensional statistics, and signal processing. Consider A{\bm{x}}={\bm{b}}+\boldsymbol{\varepsilon}, (1.1) where A\in\mathbb{R}^{m\times n} is the sensing matrix with m\ll n , {\bm{b}}\in\mathbb{R}^{m} represents the observed data, and \boldsymbol{\varepsilon}\in\mathbb{R}^{m} denotes additive noise. Under the assumption that the true signal {\bm{x}} is sparse, the objective is to recover {\bm{x}} from limited measurements. This paradigm has driven significant advancements across a wide spectrum of applications, from compressed sensing to high-dimensional inference 6 ; 9 ; 15 ; 17 ; 18 ; 35 . However, most classical methods rely on a strict sparsity assumption, utilizing cardinality-based measures like the \ell_{0} norm that treat all nonzero entries as equally important. In practice, signals often exhibit effective sparsity, where the primary information is concentrated on a few dominant coefficients, while a “long tail” of small-amplitude components—often arising from noise or modeling fluctuations—drastically inflates the discrete cardinality without reflecting the signal’s true underlying complexity. Traditionally, sparsity is quantified by the \ell_{0} “norm,” which counts the number of non-zero entries in a vector, leading to the combinatorial optimization problem 6 : \min_{{\bm{x}}}\ \|{\bm{x}}\|_{0}\quad\text{subject to}\quad{A}{\bm{x}}={\bm{b}}. (1.2) However, the \ell_{0} minimization problem is known to be NP-hard and exhibits extreme sensitivity to noise 28 . To bridge the gap between theoretical ideals and computational feasibility, various surrogates have been developed, ranging from the convex \ell_{1} relaxation 3 ; 35 ; 15 ; 10 ; 12 to non-convex penalties such as \ell_{p} ( 0<p<1 ) 14 , \ell_{1}-\ell_{2} 39 , and the scale-invariant \ell_{1}/\ell_{2} ratio 29 ; 38 . While these methods have achieved notable empirical successes, their theoretical guarantees often rely on the Restricted Isometry Property (RIP), where recovery conditions remain strictly tied to the literal cardinality of the signal’s support 13 ; 5 . The Practical Mismatch of \ell_{0} Sparsity Despite significant progress in sparse recovery, a fundamental discrepancy persists between \ell_{0} sparsity and the nature of signals encountered in realistic, noisy environments. In practice, solutions to {A}{\bm{x}}={\bm{b}} often contain a long tail of numerically small but non-zero components, stemming from numerical precision limits, modeling inaccuracies, or ambient noise 25 . While these components contribute negligibly to the signal’s energy or physical interpretation, they indiscriminately inflate the \ell_{0} count. This tension is particularly acute in compressed sensing theory. Classical recovery results typically ensure stability under a 2k -Restricted Isometry Property (RIP) condition, provided the signal contains k non-zero entries 9 ; 19 . However, when infinitesimal perturbations are treated as genuine non-zeros, the apparent sparsity level k can increase dramatically, forcing the RIP to hold at much higher orders. This leads to a theoretical paradox: the theoretical analysis imposes unnecessarily stringent measurement requirements primarily to capture negligible components, even when the meaningful structure of the signal remains unchanged. Consequently, theoretical guarantees based on \ell_{0} norm become overly pessimistic, demanding high sampling rates to protect entries that are essentially irrelevant. This observation suggests that cardinality alone is not the appropriate notion of sparsity in noisy inverse problems. Effective Sparsity and Effective Non-zeros Building on these limitations, we argue that a robust measure should capture effective sparsity—the number of components that meaningfully influence the signal’s structure 21 ; 31 . Entropy, a fundamental concept in information theory, provides a natural and principled framework for this task 33 ; 16 ; 23 . Unlike cardinality, which is a binary property of the support, entropy-based measures reflect the continuous distribution of energy: low entropy corresponds to signals dominated by a few significant components, whereas high entropy indicates diffuse or noise-dominated structures. In contrast to traditional magnitude-based penalties, we propose characterizing signal complexity in terms of the effective number of nonzeros (ENZ). The ENZ is an entropy-induced metric that prioritizes components which meaningfully contribute to the signal’s mass, rather than those that are merely non-zero in a literal sense. This robustness is essential in practical inverse problems, where numerical noise and modeling errors are unavoidable. By bridging entropy regularization with traditional sparse models, we clarify how distributional concentration serves as a stable proxy for cardinality. Contribution In this paper, we revisit sparse signal recovery by shifting the perspective from discrete support cardinality to effective sparsity. We argue that in practical, noisy environments, the conventional \ell_{0} norm serves as an overly pessimistic metric, as it fails to distinguish between primary signal components and negligible perturbations. To address this, we propose an entropy-based view of sparsity, encompassing Shannon and Rényi 33 ; 30 . By treating sparsity as a property of informational concentration rather than magnitude shrinkage, our framework introduces the ENZ—a robust metric that characterizes the informative core of a signal. Through a fundamental decomposition theorem and RIP-based stability analysis, we provide both the geometric intuition and the theoretical rigor necessary to bridge the gap between information theory and high-dimensional recovery. The principal contributions of this work are summarized as follows: • A Robust Measure of Effective Sparsity: We formalize the concept of ENZ to quantify signal complexity. Unlike the brittle \ell_{0} norm, we prove that our entropy-induced metrics are continuous and stable under small-amplitude perturbations, providing a faithful characterization of a signal’s meaningful support. • De-coupled RIP Requirements and Stability: For noisy linear inverse problems, we establish uniqueness and stability guarantees expressed directly in terms of effective sparsity. Our analysis demonstrates that entropy-based formulations yield significantly milder Restricted Isometry Property (RIP) requirements compared to classical \ell_{0} -based results. • A Unified Entropy-Based Sparsity Framework: We introduce a general information-theoretic framework in which sparsity is quantified via entropy of the normalized coefficient magnitudes and enforced through corresponding (un)normalized entropy regularizers. This framework yields both scale-invariant effective sparsity indices (ENZ) and practical regularization functions with a consistent geometric and information-theoretic interpretation. Classical scale-invariant penalties, such as the \ell_{1}/\ell_{2} ratio, appear