PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse Signal Estimation by Maximally Sparse Convex Optimization

Ivan W. Selesnick, Ilker Bayram

arXiv:1302.5729v3cs.LGstat.ML

TL;DR

Sparse signal estimation seeks stronger sparsity than ℓ1 regularization without relying on non-convex optimization. This paper designs parameterized non-convex penalties constrained so the total cost remains convex, with parameters selected by semidefinite programming. The resulting MSC framework, and its iterative extension IMSC, is reported to produce substantially sparser solutions than ℓ1 minimization.

  • Problem

    The paper addresses how to obtain solutions to ill-posed sparse signal estimation problems that are more sparsity-promoting than ℓ1 regularization without relying on non-convex optimization.

  • Method

    MSC optimizes parameters of non-convex penalty functions subject to convexity constraints on the total cost, with those constraints obtained through semidefinite programming; IMSC repeats this process on active coefficients.

  • Results

    IMSC is reported to yield solutions substantially more sparse than ℓ1 minimization, while the total cost remains convex.

  • Takeaways & Limitations

    The approach provides a convex alternative to ℓ1 minimization that uses maximally sparsity-inducing penalties within the convexity constraint.

Abstract

from arXiv · show

This paper addresses the problem of sparsity penalized least squares for applications in sparse signal processing, e.g. sparse deconvolution. This paper aims to induce sparsity more strongly than L1 norm regularization, while avoiding non-convex optimization. For this purpose, this paper describes the design and use of non-convex penalty functions (regularizers) constrained so as to ensure the convexity of the total cost function, F, to be minimized. The method is based on parametric penalty functions, the parameters of which are constrained to ensure convexity of F. It is shown that optimal parameters can be obtained by semidefinite programming (SDP). This maximally sparse convex (MSC) approach yields maximally non-convex sparsity-inducing penalty functions constrained such that the total cost function, F, is convex. It is demonstrated that iterative MSC (IMSC) can yield solutions substantially more sparse than the standard convex sparsity-inducing approach, i.e., L1 norm minimization.

I. INTRODUCTION

The paper seeks stronger sparsity than ℓ1 regularization while retaining reliable convex optimization for ill-posed linear inverse problems. MSC uses parameterized non-convex penalties constrained by the problem operator so the total cost remains convex, while IMSC extends the approach to rank-deficient or ill-conditioned systems.

  • Motivation: ℓ1 regularization is easy to solve reliably but can be less sparsity-promoting than non-convex penalties, whose optimization generally provides only local optima.Non-convex solutions can therefore be sensitive to algorithmic details.
  • MSC approach: MSC selects non-convex penalties whose parameters maximize sparsity induction subject to convexity of the total cost function F.The approach balances positive curvature from the quadratic fidelity term against negative curvature from the penalty terms.
  • MSC approach: The parameter constraints ensuring convexity are obtained by formulating a semidefinite program, so the penalty design itself is based on convex optimization.The resulting cost function is then minimized using the selected penalty parameters.
  • IMSC: IMSC applies MSC to active elements from the previous sparse solution, extending the method to rank-deficient or ill-conditioned operators such as overcomplete dictionaries and near-singular deconvolution systems.Each IMSC iteration solves a convex optimization problem.
  • Penalty and threshold design: The proposed penalty family is chosen to support MSC and is intended to provide unbiasedness for large coefficients, sparsity, and continuity.Its parameterization controls threshold sensitivity and the associated penalty behavior.
  • Relation to prior approaches: Unlike ℓ0 methods, MSC defines a convex problem and keeps every coefficient regularized rather than leaving the estimated support unpenalized.Unlike usual convex sparse estimation, it uses non-convex penalties constrained by H and λn.

II. SCALAR THRESHOLD FUNCTIONS

