Source-linked AI summary
A Cone-Constrained Bilinear Decomposition for Total Scaled-Gradient Variation Models
Haibin Su, Chunlin Wu, Huibin Chang, Zhifang Liu
TL;DR
The paper addresses computational and theoretical difficulties in nonlinear, nonconvex TSGV restoration by introducing a constrained bilinear decomposition and an MM-based alternating solver. The method provides monotonic energy descent and critical-point convergence, while experiments demonstrate robustness in denoising and NLOS imaging.
Problem
TSGV restoration is nonlinear and highly nonconvex, while existing methods can be parameter-sensitive or lack convergence guarantees.
Method
The paper decouples the nonlinear weighted gradient through an equivalent bilinear reformulation with cone or spherical constraints and solves it using MM-based alternating minimization.
Results
The method guarantees monotonic energy decrease and convergence of the generated sequence to a critical point of the quadratic-penalty problem.
Takeaways & Limitations
The cone constraint is better adapted to edges and corners, while experiments demonstrate robustness and flexibility in image denoising and NLOS imaging.
Takeaways & Limitations
The method still requires manual adjustment of the model parameter λ and penalty parameter α.
Abstract
from arXiv · showhide
The total scaled-gradient variation (TSGV) regularizer, derived from sparse modeling of piecewise-linear structures, has been shown to preserve edges and corners in image restoration. However, its highly nonconvex and nonlinear nature poses severe computational challenges, as existing methods often suffer from parameter sensitivity or lack convergence guarantees. To overcome this, we propose a tailored bilinear decomposition that decouples the nonlinear weighted gradient in the TSGV regularizer. This approach yields an equivalent optimization problem governed by cone or sphere constraints, depending on the chosen scaling function. In particular, the cone constraint plays a central role in characterizing edge- and corner-preserving behavior. We solve this reformulation using the alternating minimization method (AMM) equipped with a majorization--minimization strategy, ensuring a monotonic decrease in energy without step-size tuning. Furthermore, we provide a geometric interpretation of the edge-preserving properties of these constraints by analyzing their asymptotic behavior near image singularities. We establish the global convergence of the proposed method to a critical point within the Kurdyka--Łojasiewicz framework. Extensive numerical experiments on Gaussian denoising and non-line-of-sight (NLOS) imaging show that the proposed method achieves PSNR and SSIM competitive with or superior to representative variational methods, especially at high noise levels, and improves the structural reconstruction under dense and sparse scanning.
1. Introduction.
The paper develops a constrained bilinear reformulation and MM-based alternating solver for the nonlinear TSGV model, addressing parameter sensitivity and convergence gaps in existing methods.
- Motivation: TSGV is a high-order regularization framework derived from sparse modeling of piecewise-linear structures.It connects geometry-driven approaches with sparse representation and includes several classical high-order regularizers as special cases.
- Limitations of existing methods: Existing ALM methods can be sensitive to multiple penalty parameters, while operator-splitting methods lack rigorous convergence theory for nonconvex high-order models.Earlier bilinear approaches provide KL-based convergence guarantees, but their practical performance still depends on parameter selection.
- Proposed approach: The proposed decomposition exactly decouples the nonlinear field ψ(|∇u|)∇u using an augmented direction field with a third component encoding the scaling relation.The resulting equivalent formulation uses non-Riemannian cone or spherical constraints.
- Optimization method: The MMAMM algorithm uses a surrogate function to ensure monotonic energy descent without explicit step-size dependence.This avoids step-size sensitivity and potential numerical instability associated with traditional gradient-based solvers.
- Theory: The paper establishes sequence boundedness and convergence to a critical point within the Kurdyka–Łojasiewicz framework.The convergence guarantee applies to the proposed nonconvex optimization scheme.
2. A bilinear decomposition method for the TSGV-based model.
The TSGV model is reformulated by introducing variables that separate its nonlinear weighted-gradient structure, yielding equivalent constraint-based formulations for selected scaling functions.
- Variable transformation: Two auxiliary variables are introduced to decouple the nonlinearities in the weighted gradient structure.The reformulation is constructed for the scaling family ψ_j associated with (b + s^j)^(1/j), with b > 0 and j ≥ 1.
- Constraint geometry: For b, one constraint reduces to the Euclidean norm relation n_1^2 + n_2^2 + n_3^2 = 1.This identifies the spherical form of the constraint in the corresponding parameterization.
- Equivalent formulation: The transformed model is expressed as an equivalent constrained minimization problem.The induced length-like quantity is defined through the scaling function.
- Constraint geometry: The paper focuses on j = 1 and j = 2, corresponding respectively to cone-constrained and upper-hemisphere-constrained formulations.Thus, different scaling functions generate distinct feasible-set geometries.
3. Asymptotic analysis of the different constraints near edges.
The asymptotic analysis separates gradient-magnitude and gradient-direction variation, showing that the cone constraint is anisotropically adapted to edge geometry.
- Geometric decomposition: The regularizer penalizes both variation of the gradient magnitude and variation of the gradient direction.This decomposition provides the basis for comparing constraints near image edges.
- Directional variation: In the edge regime, the cone constraint assigns a smaller weight to directional variation, so changes in the normal direction are less penalized.The comparison is made as the gradient magnitude s tends to infinity.
- Magnitude variation: The cone constraint penalizes gradient-magnitude variation more strongly than directional variation in the edge regime.This contrasts the two geometric components of the regularizer.
- Edge preservation: Consequently, the cone constraint allows sharp changes in edge direction while suppressing oscillations near edges.The paper interprets this anisotropic weighting as better adapted to edge geometry.
4. Majorization-minimization alternating minimization method.
MMAMM alternates updates for the discretized model and uses majorization to handle the nonconvex n-subproblem. The resulting updates exploit pixelwise decoupling, FFT-based linear solves, and cone or spherical projections.
- Alternating minimization: MMAMM alternately updates u, n, and q within the discretized optimization framework.The method constructs the discretized model on an N × N grid and computes the three variables successively.
- Discretization: The discretization represents images as vectors and defines gradient and divergence operators using periodic finite differences and Kronecker products.Forward and backward differences generate the discrete gradient, while the divergence is defined through standard inner products.
- Subproblem structure: The n-subproblem is difficult because its constraint is nonconvex, whereas u- and q-subproblems are strongly convex and efficiently solvable in closed form.Earlier splitting methods require a step size bounded by a Lipschitz constant that depends on qk and may become prohibitively small.
- Majorization-minimization: MMAMM majorizes the nonlinear n-subproblem with a quadratic surrogate using µ > Lφ, producing a tractable update with sufficient descent.The surrogate combines the exact quadratic expansion of hk with a quadratic upper bound for φ.
- Descent and computation: The MM construction guarantees energy descent independently of the particular inner algorithm, allowing any solver that exactly or sufficiently decreases the surrogate.Under periodic boundary conditions, the associated linear system can be solved efficiently by FFT.
- Implementation: The n-update reduces to N^2 independent pixelwise problems because Λk is block diagonal, followed by projection onto an upper-cone or upper-hemispherical surface.For j = 1, the projection uses the cone surface S1,+; for j = 2, the constraint is the upper hemisphere S2,+.
5. Convergence analysis of MMAMM.
The convergence analysis establishes regularity, descent, boundedness, and subgradient control for MMAMM. Together with the Kurdyka–Łojasiewicz property, these results imply convergence of the iterates to a critical point.
- Regularity estimates: The partial derivatives of Eα with respect to u, n, and q are Lipschitz continuous with explicit bounds Lu, Lq, and Ln.The analysis separately estimates the regularization and quadratic penalty contributions to the n-gradient.
- Regularity estimates: The n-regularization analysis uses the symmetry and eigenstructure of gϕ(g), chain-rule Hessian expressions, and difference-operator norm estimates.These estimates combine into an upper bound for the Hessian and hence the Lipschitz constant of the n-gradient.
- Descent: The MMAMM energy sequence is nonincreasing and satisfies a sufficient descent property along the iterations.Descent in n follows from the MM update, while descent for u and q is established separately.
- Boundedness: The generated sequence remains uniformly bounded because n is bounded and Eα,I is coercive with respect to (u, q).This boundedness supports the subsequent subgradient estimates used in the convergence proof.
- Global convergence: The KL-based convergence theorem shows that the full MMAMM sequence converges to a critical point of the quadratic-penalty problem Eα,I.The convergence conclusion applies to the sequence {(uk+1, nk+1, qk+1)} generated by the proposed method.
- Constraint feasibility: For fixed α, feasibility violations of the bilinear constraints remain uniformly controlled, and increasing α enforces those constraints more strongly.The control follows from the nonincreasing energy and the nonnegative penalty term.
6. Numerical experiments.
The experiments evaluate MMAMM for TSGV-based image restoration across Gaussian denoising and NLOS imaging, examining parameter sensitivity, structural preservation, convergence, quality, and efficiency. MMAMM generally improves restoration quality and edge preservation, particularly under high noise and sparse scanning, while requiring more iterations than IOS–TSGV.
- Experiment settings: The denoising experiments use Gaussian noise with variance 0.0025 for TestImg1–TestImg7 and 0.005 for TestImg8–TestImg11.The test set includes binary, synthetic, and real images with different resolutions.
- Experiment settings: MMAMM performs well for λ ∈[10, 300] and α ∈[100, 800] in most Gaussian denoising experiments.The broader parameter investigation covers λ ∈[1, 500] and α ∈[100, 1000] on TestImg4 and TestImg8.
- Advantages of MMAMM over the IOS algorithm: MMAMM–ψ1 preserves edges and corners better than IOS–TSGV on binary images, while MMAMM–ψ2 achieves the highest PSNR for TestImg1–TestImg3.MMAMM methods require more iterations and longer total runtimes, but their average time per iteration is approximately one-sixth that of IOS–TSGV.
- Advantages of MMAMM over the IOS algorithm: MMAMM produces smoother, more regular restored surfaces than IOS–TSGV in smooth regions, with MMAMM–ψ1 better removing small oscillatory artifacts.MMAMM–ψ2 still leaves visible residual noise at a few isolated points.
- Advantages of MMAMM over the IOS algorithm: All tested algorithms converge stably, although IOS–TSGV converges faster while ending at a larger final relative-error value than the MMAMM methods.The comparison uses 2000 iterations on TestImg4 and TestImg8 with different noise levels.
- Comparison of state-of-the-art methods: At noise variance 0.005, MMAMM–ψ1 consistently achieves the best PSNR and SSIM, while MMAMM methods preserve edges more effectively than IOS–TSGV and HALM–EE.In NLOS imaging, MMAMM generally outperforms LCT and CNLOS; ψ1 leads PSNR for 64×64, 32×32, and 16×16 scans, while ψ2 leads SSIM, whereas CNLOS has the highest PSNR at 8×8.
7. Conclusions.
The paper introduces a bilinear decomposition for nonconvex TSGV models that preserves their geometric structure while making computation more tractable. Its alternating-minimization/MM algorithm and experiments support the method’s convergence, robustness, and flexibility.
- The bilinear reformulation preserves the geometric structure of TSGV while making the nonconvex optimization more tractable.
- Cone-constraint asymptotic analysis indicates better adaptation to edges and corners, consistently with the numerical results.
- Alternating minimization with majorization-minimization produces tractable surrogate subproblems and ensures monotone energy decrease.
- The convergence analysis provides theoretical justification for the proposed scheme, while experiments demonstrate robustness and flexibility in image denoising and NLOS imaging.