Randomized block coordinate descent method for linear ill-posed problems

Qinian Jin, Duo LiuarXiv 2024 · DOI · arXiv

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:

  1. 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."
  2. 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.
  3. 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

Abstract

Consider the linear ill-posed problems of the form $\sum_{i=1}^{b} A_i x_i =y$, where, for each $i$, $A_i$ is a bounded linear operator between two Hilbert spaces $X_i$ and ${\mathcal Y}$. When $b$ is huge, solving the problem by an iterative method using the full gradient at each iteration step is both time-consuming and memory insufficient. Although randomized block coordinate decent (RBCD) method has been shown to be an efficient method for well-posed large-scale optimization problems with a small amount of memory, there still lacks a convergence analysis on the RBCD method for solving ill-posed problems. In this paper, we investigate the convergence property of the RBCD method with noisy data under either {\it a priori} or {\it a posteriori} stopping rules. We prove that the RBCD method combined with an {\it a priori} stopping rule yields a sequence that converges weakly to a solution of the problem almost surely. We also consider the early stopping of the RBCD method and demonstrate that the discrepancy principle can terminate the iteration after finite many steps almost surely. For a class of ill-posed problems with special tensor product form, we obtain strong convergence results on the RBCD method. Furthermore, we consider incorporating the convex regularization terms into the RBCD method to enhance the detection of solution features. To illustrate the theory and the performance of the method, numerical simulations from the imaging modalities in computed tomography and compressive temporal imaging are reported.
BibTeX
@misc{jin2024randomized,
  author = {Qinian Jin and Duo Liu},
  title = {{Randomized block coordinate descent method for linear ill-posed problems}},
  year = {2024},
  eprint = {2405.13340},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2405.13340},
}
Figure