Abstract
This paper investigates the numerical minimization of energy functionals in Hilbert spaces involving convex constraints that coincide with a semi-norm for a subspace. The optimization is achieved through alternating minimizations of the functional across a sequence of orthogonal subspaces. The primary innovation introduced is the "oblique thresholding" technique, an iterative proximity-map algorithm implemented on each subspace. We establish convergence conditions for both sequential and parallel variants of the algorithm, ensuring they reach the minimizers of the target energy. The framework is applied to domain decomposition for singular elliptic PDEs in total variation (TV) minimization and accelerated sparse recovery via $\ell_1$-minimization. Numerical experiments demonstrate the efficiency of these methods in solving classic signal and image processing challenges.
Introduction
In the fields of image processing and compressed sensing, many problems are formulated as the minimization of an energy functional. These functionals typically consist of a data-fidelity term, ensuring the model fits the observed data, and a non-smooth regularization term, such as Total Variation (TV) or the $\ell_1$-norm, which promotes desirable properties like edge preservation or sparsity.
While iterative thresholding algorithms are standard tools for these problems, they often suffer from slow convergence rates in high-dimensional settings. Domain decomposition—splitting a large problem into smaller, parallelizable sub-problems—is a common strategy for acceleration. However, for "singular" problems like TV minimization, this approach is fraught with difficulty. Discontinuities, such as edges in an image, frequently cross the artificial boundaries of the subdomains. Standard decomposition methods often fail to correctly "stitch" these features back together, leading to artifacts at the interfaces. This paper introduces a mathematically rigorous framework to perform this splitting without sacrificing accuracy at the boundaries.
The Core Innovation: Oblique Thresholding
The central contribution of this work is the introduction of Oblique Thresholding. This technique allows for the decomposition of a large Hilbert space into a sequence of orthogonal subspaces while maintaining the integrity of the global solution.
1. Subspace Splitting and Alternating Minimization
The algorithm decomposes the global space into a sequence of orthogonal subspaces. Rather than attempting to solve the entire minimization problem simultaneously, the algorithm alternates between these subspaces. In each step, it solves a localized version of the problem that accounts for the current state of the other subspaces.
2. The Oblique Proximity Map
Standard soft-thresholding (the proximity map for the $\ell_1$-norm) works effectively when the regularization term is "separable," meaning the penalty on one variable does not depend on another. However, in TV minimization, pixels at the boundary of one subdomain interact with pixels in the adjacent subdomain.
To address this, the authors developed a generalized Lagrange multiplier approach. The "oblique" version of the proximity map incorporates the influence of neighboring subspaces during the local minimization step. This ensures that the local update is consistent with the global energy functional, effectively handling the "interface condition" that typically plagues domain decomposition in singular problems.
3. Sequential and Parallel Variants
The paper details two primary algorithmic structures:
- Sequential Variant: Subspaces are updated one by one. This version is easier to analyze and provides stable convergence.
- Parallel Variant: All subspaces are updated simultaneously, making it ideal for multi-core and distributed computing environments. To ensure the energy functional consistently decreases, the authors employ a "halving" trick (a specific step-size adjustment) to maintain stability during parallel updates.
Experimental Validation
The authors validated their theoretical framework using a variety of synthetic and real-world numerical examples.
Total Variation Inpainting
In 2D image processing, the method was tested on "inpainting" tasks—recovering missing data within an image. Using a "Robin Hood" text image and a photograph of a cat, the authors demonstrated that the domain decomposition method could split an image into multiple arbitrary strips, process them, and reconstruct the missing sections seamlessly. The oblique thresholding operator correctly matched discontinuous edges across boundaries, leaving no visible "seams."
Accelerated Sparse Recovery
For $\ell_1$-minimization, the authors utilized $200 \times 40$ random matrices with Gaussian entries to simulate sparse recovery. A key finding was that choosing subspaces based on the Singular Value Decomposition (SVD) of the operator $T$ significantly accelerated the initial iterations. This SVD-based splitting quickly identifies the "support" (the locations of non-zero entries) of the sparse signal, leading to much faster convergence than standard iterative thresholding.
Key Insights and Results
- Interface Preservation: Oblique thresholding naturally handles discontinuities across subdomain boundaries, a feat that naive subdifferential approaches cannot achieve.
- Conditioning Improvement: By splitting a large, ill-conditioned operator into smaller subspace-restricted operators, the local conditioning of the problem is improved, which accelerates the overall convergence of the system.
- Convergence Guarantees: The paper provides rigorous proofs (Theorems 5.1 and 6.1) confirming that both the sequential and parallel algorithms converge to a global minimizer under specific conditions.
Limitations and Future Work
While the results are promising, certain limitations remain. The strongest convergence results are currently proven for finite-dimensional spaces; while sufficient for digital applications, the infinite-dimensional theory requires further refinement. Additionally, the speed of convergence is highly sensitive to the choice of subspaces. While SVD-based splitting is effective, it can be computationally expensive for very large-scale matrices. Finally, the width of the "stripe" used for computing the oblique thresholding (the $\eta$ parameter) is currently chosen heuristically. Future research could focus on automating this parameter selection based on the local scale of image features.
Summary updated