Source-linked AI summary
Sparse Regularization via Convex Analysis
Ivan Selesnick
TL;DR
ℓ1-regularized least squares can underestimate high-amplitude components, while non-convex penalties generally sacrifice convexity. This paper introduces a multivariate MC-type penalty built from a generalized Huber function and shows that it preserves convexity while supporting simple proximal optimization.
Problem
ℓ1 regularization promotes sparsity but tends to underestimate high-amplitude components, whereas non-convex regularizers generally make the cost function non-convex with suboptimal local minimizers.
Method
The paper constructs a multivariate generalized MC penalty from a generalized Huber function defined through infimal convolution, with parameters chosen using A to preserve cost convexity.
Results
For arbitrary A, the proposed formulation avoids systematic underestimation of high-amplitude sparse components and has no suboptimal local minimizers because the cost function is convex.
Takeaways & Limitations
The method bridges convex ℓ1 and non-convex sparse regularization while retaining globally convergent, computationally efficient convex optimization algorithms.
Takeaways & Limitations
Direct evaluation of the generalized Huber function requires 3^N simpler functions, making it impractical except for small N; the proposed algorithms avoid explicit evaluation.
Abstract
from arXiv · showhide
Sparse approximate solutions to linear equations are classically obtained via L1 norm regularized least squares, but this method often underestimates the true solution. As an alternative to the L1 norm, this paper proposes a class of non-convex penalty functions that maintain the convexity of the least squares cost function to be minimized, and avoids the systematic underestimation characteristic of L1 norm regularization. The proposed penalty function is a multivariate generalization of the minimax-concave (MC) penalty. It is defined in terms of a new multivariate generalization of the Huber function, which in turn is defined via infimal convolution. The proposed sparse-regularized least squares cost function can be minimized by proximal algorithms comprising simple computations.
1 Introduction
The paper develops non-convex penalties for sparse-regularized least squares that preserve convexity, addressing the amplitude underestimation of ℓ1 regularization. The resulting formulation supports proximal optimization and applies to arbitrary linear operators A.
- ℓ1 regularization promotes sparsity effectively among convex regularizers but tends to underestimate high-amplitude components.
- The proposed non-convex penalty generalizes ℓ1 while maintaining convexity of the least-squares cost function.
- The penalty ψB is parameterized by B, whose suitable choice depends on A and determines whether the cost function remains convex.
- For arbitrary A, the approach avoids systematic underestimation of high-amplitude sparse components and eliminates suboptimal local minimizers through convexity.
- The generalized MC penalty is constructed from a multivariate Huber function defined using infimal convolution.
- The convex cost can be minimized with proximal algorithms using A, A^T, and soft thresholding, enabling matrix-free implementations.
2 Notation
This section establishes notation for vector and matrix norms, linear operators, convex-analysis functions, and soft thresholding. It also introduces infimal convolution and the Moreau envelope used in the paper’s constructions.
- The section defines the ℓ1, ℓ2, and ℓ∞ norms for vectors in R^N.
- For A ∈ R^(M×N), [Ax]n denotes component n of Ax, and the matrix 2-norm is tied to the largest eigenvalue of A^T A.
- Infimal convolution combines two functions by minimizing their summed values over a shared decomposition.
- The Moreau envelope is introduced as a convex-analysis construction for a function f : R^N → R.
- The notation f = h ◦ g denotes composition, and soft thresholding is defined as a scalar operator with threshold parameter λ ≥ 0.
3 Scalar Penalties
The scalar Huber and MC penalties are represented through convex-analysis constructions, with the MC penalty linked to firm thresholding under a convexity condition. These scalar relationships motivate the multivariate generalization developed later.
- Huber function: The Huber function is a standard Moreau envelope and can equivalently be expressed using infimal convolution.This representation supports the later construction of generalized Huber functions.
- MC penalty: The MC penalty admits a representation involving the Huber function, which is used to generalize it to the multivariate case.
- Scaled functions: Scaled Huber and MC functions introduce a scaling parameter b, with the scaled MC penalty reducing to |x| when b = 0.
- Firm thresholding: The firm threshold function is defined for λ > 0 and µ > λ and interpolates between zero, a transition region, and the identity mapping.
- Firm thresholding: The firm threshold function does not underestimate large amplitudes and approaches hard or soft thresholding as µ approaches λ or infinity, respectively.
- Convexity condition: When b^2 ≤ a^2/λ, the scalar regularized least-squares objective is convex and its minimizer is obtained by firm thresholding.
- Transition to multivariate case: The paper extends the scalar construction by defining multivariate MC penalties, regularized least-squares costs, generalized convexity conditions, and minimization methods.
4 Generalized Huber Function
The generalized Huber function extends the scalar Huber function to multivariate settings through infimal convolution, preserving convex-analytic structure while allowing non-separable behavior. Its properties include convexity, differentiability, and computational limitations that motivate indirect use in sparse regularization.
- Definition and construction: The generalized Huber function S_B is defined through infimal convolution as a multivariate extension of the scalar Huber function.It reduces to the scalar Huber function when B is scalar.
- Convex-analytic properties: S_B is a proper, lower semicontinuous, convex function, and its infimal convolution is exact.The convexity follows from the convexity of the component functions used in the infimal convolution.
- Separable and non-separable cases: When B^T B is diagonal, S_B is separable and consists of a sum of scalar Huber functions; otherwise, it can be non-separable.The non-separable case is the principal multivariate setting illustrated by the paper.
- Examples: For the illustrated matrix in Fig. 6, level sets near the origin are ellipses, whereas for the rank-1 matrix in Fig. 7, level sets are parallel lines.The ellipsoidal contours occur only near the origin; farther away, the contours are not ellipsoidal.
- Further properties: S_B is differentiable, and each component of its gradient has magnitude at most 1.The differentiability is established using its Moreau-envelope representation and convexity.
- Computation: Direct evaluation as a pointwise minimum requires 3^N simpler functions, making it impractical except for small N; the paper instead uses it indirectly for sparse regularization.The simpler functions comprise quadratics, absolute values, and linear functions, while illustrations are computed only on R^2.
5 Generalized MC Penalty
The paper defines the generalized MC penalty from the ℓ1 norm and a multivariate generalized Huber function, yielding a potentially non-separable sparsity penalty with controlled behavior.
- The generalized MC penalty ψB is defined by combining the ℓ1 norm with the generalized Huber function SB.
- When BTB is diagonal, ψB is separable and comprises a sum of scalar MC penalties; when BTB is non-diagonal, it is non-separable.
- Around zero, the generalized MC penalty approximates the ℓ1 norm from below.
- Within any fixed quadrant, ψB is non-decreasing in each coefficient magnitude, so larger same-sign magnitudes receive at least as much penalty.
- Each nonzero gradient component of ψB has the same sign as its corresponding coefficient or is zero.
6 Sparse Regularization
The paper chooses the GMC matrix parameter from A so the non-convex regularized least-squares objective remains convex, with γ controlling the penalty’s nonconvexity.
- The regularized least-squares cost F is convex when ATA − λBTB is positive semidefinite.
- Given A, setting BTB = (γ/λ)ATA satisfies the convexity condition for γ ≤ 1.
- γ = 0 reduces the GMC penalty to the ℓ1 norm, while γ = 1 gives the maximally non-convex case under equality in the convexity condition.
- In practice, the paper uses a nominal range of 0.5 ≤ γ ≤ 0.8.
- When ATA is diagonal, minimizing F reduces to element-wise firm thresholding.
7 Optimization Algorithm
The proposed sparse-regularized objective can be reformulated as a saddle-point or monotone-inclusion problem and minimized with proximal algorithms using simple operator steps.
- A global minimizer can be calculated with proximal algorithms without explicitly evaluating the GMC penalty or its gradient.
- The cost function is rewritten as a saddle-point problem before applying proximal algorithms.
- The resulting saddle-point problems are monotone inclusions solvable by the forward-backward algorithm.
- The forward-backward implementation uses soft-thresholding together with A and AT.
- The algorithm uses γ < 1, with ρ = max{1, γ/(1 − γ)}∥ATA∥2 and a step size satisfying 0 < μ < 2/ρ.
8 Numerical Examples
Numerical examples compare GMC with ℓ1 and other sparse regularizers in frequency-domain denoising, bat-pulse denoising, and signal smoothing, with GMC reducing amplitude underestimation and artifacts.
- 8.1 Denoising using frequency-domain sparsity: GMC achieved the minimum average RMSE among the compared denoising methods, with ℓ1 debiasing performing almost as well.
- 8.1 Denoising using frequency-domain sparsity: In Figure 10, GMC produces a sparser frequency-domain solution, while the ℓ1 solution underestimates coefficient amplitudes.
- 8.1 Denoising using frequency-domain sparsity: Changing λ does not resolve the ℓ1 trade-off: larger λ improves sparsity but reduces amplitudes, whereas smaller λ increases noise and reduces sparsity.
- 8.2 Bat echolocation pulse denoising: For the bat pulse, the GMC penalty produced fewer extraneous noise artifacts in the time-frequency representation.
- 8.3 Sparsity-assisted signal smoothing: In biosensor smoothing, GMC estimated jump discontinuities more accurately than ℓ1, which tends to underestimate amplitudes and can create false detections when λ is reduced.
9 Conclusion
The work bridges convex and non-convex sparse regularization by preserving convex optimization while improving estimation relative to ℓ1 regularization. It also identifies extensions to broader regularizers, nonquadratic data fidelity, and biosensor signal smoothing.
- 9 Conclusion: The proposed non-convex generalization of the ℓ1 norm preserves cost-function convexity and avoids extraneous suboptimal local minima.It supports globally convergent, computationally efficient, scalable convex optimization algorithms.
- 9 Conclusion: Compared with ℓ1 regularization, the method can more accurately estimate high-amplitude sparse components or achieve greater sparsity.In the scalar case, it reduces to firm thresholding, a generalization of soft thresholding.
- 9 Conclusion: The framework may extend to total variation, nuclear, mixed, composite, co-sparse, atomic, and partly smooth regularizers.These extensions are identified as directions for further work rather than completed components of the method.
- 9 Conclusion: With GMC regularization, sparsity-assisted signal smoothing more accurately estimates jump discontinuities in biosensor data.The example applies SASS to biosensor measurements containing jump discontinuities.
- 9 Conclusion: The approach may also extend to nonquadratic data-fidelity problems such as Poisson denoising.The stated least-squares formulation uses a quadratic data-fidelity term, while Poisson denoising is presented as an extension of interest.