This section motivates continuous threshold functions that combine sparsity with reduced bias for large coefficients. It shows why avoiding large-value attenuation requires non-convex penalties and frames the desired threshold properties.

  • Threshold-function trade-offs: Hard thresholding is highly sensitive to small input changes, while soft thresholding is insensitive but substantially biases large inputs.The hard threshold's discontinuity can produce spurious noise peaks or bursts.
  • Design objectives: The target threshold function should allow sensitivity θ′(T +) to vary from 1 to infinity while making the large-input bias y − θ(y) decay rapidly to zero.These requirements combine tunable threshold behavior with reduced attenuation of large coefficients.
  • Proximity operator: The proximity operator θ is the thresholding operation associated with a penalty φ, and strict convexity of the total cost is assumed to make its minimizer unique.The paper uses this operator to connect penalty design with scalar threshold behavior.
  • Convexity and bias: For convex penalties, the gap between the input y and threshold output θ(y) increases with |y|, so avoiding large-value attenuation requires a non-convex penalty.Soft thresholding is an extreme convex case with a constant gap beyond the threshold.

B. Properties

The logarithmic penalty yields a continuous threshold whose sensitivity and bias depend on its parameter. The paper then proposes setting the threshold curvature to zero to obtain faster convergence toward the identity for the same threshold sensitivity.

  • Logarithmic penalty: The logarithmic penalty produces a threshold through θ(y) = f^-1(y), where f(x) = x + λφ′(x).Figure 1 presents the penalty derivative, the function f, and the resulting threshold function.
  • Convexity condition: 0 < a ≤ 1/λ ensures that f is increasing, the total cost F is convex, and the threshold function θ is continuous.The threshold is T = λ in this parameter range.
  • Threshold sensitivity: As a varies from 0 to 1/λ, θ′(T +) varies from 1 to infinity, while a → 0 recovers the soft-threshold limit.The parameter a therefore controls threshold sensitivity within the convexity range.
  • Bias behavior: The logarithmic penalty's single parameter a affects both threshold sensitivity and the rate at which y − θ(y) approaches zero for large y.Increasing a accelerates the approach to the identity but also changes θ′(T +).
  • Penalty refinement: The proposed next penalty sets θ′′(T +) = 0 to make the gap from θ to the identity decay more rapidly at the same threshold sensitivity.The logarithmic penalty has θ′′(T +) strictly negative except in the soft-threshold case.

D. The Arctangent Penalty Function

The arctangent penalty is designed to approach the identity faster than the logarithmic penalty while remaining compatible with convex total-cost optimization. Its parameterization controls threshold sensitivity and convergence toward the identity, with larger sensitivity producing faster convergence but potentially greater threshold sensitivity.

  • Construction: The arctangent penalty is constructed from a derivative-based model whose parameter b makes its threshold function approach the identity rapidly.Setting θ′′(T +) = 0 gives b = a^2, producing the proposed penalty family.
  • Convexity: For 0 < a ≤ 1/λ, f(x) is strictly increasing, F is strictly convex, and the threshold function θ is continuous.The threshold is T = λ, with a selected through the desired right-sided threshold derivative.
  • Parameter effects: With T = λ = 2, θ′(T +) values of 1, 2, and ∞ correspond to a = 0, 1/4, and 1/2, respectively.At infinite sensitivity, convergence to the identity is faster, but sensitivity near the threshold may be excessive.
  • Comparison: When T = θ′(T +) = 2, the arctangent threshold function converges to the identity faster than the logarithmic threshold function.The gap between each threshold function and the identity also goes to zero more rapidly for the arctangent function.
  • Penalty properties: The arctangent penalty grows more slowly than |x| and tends to a constant, yielding less large-x bias than both the ℓ1 norm and logarithmic penalty.All three penalties have slope 1 at x = 0; the arctangent penalty is more concave at the origin than the logarithmic penalty.

E. Other Penalty Functions

