Introduction
Linear ill-posed problems are a cornerstone of modern imaging science, appearing in applications ranging from Computed Tomography (CT) to Compressive Temporal Imaging (CACTI). These problems are characterized by their inherent instability: small perturbations in the input data, such as sensor noise, can lead to disproportionately large errors in the reconstructed solution. Traditionally, iterative methods like the Landweber iteration have been used to solve these problems. However, as data scales increase—moving from 2D images to high-resolution 3D volumes and high-speed video—these standard approaches encounter a "memory wall." They require calculating the gradient for the entire dataset at every step, making them computationally prohibitive for massive datasets.
This paper provides the first rigorous convergence analysis for the Randomized Block Coordinate Descent (RBCD) method specifically applied to linear ill-posed problems. By updating only a single "block" of the solution at a time, RBCD offers a path toward solving large-scale problems with significantly reduced memory and time requirements while maintaining the stability necessary for ill-posed regimes.
The RBCD Framework
The authors analyze several variations of the RBCD algorithm to address different aspects of the reconstruction process:
- Basic RBCD (Algorithm 1): In this version, a block index is chosen uniformly at random at each iteration. Only the corresponding component of the solution is updated using a partial gradient. A critical efficiency gain is achieved through a recursive update of the residual (the difference between the model and the data). By tracking how local block updates affect the global error, the algorithm avoids expensive full-matrix multiplications, keeping the process computationally "lightweight."
- Discrepancy Principle (Algorithm 2): In ill-posed problems, iterating indefinitely often leads to semi-convergence, where the algorithm begins to fit the noise rather than the signal. The authors incorporate a stopping rule based on the noise level ($\delta$). They prove that this method terminates in a finite number of steps almost surely, providing a theoretical safety net for practical applications.
- Convex Regularization (Algorithms 3 & 4): To improve image quality—specifically to preserve sharp edges—the method is extended to include convex terms such as Total Variation (TV). This version utilizes Bregman distances and proximal operators to handle non-smooth features, allowing for more sophisticated image priors.
Theoretical Insights
The primary contribution of this work is the proof that RBCD acts as a mathematically sound regularization method. The authors demonstrate "weak convergence" to a solution for general problems and "strong convergence" for problems with specific structures, such as tensor products. This confirms that the randomness inherent in the block selection does not just save time; it reliably leads to the correct solution. Furthermore, the authors prove that the expected error of the RBCD iterates is bounded by the noise level, ensuring stability even when dealing with noisy sensor data.
Experimental Results
The algorithms were evaluated using standard benchmarks and real-world datasets, including the Shepp-Logan phantom, a 3D chest CT volume, and video datasets ("Runner" and "Kobe") for Coded Aperture Compressive Temporal Imaging.
- Computational Efficiency: In CT simulations, RBCD achieved a 5% relative error in approximately half the time required by the standard Landweber method (e.g., ~5 seconds compared to ~9.4 seconds).
- Memory Management: By partitioning the problem into 8 or 16 blocks, the peak memory requirement was drastically reduced. This allows for high-resolution reconstructions on consumer-grade hardware that would otherwise be unable to process the full dataset.
- Video Reconstruction: The method successfully reconstructed 8 frames of video from a single compressed snapshot in CACTI simulations. Even with 1% added noise, the algorithm maintained high Peak Signal-to-Noise Ratio (PSNR) and Structural Similarity (SSIM) scores, effectively "hallucinating" temporal details based on the physics of the imaging mask.
Discussion and Future Work
While RBCD offers significant advantages in speed and memory, the authors note a limitation regarding "block mismatch." Because blocks are updated independently, the algorithm can occasionally produce artifacts or "seams" at the boundaries of the blocks, particularly when the underlying solution is very smooth.
Future research directions include the development of adaptive blocking strategies or overlapping blocks to mitigate these boundary artifacts. Additionally, extending this rigorous convergence analysis to non-linear ill-posed problems remains a significant open challenge in the field.
Summary updated