Abstract
Total variation (TV) is a widely used regularizer for stabilizing the solution of ill-posed inverse problems. In this paper, we propose a novel proximal-gradient algorithm for minimizing TV regularized least-squares cost functional. Our method replaces the standard proximal step of TV by a simpler alternative that computes several independent proximals. We prove that the proposed parallel proximal method converges to the TV solution, while requiring no sub-iterations. The results in this paper could enhance the applicability of TV for solving very large scale imaging inverse problems.
Introduction
In imaging science, recovering a clean image from noisy or incomplete data is a fundamental linear inverse problem. Total Variation (TV) regularization is a cornerstone technique for this task, valued for its ability to suppress noise while preserving sharp edges. However, TV minimization faces a significant computational bottleneck. Standard solvers, such as the Iterative Shrinkage-Thresholding Algorithm (ISTA), require evaluating a proximal operator in each iteration. For TV, this operator lacks a closed-form solution, necessitating nested optimization sub-iterations. This "loop-within-a-loop" structure makes TV reconstruction prohibitively slow for large-scale 3D datasets.
Methodology: The Parallel Proximal Approach
The proposed method circumvents nested iterations by decomposing the complex TV proximal step into an average of simpler, independent operations.
- Decomposition via Redundancy: The TV regularizer is mathematically decomposed into a sum of simpler functions using a redundant Haar wavelet transform (specifically, a Parseval frame). This transforms a non-separable problem into a sum of separable ones that are much easier to solve.
- Parallel Processing: After a standard gradient descent step, the algorithm applies simple thresholding (shrinkage) to multiple shifted versions of the image in parallel. This provides a rigorous optimization framework for "cycle spinning," a classic heuristic in wavelet denoising.
- Averaging and Acceleration: The results of these parallel steps are averaged to form the next estimate. To ensure efficiency, the framework is integrated with the Fast Iterative Shrinkage-Thresholding Algorithm (FISTA), achieving an $O(1/t^2)$ convergence rate.
Crucially, this approach is "sub-iteration free," reaching the TV solution without the overhead of internal optimization loops.
Experimental Results
The algorithm was evaluated using a $32 \times 32$ Shepp-Logan phantom reconstructed from 512 linear measurements corrupted by Additive White Gaussian Noise (AWGN) at a 30 dB Signal-to-Noise Ratio (SNR).
Convergence Behavior
Theoretical analysis suggests that the parallel approximation converges to the neighborhood of the true TV minimizer, with accuracy controlled by the step size $\gamma$. Empirical results confirm this stability, showing the relative gap from the optimal cost shrinking consistently over iterations.
Reconstruction Accuracy
The parallel method successfully approximates the true TV solution. As shown in the visual comparison, reducing the step size $\gamma$ allows the method to reach a Peak Signal-to-Noise Ratio (PSNR) of 27.94 dB, which is nearly identical to the 27.96 dB achieved by standard TV solvers.
Discussion and Conclusion
By eliminating nested loops, each iteration of the parallel proximal method is significantly faster than traditional TV approaches, particularly as data dimensionality increases. While this study utilized a small 2D phantom, the framework is designed for "very large scale" problems like 3D microscopy or medical CT.
Future work includes benchmarking on large-scale 3D datasets to quantify real-world speedups and extending the parallel proximal framework to other non-separable regularizers beyond anisotropic TV. This could broaden the applicability of sophisticated imaging models in high-throughput scientific imaging.
Summary updated