Source-linked AI summary
Group-Sparse Signal Denoising: Non-Convex Regularization, Convex Optimization
Po-Yu Chen, Ivan W. Selesnick
TL;DR
The paper addresses estimating sparse signals from noisy observations by combining non-convex regularization with a convex total cost function. It formulates group-sparse denoising this way, develops an efficient OGS algorithm, and reports improvements over prior convex regularization with favorable speech-enhancement results.
Problem
The paper addresses estimating a vector x from an observation y and seeks stronger sparsity promotion than convex regularization without abandoning convex optimization.
Method
The method formulates group-sparse denoising with a non-convex, overlapping-group regularizer while constraining parameters so the total cost function is strictly convex, then minimizes it using a majorization-minimization algorithm.
Results
The proposed approach substantially improves upon the earlier convex-regularized OGS method and demonstrates effectiveness for speech enhancement.
Takeaways & Limitations
The approach combines stronger sparsity promotion with a unique minimizer, decreasing-cost iterations, and O(N) computational cost per iteration.
Takeaways & Limitations
Convergence of OGS to the minimizer of F is not proved because of the singularity issue, although each iteration is guaranteed to decrease the cost function.
Abstract
from arXiv · showhide
Convex optimization with sparsity-promoting convex regularization is a standard approach for estimating sparse signals in noise. In order to promote sparsity more strongly than convex regularization, it is also standard practice to employ non-convex optimization. In this paper, we take a third approach. We utilize a non-convex regularization term chosen such that the total cost function (consisting of data consistency and regularization terms) is convex. Therefore, sparsity is more strongly promoted than in the standard convex formulation, but without sacrificing the attractive aspects of convex optimization (unique minimum, robust algorithms, etc.). We use this idea to improve the recently developed 'overlapping group shrinkage' (OGS) algorithm for the denoising of group-sparse signals. The algorithm is applied to the problem of speech enhancement with favorable results in terms of both SNR and perceptual quality.
I. INTRODUCTION
The paper estimates group-sparse signals from noisy observations using a non-convex penalty balanced with data consistency so the total cost remains strictly convex. This preserves convex optimization benefits while promoting sparsity more strongly, and supports an efficient overlapping-group method.
- Problem: The problem is to estimate a group-sparse vector x from an observation y corrupted by additive white Gaussian noise.Large values tend to form clusters, while group locations and boundaries are unknown.
- Motivation: Convex formulations offer robust optimization theory and convergence guarantees, whereas non-convex formulations generally produce sparser solutions but may have local minima and initialization issues.Non-convex solutions can also be discontinuous functions of the input data.
- Approach: The paper balances a non-convex penalty against the data-consistency term so the total cost function is strictly convex.This approach retains a unique minimizer while using a penalty that promotes sparsity more strongly than convex regularizers.
- Method: The proposed overlapping-group method uses fully overlapping groups, making it translation invariant and avoiding auxiliary variables used in some overlapping-group approaches.Auxiliary-variable methods increase memory usage and data indexing in proportion to group size.
- Method: The algorithm is computationally efficient at O(N) per iteration, monotonically decreases the cost function, and requires no step-size or Lagrange algorithmic parameters.The method is derived using majorization-minimization.
- Result: The authors report that the proposed approach substantially improves upon their earlier method using only convex regularization.The method is applied to group-sparse denoising, including speech-related signals.
B. Penalty Functions
The paper uses parameterized, non-convex penalty functions that satisfy structural assumptions designed for sparsity promotion and thresholding. Their resulting threshold functions can reduce bias relative to soft thresholding while preserving threshold behavior.
- The penalty functions are continuous, symmetric, increasing on positive inputs, concave there, and maximally concave at zero with unit slope.
- The penalties are parameterized by a scalar a > 0, with logarithmic, arctangent, and rational examples approaching the absolute value function as a → 0.The rational penalty permits a = 0, whereas the logarithmic and arctangent penalties require a > 0.
- The ℓp pseudo-norm for 0 < p < 1 fails these assumptions because it lacks unit slope at zero and cannot be normalized or scaled to obtain it.
- The threshold functions derived from the penalties retain thresholding behavior, while the three non-convex functions approach the identity rather than applying the constant shrinkage of soft thresholding.Soft thresholding's constant reduction of large values causes systematic underestimation, whereas asymptotically unbiased thresholds are often preferred.
- For λ = 4 and a = 0.2, the logarithmic, arctangent, and rational threshold functions all satisfy θ′(λ+) = 5 but approach the identity at different rates.The arctangent threshold approaches the identity fastest among the shown functions.
III. OGS WITH NON-CONVEX REGULARIZATION
The proposed OGS formulation uses a non-convex sparsity penalty while restricting its parameter so the total group-sparse denoising cost remains strictly convex. This yields a unique minimizer with structured thresholding properties and requires group-size knowledge.
- The denoising cost combines squared data error with a non-convex sparsity-promoting penalty applied to overlapping group norms.
- The group size K should match the size of clusters in the data, so selecting it requires prior knowledge that may involve trial and error.
- The analysis asks which values of a make F strictly convex and how to compute its unique minimizer efficiently.
- When K = 1, variables decouple and minimization reduces to component-wise nonlinear thresholding, which does not promote group structure.
- Under strict convexity, the minimizer preserves the sign of each observation, zeros coordinates where y is zero, and does not exceed its coordinatewise magnitude.
A. Group Thresholding
The single-group analysis reduces multivariate convexity to a scalar condition and defines a group threshold at norm λ. This provides the basis for non-convex multivariate shrinkage with reduced bias for large components.
- The single-group cost H is strictly convex exactly when the corresponding scalar cost G is strictly convex.
- The convexity condition requires the positive quadratic curvature to dominate the penalty's negative second derivative: 1 + λφ′′(v; a) > 0 for v > 0.
- For the logarithmic, arctangent, and rational penalties, explicit parameter intervals are obtained that ensure strict convexity of H.
- The multivariate threshold function maps inputs with ∥y∥2 < λ to the unique zero-vector minimizer, making λ its threshold.The subgradient argument also shows that inputs with norm greater than λ do not have zero as the minimizer.
- With strictly concave penalties, the induced threshold function approaches the identity for large inputs, producing less bias than soft thresholding.
B. Overlapping Group Thresholding
The paper derives conditions under which a non-convex penalty yields a strictly convex total cost, enabling stronger group-sparsity promotion while preserving convex optimization. It also discusses parameter selection and how larger groups affect the regularizer.
- The proposed non-convex regularization strongly promotes group sparsity while preserving strict convexity of the total cost function F.
- F is strictly convex under a condition on the penalty parameter a, including explicit conditions for the φlog, φatan, and φrat penalties.
- The suggested parameter workflow chooses K from signal structure, sets a as a fraction of its maximum, and then selects λ according to noise variance.
- For larger K, a smaller λ is needed for fixed noise suppression, while greater group overlap can make regularization more sensitive to a.
C. Minimization Algorithm
The minimization algorithm uses majorization-minimization to replace the strictly convex objective with simpler quadratic subproblems. The resulting OGS updates are efficient and monotonically decrease cost, but singularities require careful initialization and finite-precision handling.
- Majorization-minimization replaces the minimization of F with a sequence of simpler problems based on a majorizer Q.
- The majorizer makes the components uncoupled and quadratic, so each update is readily computed using quantities obtained by double K-point convolution.
- The resulting OGS algorithm monotonically decreases the cost function and has computationally efficient updates.
- The quadratic majorizer is undefined at v = 0, creating a potential divide-by-zero singularity that initialization and exclusion rules address.
- Convergence to the minimizer of F is not proved because of the singularity issue, although cost decrease is guaranteed and rapid convergence is observed in practice.
- The penalty affects the OGS iteration through the function φ′(u)/u, whose similar forms reveal relationships among the listed penalties.
D. The Multidimensional Case
The one-dimensional OGS formulation extends directly to multidimensional signals by replacing groups and summations with their multidimensional counterparts. The paper applies the two-dimensional version to noisy speech spectrograms.
- The OGS formulation extends straightforwardly to multidimensional signals, including two-dimensional arrays and groups.
- The numerical experiments use the two-dimensional algorithm to denoise time-frequency spectrograms of noisy speech waveforms.
- In two dimensions, the objective and convexity conditions use double summations, while the algorithm remains essentially unchanged.
E. Regularization Parameter Selection
The paper presents noise-based and SURE-based strategies for selecting the regularization parameter λ. Precomputed tables and interpolation support rapid selection under AWGN, while MC-SURE closely tracks true MSE for OGS.
- λ can be selected from the AWGN standard deviation by empirically measuring OGS noise suppression for combinations of λ, K, and penalty.
- Precomputed tables and interpolation provide fast λ selection for supported penalty functions, parameters, complex data, and AWGN settings.
- With K = 5, the atan penalty, and 25 iterations, λ = 1.2σ reduces the noise standard deviation to 10−4σ.
- MC-SURE estimates MSE from the observation, noise variance, and estimator divergence, using Monte-Carlo methods when direct divergence computation is intractable.
- For OGS, MC-SURE closely follows true MSE, indicating that the estimator is close to continuous and bounded.
IV. EXPERIMENTAL RESULTS
The experiments evaluate non-convex regularized OGS for one-dimensional group-sparse denoising and speech enhancement. OGS[atan] generally improves SNR while preserving perceptual quality, with group-size choice creating an SNR–perception trade-off.
- Experimental setup: OGS[atan] uses the arctangent penalty with its largest convexity-preserving parameter, while speech enhancement applies the two-dimensional OGS algorithm to STFT coefficients.The speech experiments use 25 OGS iterations and evaluate multiple speakers, sentences, noise levels, and sampling rates.
- Example 1: One-dimensional signal denoising: OGS[atan] substantially outperforms convex OGS[abs] in one-dimensional denoising, with higher SNR and almost no visible residual noise.It also achieves higher SNR than hard thresholding in the reported comparison.
- Example 1: One-dimensional signal denoising: OGS[atan] better preserves nonzero amplitudes and thresholds small values than OGS[abs], yielding essentially zero error for 50% of signal values.The comparison also reports much less denoising error for OGS[atan].
- Example 2: Speech denoising: Group size (2, 4) suppresses inter-formant noise more completely, whereas (8, 2) recovers some spectrogram regions more accurately and gives better perceptual quality.Although (2, 4) is SNR-optimal for the female speaker, the evaluation uses (8, 2) because of its superior perceptual quality.
- Example 2: Speech denoising: OGS[atan] achieves the highest SNR across the evaluated genders, sampling rates, and input noise levels.The reported comparisons use a larger noise-suppression λ rather than an SNR-optimized value, prioritizing perceptual quality.
- Example 2: Speech denoising: EWP improves SNR for all methods but least for OGS[atan], whose SNR remains highest with or without EWP.Listening tests report that EWP has an almost imperceptible effect on OGS[atan]'s already good perceptual quality.
V. REMARKS
The remarks relate the proposed method to prior OGS work, speech-enhancement comparisons, and proximity-operator methods. They identify broader inverse problems as an avenue for future investigation.
- Relationship to prior OGS work: The non-convex regularized OGS algorithm shares convergence behavior, implementation issues, computational complexity, and FOCUSS relationships with prior convex regularized OGS.The paper refers readers to the earlier OGS work for these aspects.
- Speech-enhancement comparison: The speech-enhancement comparison includes algorithms evaluated with and without empirical Wiener post-processing, with sentences ordered by OGS[atan] SNR.The figure compares individual SNRs for 30 male sentences at 10 dB input SNR.
- Proximal-framework relation: The proposed algorithm resembles a proximity operator but uses a non-convex penalty, placing it outside the standard proximal framework described in the paper.The paper proposes exploring proximal-like techniques for more general inverse problems such as deconvolution.
VI. CONCLUSION
The paper formulates group-sparse denoising as convex optimization with a non-convex overlapping-group regularizer. Parameter constraints preserve strict convexity while numerical experiments support speech-enhancement effectiveness.
- Conclusion: The proposed regularizer uses overlapping groups and is concave on the positive real line, promoting group sparsity more strongly than convex regularizers.The paper considers several parameterized non-convex penalties.
- Conclusion: Constraining the penalty parameter preserves strict convexity of the optimization problem, while numerical experiments demonstrate effectiveness for speech enhancement.The conclusion links the convex formulation and non-convex regularization to the reported application results.
APPENDIX
The appendix supplies convexity criteria based on monotone derivatives. A continuous function with positive curvature away from zero and an upward derivative jump at zero is strictly convex.
- Convexity criteria: A continuous function with an increasing right- or left-derivative on an open interval is convex there.The theorem provides the derivative-based criterion used in the appendix.
- Convexity criteria: Strict convexity follows when the relevant derivative is monotonically increasing.The appendix states this as the strict version of the derivative criterion.
- Corollary: If G is continuous, has G′′(x) > 0 away from zero, and satisfies G′(0−) < G′(0+), then G is strictly convex on R.The condition combines positive curvature on each side with a derivative jump at zero.
- Proof: The proof establishes monotonicity of the right derivative separately on each side of zero and across the derivative jump.This verifies the theorem's strict-convexity condition for G.