The Effective Number of Nonzeros: Theory and Regularization for Sparse Recovery
Authors: Haoyu He, Hao Wang, Jiashan Wang, Qiankun Shi
Organizations: School of Information Science and Technology, ShanghaiTech University, Shanghai, China · Department of Mathematics, University of Washington, Seattle, WA, USA · School of Computer Science and Engineering, Sun Yat-sen University
Abstract
Classical sparse recovery treats all nonzero entries equally, though numerical noise often creates long tails of negligible coefficients. This paper develops an entropy-based notion of effective sparsity to measure the coefficients carrying significant mass. The central quantity, the effective number of nonzeros (ENZ), is obtained by exponentiating the Shannon entropy of the normalized magnitude distribution. We show that ENZ decomposes exactly into the support cardinality multiplied by a distributional efficiency factor, thereby making precise its relation to the ℓ0 count and explaining how it discounts uninformative coefficients. Furthermore, the Shannon ENZ is embedded into a parallel Rényi family that recovers several scale-invariant sparsity measures, including the ℓ1/ℓ2 ratio, as special cases. We then prove a stability result under a restricted isometry condition, establishing an explicit bound that depends on the tail energy, measurement perturbation, and restricted isometry constant. For computation, a separable unnormalized entropy surrogate is introduced to avoid global coupling. Numerical experiments on sparse signal recovery and gradient-domain image denoising demonstrate that the resulting regularizer is robust, computationally efficient, and competitive with standard sparsity penalties.
We consider the problem of support recovery for sparse binary signals from noisy linear measurements. For sparse Gaussian measurement matrices we identify sufficient conditions on the minimal sample size for maximum-likelihood recovery in the high-SNR regime ds/p→∞, where p denotes the signal dimension, s the number of non-zero components of the signal, and d the expected number of non-zero components per row of measurement. Combined with known lower bounds, this yields an information-theoretic threshold of order slog(p/s)/log(ds/p), making explicit the price of measurement sparsity. In particular, we highlight a regime where the sample-complexity loss from measurement sparsity is logarithmic while the computational gain is nearly linear. Second, we study recovery after sparsifying an originally dense Gaussian design: the observations are generated from the dense design, while estimation uses an independently sparsified design and a rescaled response. In the proportional regime s=αp, d=ψp, we prove that, for every fixed target error level δ and every slack ε>0, a sample size of order p/ψ2 is sufficient for support recovery for arbitrarily small ψ.
We propose a unified fractional regularization framework for sparse signal recovery based on the ℓ1/ℓpq model. This model generalizes several widely used sparsity-promoting regularizers and provides additional flexibility through the parameters p and q. Our main theoretical contribution is the characterization of the equivalence between the first-order stationary points of the ℓ1/ℓpq formulation and the subtractive ℓ1−αℓp model, thereby offering a unified perspective on these nonconvex regularizers. In addition, we establish a new sufficient recovery condition under the Restricted Isometry Property (RIP), which shows that the proposed framework can provide relaxed recovery guarantees and improved robustness. To solve the resulting nonconvex problem, we develop a majorization--minimization (MM) algorithm and prove its convergence by using the Kurdyka--Łojasiewicz (KL) property. Numerical experiments on sparse recovery problems with different sensing matrices and MRI reconstruction demonstrate that the proposed approach outperforms existing methods in recovery accuracy.
Sparse recovery is among the most well-studied problems in learning theory and high-dimensional statistics. In this work, we investigate the statistical and computational landscapes of sparse recovery with ℓ∞ error guarantees. This variant of the problem is motivated by \emph{variable selection} tasks, where the goal is to estimate the support of a k-sparse signal in Rd. Our main contribution is a provable separation between the \emph{oblivious} (for each'') and \emph{adaptive} (for all'') models of ℓ∞ sparse recovery. We show that under an oblivious model, the optimal ℓ∞ error is attainable in near-linear time with ≈klogd samples, whereas in an adaptive model, ≳k2 samples are necessary for any algorithm to achieve this bound. This establishes a surprising contrast with the standard ℓ2 setting, where ≈klogd samples suffice even for adaptive sparse recovery. We conclude with a preliminary examination of a \emph{partially-adaptive} model, where we show nontrivial variable selection guarantees are possible with ≈klogd measurements.