The paper contrasts other non-convex penalties with its convex-cost objective. The ℓp pseudo-norm is excluded because it cannot produce a convex total cost, while firm and SCAD penalties create divide-by-zero issues for some algorithms.

  • Firm and SCAD penalties: Firm and SCAD penalties are continuous and equal the identity for large |y|, but their derivatives can cause divide-by-zero issues in IRLS and MM.Their corresponding penalty derivatives become zero above some value, making these algorithms unsuitable for them.
  • ℓp penalty: For 0 < p < 1, the ℓp pseudo-norm makes F non-convex for every p, so it is not considered for convex-cost non-convex regularization.The paper therefore focuses on penalty functions whose non-convexity is constrained while F remains convex.

F. Denoising Example

The denoising example compares threshold functions and illustrates how non-convex penalties can produce a convex total cost while inducing sparsity more strongly than the ℓ1 norm.

  • Denoising via thresholding: The experiment applies each threshold at T = 3σ to a length-2048 noisy bumps signal with σ = 0.4 and an orthonormal Daubechies wavelet.
  • Denoising via thresholding: The hard threshold achieves the best RMSE but produces spurious noise bursts, while soft thresholding suppresses bursts at the cost of attenuated peaks and higher RMSE.
  • Denoising via thresholding: The arctangent threshold suppresses noise bursts with modest peak attenuation and RMSE closer to hard thresholding.
  • Convexity condition: A diagonal lower bound R and parameter-set constraints on (λn, an) ensure strict convexity of F when the stated matrix conditions hold.
  • Convexity condition: For a = 0.1, the logarithmic penalty is non-convex but F remains convex, whereas a = 0.2 makes both the penalty and F non-convex.
  • Convexity condition: A tighter lower bound permits more non-convex, sparsity-inducing penalties while preserving convexity, yielding the maximally sparse convex choice.

B. Diagonal Lower Bound Matrix Computation

The method computes a diagonal positive semidefinite lower bound R for H^T H by jointly maximizing its diagonal entries under a positive semidefinite constraint.

  • Optimization formulation: The diagonal entries rn are optimized jointly so that H^T H − R remains positive semidefinite.
  • Optimization formulation: The resulting problem is a semidefinite optimization problem with a linear objective and linear matrix inequalities, solvable using convex-optimization software.
  • Optimization formulation: The baseline R = αminI is feasible but generally suboptimal, whereas tighter bounds allow more non-convex penalties and potentially sparser solutions.
  • Computational limitation: For large matrix-free problems, SDP computation can be a bottleneck; in one deconvolution example it took 35 to 55 times longer than the ℓ1 solution.

C. Optimality Conditions and Threshold Selection

Strict convexity supplies optimality conditions for validating solutions and setting regularization parameters, including choices based on the noise-only model.

  • Optimality conditions: When F is strictly convex, its minimizer satisfies conditions that can verify numerical optimality and help set λn.
  • Optimality conditions: For log and arctangent penalties, optimality can be visualized by plotting [H^T(y − Hx)]n/λn against xnan, with points lying on φ′.
  • Threshold selection: If the true signal is zero, the observation is noise only, and the optimality condition can determine λn values that yield an all-zero solution.
  • Threshold selection: Because larger λn increases attenuation, the method selects the smallest value satisfying the zero-solution condition.
  • Threshold selection: Noise statistics and the three-sigma rule can estimate the required regularization when the actual noise realization is unavailable.

D. Usage of Method

MSC constructs a convex sparse-estimation problem from a suitable penalty and diagonal lower bound, while IMSC repeatedly restricts the problem to the current active support to obtain progressively sparser solutions.

  • MSC usage: MSC takes y, H, λn, and a parameterized penalty as input, computes R, selects an so (rn/λn, an) lies in the convexity set, and minimizes F.
  • MSC usage: For β = 1, the penalty is maximally non-convex subject to convex F; β = 0 reduces to the ℓ1 norm and provides no advantage.
  • MSC usage: The minimization in MSC remains a convex optimization problem, with the most efficient algorithm depending primarily on H.
  • Limitations: MSC can offer no advantage over ℓ1 when R is zero or nearly zero, a situation arising in noninvertible or nearly singular deconvolution and overcomplete-frame BPD.
  • IMSC procedure: IMSC starts from an ℓ1 solution, identifies its nonzero support, recomputes a lower bound on the corresponding submatrix, and repeats until the support stops shrinking.
  • IMSC procedure: Each IMSC iteration relaxes the lower-bound constraints as active columns are removed, making penalties more non-convex and producing successively sparser solutions.

