Stopping criterion for iterative regularization of large-scale ill-posed problems using the Picard parameter

Eitan Levin, Alexander Y. Meltzer

Abstract

We propose a new stopping criterion for Krylov subspace iterative regularization of large-scale ill-posed inverse problems. Our stopping criterion accurately filters the data using a generalization of the Picard parameter that was originally introduced for direct regularization of small-scale problems. In the one dimension we filter the data in the discrete Fourier transform (DFT) basis using the Picard parameter, which separates noise-dominated Fourier coefficients from the signal-dominated ones. For two-dimensional problems we propose a novel vectorization scheme of the Fourier coefficients of the data based on the Kronecker product structure of the two-dimensional DFT matrix, which effectively reduces the problem to one dimension. At each iteration we compute the distance between the data reconstructed from the iterated solution and the filtered data, terminating the iterations once this distance begins to increase or to level off. The accuracy and robustness of the proposed method is demonstrated by several numerical examples and a MATLAB-based implementation is provided.

Introduction

In computational imaging and signal processing, many tasks are modeled as ill-posed inverse problems of the form $Ax = b$, where $A$ is a large, ill-conditioned matrix representing a forward operator (like blurring), $b$ is the observed noisy data, and $x$ is the unknown sharp signal or image. Because $A$ is ill-conditioned, direct inversion is impossible as it would amplify the noise in $b$ to catastrophic levels.

Iterative solvers, such as the Golub-Kahan bidiagonalization (GKB) or LSQR, are commonly used for large-scale problems. These methods exhibit a phenomenon known as semi-convergence: during the early iterations, the solution improves as the algorithm captures the dominant, smooth components of the signal. However, as iterations continue, the algorithm begins to fit the high-frequency noise, causing the solution quality to degrade. Determining the optimal stopping point is critical but challenging.

The Data Filtering (DF) Stopping Criterion

The core of the proposed method is the "Data Filtering" (DF) criterion. It leverages the Discrete Picard Condition, which states that for a solution to exist, the coefficients of the data in the basis of the singular vectors of $A$ must decay faster than the singular values. In small-scale problems, one can use the Singular Value Decomposition (SVD) to identify the "Picard parameter"—the index where noise begins to dominate the signal.

For large-scale problems, computing the SVD is computationally prohibitive. The authors observe that for many common operators (like shift-invariant blurs), the Discrete Fourier Transform (DFT) basis serves as an excellent approximation of the SVD basis. By transforming the data $b$ into the frequency domain via DFT, the signal and noise can be separated.

The Picard Filter

In the frequency domain, the signal typically occupies low-frequency components, while white noise is spread uniformly across all frequencies. The Picard parameter identifies the cutoff frequency where the noise floor is reached. The authors use this to create a filtered version of the data, $b_{filt}$, which retains the signal-dominated components and discards the noise-dominated ones.

Hyperbolic Ordering in 2D

A significant contribution of this work is the treatment of 2D data (images). Standard frequency filtering often uses "elliptic" or circular ordering based on the distance from the DC component. However, the authors argue that for many image restoration problems, the underlying operators have a Kronecker product structure ($A = A_c \otimes A_r$).

To respect this structure, they propose hyperbolic ordering. This scheme vectorizes the 2D Fourier coefficients in a way that aligns with the decay properties of the singular values of the Kronecker-structured operator. This 1D representation allows for a more accurate estimation of the Picard parameter in 2D problems than traditional methods.

Implementation and Results

The stopping rule is defined by monitoring the distance between the reconstructed data at iteration $k$, $Ax^{(k)}$, and the filtered data $b_{filt}$. The algorithm terminates when this distance stops decreasing: $$k^* = \text{argmin}_k \|Ax^{(k)} - b_{filt}\|_2$$

Performance Benchmarks

The method was rigorously tested using the RestoreTools MATLAB toolbox on various benchmarks, including satellite, GaussianBlur, and AtmosphericBlur. The experiments covered noise levels ranging from 1% to 0.0001%.

The results demonstrate that the proposed "DF-h" (Data Filtering with hyperbolic ordering) method is highly robust:

  • Accuracy: It consistently stops closer to the theoretical optimal iteration (the point of minimum Mean-Square Deviation) compared to established methods like the L-curve, Normalized Cumulative Periodogram (NCP), or Weighted GCV (W-GCV).
  • Reliability: In cases where other methods failed to find a clear stopping point (e.g., the Text2 benchmark), the DF-h criterion remained stable and accurate.
  • Boundary Handling: By incorporating a "Periodic Plus Smooth" (PPS) decomposition, the method avoids artifacts caused by the DFT's assumption of periodicity, which is often violated at image boundaries.

Conclusion

The Picard-based Data Filtering criterion provides a powerful, parameter-free stopping rule for iterative regularization. By utilizing the DFT as a proxy for the SVD and introducing hyperbolic ordering for 2D data, the authors have developed a method that is both computationally efficient and more accurate than traditional heuristics. This approach ensures that iterative solvers "know when to quit," preventing noise contamination and ensuring high-quality reconstructions in large-scale inverse problems.

Summary updated

Abstract

We propose a new stopping criterion for Krylov subspace iterative regularization of large-scale ill-posed inverse problems. Our stopping criterion accurately filters the data using a generalization of the Picard parameter that was originally introduced for direct regularization of small-scale problems. In the one dimension we filter the data in the discrete Fourier transform (DFT) basis using the Picard parameter, which separates noise-dominated Fourier coefficients from the signal-dominated ones. For two-dimensional problems we propose a novel vectorization scheme of the Fourier coefficients of the data based on the Kronecker product structure of the two-dimensional DFT matrix, which effectively reduces the problem to one dimension. At each iteration we compute the distance between the data reconstructed from the iterated solution and the filtered data, terminating the iterations once this distance begins to increase or to level off. The accuracy and robustness of the proposed method is demonstrated by several numerical examples and a MATLAB-based implementation is provided.
BibTeX
@misc{levin2017stopping,
  author = {Eitan Levin and Alexander Y. Meltzer},
  title = {{Stopping criterion for iterative regularization of large-scale ill-posed problems using the Picard parameter}},
  year = {2017},
  eprint = {1707.04200},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1707.04200},
}
Figure