F. Deconvolution Example

The deconvolution experiment compares ℓ1, non-convex, and iterative MSC methods using estimation and support errors. IMSC produces competitive sparse solutions through convex optimization, but SDP computation is substantially slower than ℓ1 minimization.

  • Non-convex baselines: The ℓp quasi-norm with p = 0.7 substantially improves upon the ℓ1 result, while IRL1 outperforms IRL2 because IRL2 can converge to a local minimizer.Debiasing improves L2E and L1E for both methods but does not affect SE.
  • IMSC results: IMSC results are reported with logarithmic and arctangent penalties, with the arctangent penalty improving L2E, L1E, and SE relative to the logarithmic penalty.Debiasing substantially helps the logarithmic penalty but has negligible effect for the arctangent penalty; the simplified IMSC/S variant is faster but less accurate.
  • Bias comparison: The IMSC solution lies closer to the identity than the ℓ1 solution, whose estimates tend to underestimate the true values.Only non-zero elements are shown in the comparison.
  • Method comparison: IMSC (atan) has lower SE than ℓ1 minimization, AIHT, and ISD, although SBR and IRL1 with debiasing outperform it on L2E and L1E.The paper characterizes IMSC as reasonably close to the best error measures despite relying entirely on convex optimization.
  • Computation: 1.7 seconds were required for IMSC with the atan penalty versus 52 milliseconds for ℓ1 minimization, with about 94% of IMSC time spent solving SDPs.The atan implementation solved three SDPs of sizes 61, 40, and 38; the ℓ1 solution was 33 times faster.

IV. CONCLUSION

MSC uses non-convex, sparsity-inducing penalties while constraining the total cost to remain convex, with maximally non-convex penalties found by semidefinite programming. IMSC applies MSC iteratively to active elements, while the approach remains less sparse than non-convex optimization methods and faces large-scale implementation considerations.

  • MSC and IMSC: MSC finds maximally sparsity-inducing non-convex penalties subject to convexity of the total cost, using semidefinite programming.Each IMSC iteration solves a convex optimization problem on the active elements from the previous iteration.
  • MSC and IMSC: IMSC applies MSC to the non-zero elements of the previous sparse solution, with every iteration formulated as a convex optimization problem.
  • Design objective: The method asks which convex optimization problem best promotes sparsity within a parameterized family of penalty functions.
  • Scope and comparison: MSC cannot be expected to produce solutions as sparse as non-convex methods such as ℓp quasi-norm minimization, although it provides enhanced sparsity relative to ℓ1 minimization.
  • Implementation boundary: Large-scale image and video reconstruction benefits from algorithms for equation (33) that avoid accessing or manipulating individual rows or columns of H.

APPENDIX

The appendix characterizes the thresholding solution of the strictly convex penalized problem through subdifferentials and the inverse of an increasing function. It establishes the zero-threshold interval, positive-solution case, threshold continuity, and a curvature condition ensuring strict convexity.

  • Thresholding characterization: For strictly convex F, the minimizer x* satisfies 0 ∈ ∂F(x*), providing the condition used to characterize thresholding.
  • Thresholding characterization: When y lies within [λφ′(0−), λφ′(0+)], the minimizer is x*=0 and, for symmetric φ, the threshold is T=λφ′(0+).
  • Nonzero solution: For y>λφ′(0+), the minimizer satisfies x*>0, and the threshold function is expressed through the increasing function f.
  • Continuity: The threshold function θ is continuous at T because f is continuous and f(0+)=λφ′(0+)=T.
  • Convexity condition: For symmetric φ, strict convexity is equivalent to f being strictly increasing for x>0 and is ensured by φ′′(x)>−1/λ.
Loading 1302.5729v3…