WorksMathematics
Stochastic Multilevel Sampling for Inverse Problems via Coarse-Space Identifiability
Abstract
Sampling only part of the data reduces the cost of each iteration in an inverse problem, but can make reconstruction updates unreliable. We study stochastic multilevel sampling, which computes updates on a coarse-to-fine hierarchy of correction spaces. The guiding idea is that a small sample may support a reliable coarse-grid update even when it provides insufficient information for a fine-grid update. For quadratic objectives, we identify conditions under which corrections computed from sampled data decrease the full-data objective. In small-batch experiments with computed tomography and periodic deblurring, the stochastic multilevel method improves reconstruction accuracy over matched single-level methods. In an increasingly ill-conditioned CT refinement with a fixed number of projection angles, the single-level error increases as the image dimension grows, whereas a deep hierarchy maintains or improves accuracy and outperforms full-data single-level optimization at the same number of forward and adjoint applications. The gains persist across the tested local solvers and strengthen with deeper hierarchies. A separate known-probe ptychography study provides complementary evidence for the benefit of hierarchical corrections for nonlinear inverse problems.
Introduction
Large inverse problems are often expressed as sums of many data terms, such as rays in computed tomography (CT), pixels in an image-deblurring model, or scan positions in ptychography. Using only a subset of these terms can substantially reduce the cost of an iteration [24, 1]. However, the resulting batch may not contain enough information to determine a stable update in the full solution space. This limitation is particularly important for ill-conditioned inverse problems with weakly observed directions, where a decrease in the sampled residual need not improve the reconstruction [4, 9].
The reliability of a sampled update depends not only on the number of sampled data terms, but also on the space in which the update is sought. A small batch may be inadequate for a high-dimensional correction while still identifying a useful correction in a lower-dimensional, structured subspace. This observation suggests matching the dimension and geometry of the correction space to the information available in the sample. A hierarchy of spaces provides a natural way to do so, moving from inexpensive, strongly restricted corrections to more expressive fine-scale corrections as needed.
Classical multigrid provides the best-known example of such a hierarchy: it combines relaxation with coarse-grid correction to treat error components at different spatial scales [2, 33, 28]. Its usual interpretation, however, concerns the acceleration of a deterministic solve. Many inverse-problem operators are nonlocal, so the standard connection between spatial scale and error reduction may not carry over directly [17, 11]. Here we use the hierarchy for a different purpose. We ask whether restricting a correction to a coarse space can make a sampled inverse problem statistically more reliable, regardless of whether the same hierarchy accelerates the corresponding full-data solve.
To formalize this question, let denote a curvature model at the current iterate, let be its sampled counterpart, and let , with , define a correction space. Although may approximate poorly on , the restricted matrix may still approximate accurately. We refer to this property as coarse-space identifiability. The restriction acts on the unknown variables; it neither coarsens the observations nor changes the data-acquisition geometry.
In this study, we develop stochastic multilevel sampling around this principle. The method visits a prescribed hierarchy from coarse to fine, computing each correction by a gradient update or a short Krylov solve. A separate data batch then evaluates the feasible candidates through a projected Armijo line search. This independent line search limits reuse of the data that constructed the correction, while the central question remains whether the sampled model identifies a useful correction on the chosen space. The sampling distribution, batch size, and hierarchy remain fixed during a run.
Our analysis follows the correction through three stages. For quadratic objectives, an exact identity quantifies the best decrease attainable in a prescribed correction space and the loss caused by an inexact correction. Perturbation and concentration bounds then give sufficient conditions under which the minimizer of the sampled restricted problem decreases the full-data objective. Finally, an independent-batch bound gives a sufficient condition for accepting the projected candidate.
The numerical study first considers an increasingly ill-conditioned CT refinement in which the image dimension grows while the number of projection angles remains fixed. As the measurement-to-unknown ratio decreases, the single-level sampled method degrades, whereas the multilevel methods maintain or improve reconstruction accuracy. Broader sampled-row experiments for CT and periodic deblurring then show lower error than matched single-level controls after the same number of sampled rows or, separately, the same number of forward and adjoint applications. The improvement occurs for gradient and short Krylov corrections and generally increases with hierarchy depth. A uniform-sampling deblurring control further shows that nonuniform sampling is not required in this setting.
We also use known-probe MAGPIE ptychography [34] as a nonlinear scope study, motivated by earlier multigrid optimization for large-scale ptychographic phase retrieval [5]. The hierarchy produces lower reconstruction error than the single-level method after the same number of scan passes and, separately, after the same number of updates. The MAGPIE implementation does not use the sampling strategy or projected Armijo line search developed here. These experiments therefore demonstrate the usefulness of hierarchical correction spaces in a nonlinear problem, not the performance of the complete stochastic multilevel algorithm.
The remainder of the paper is organized as follows. § 2 positions the method relative to multilevel optimization and randomized least-squares methods, and § 3 defines the algorithm. § 4 develops the coarse-space analysis. § 5 presents the coarse-space diagnostics and reconstruction experiments, respectively, while § 6 reports the ptychography study. § 7 summarizes the conclusions and limitations.
Related methods and positioning
Multigrid and subspace correction organize updates through hierarchical spaces [2, 33]. MG/OPT and its trust-region and line-search variants extend this construction to optimization [16, 8, 31]. In particular, line-search multigrid combines direct and recursive directions with conditions ensuring descent [31]. Our method retains hierarchical corrections but constructs and evaluates them using separate sampled observations. Its additional question is statistical: does a batch represent the restricted model well enough to produce a useful correction?
Two recent methods combine multilevel structure with stochastic or geometric optimization. Marini, Porcelli, and Riccietti [15] use random regularized first-order models and hierarchical descriptions in variable or function space to obtain an almost-sure global convergence result for unconstrained optimization. Vanmaele, Elshiaty, and Petra [29] analyze deterministic geometric coarse models, including box-constrained tomography, for problems whose objective and gradient can be evaluated on each spatial grid. Our setting differs from both: we retain the same fine-grid inverse-problem objective and acquisition geometry, sample its measurement rows, and use the spatial hierarchy only to define correction spaces. The central issue is therefore whether sampled restricted gradients and curvature identify a useful correction in a prescribed subspace, rather than convergence of a stochastic regularized model or deterministic acceleration through grid-dependent objectives.
Stochastic gradients and variance reduction lower per-step cost and stabilize updates [24, 10, 1]. Randomized Kaczmarz and sketch-and-project methods similarly sample rows or constraints [25, 7, 18]. We retain row sampling but restrict corrections to hierarchical trial spaces. Stochastic line searches give complementary guarantees under probabilistically accurate estimates [12, 21, 30]; our analysis connects an independent-batch test of a realized multilevel direction to fine-objective descent.
Least-squares and Hessian sketching provide the closest theoretical tools [32, 22, 23, 3]. Concentration on relevant directions is already central to this literature; for example, iterative Hessian sketch guarantees depend on the geometry of a tangent cone and retain the full gradient while sketching curvature [22]. Here both the restricted gradient and curvature are sampled, and the prescribed hierarchy changes the trial space across a sweep. We apply standard concentration tools [27] to these spaces and study their effect on reconstruction quality at matched sample and operator counts. The contribution is the multilevel construction and its analysis and numerical validation, not a new general-purpose embedding bound. It is also distinct from multilevel Monte Carlo [6], which combines estimators across discretizations to reduce the variance of a scalar quantity.
The ptychography diagnostic connects to iterative engines [14, 13], maximum-likelihood solvers [26, 19], and multigrid optimization for large-scale ptychographic phase retrieval [5]. The nonlinear scope study uses MAGPIE [34]; we compare its surrogate hierarchy with the same surrogate update at single level.
Model and stochastic multilevel method
Inverse problems and sampled objectives
We consider a finite-sum inverse problem
where is a nonempty closed convex admissible set, and each term corresponds to an observation or observation block. The analysis and primary experiments use linear least squares,
with and observed data . We write for the Euclidean projection onto . Closed convexity makes this projection single valued and nonexpansive. The method does not require a particular constraint: taking recovers the unconstrained algorithm. In the CT and deblurring experiments we use , since the unknown represents a nonnegative density or intensity. This is a modeling choice rather than a property required by the multilevel construction. No explicit regularizer is used; inexact corrections, restricted spaces, and finite iteration counts provide implicit regularization. For the synthetic linear experiments with ground truth , we write , define the relative noise level by , and denote the known noise norm by .
Draw a batch independently with replacement from a law , where , and define
For least squares, the weighted rows
give , with unbiased gradient and Hessian. We use the fixed row-norm law . Zero operator rows are omitted from sampling because they contribute only a constant to the objective. Uniform gives the usual rescaling.
Hierarchy of correction spaces
Let prolong level- corrections to the finest grid, with . At an iterate , the restricted full and sampled objectives are
The hierarchy changes the correction space, not the observation geometry: ray, pixel, and scan-position indices retain their physical meaning. In the CT and deblurring experiments, we transfer from an image grid to the next coarser grid using the normalized stencil
In each coordinate, the four weights act at offsets from the stored coarse-grid anchor, so the stencil is centered at the intervening half-grid location. Its interior weights sum to one; entries outside the image are omitted at the boundary. Prolongation to the adjacent finer grid is times the transpose of this operation. The factor is a scaling convention and does not change the range of the prolongation. We use this choice throughout to define a concrete geometric hierarchy, but neither the algorithm nor the analysis is restricted to this stencil. Other prescribed transfer operators may be used to compose the adjacent prolongations and construct the correction spaces.
Stochastic multilevel cycle
A sweep visits levels . At level , we draw a correction batch and use its sampled residual and operator to compute a local correction using either one gradient step or a short zero-start LSQR solve [20]. Prolongation maps this correction to a fine-space direction . The correction batch also supplies the scale
with if the denominator vanishes. This value is used only to initialize a finite backtracking grid,
We use . The construction is invariant to positive rescaling of and fixes before validation data are drawn.
We then draw an independent line-search batch and evaluate the projected path
Starting from , we accept the first candidate that satisfies a projected Armijo condition on the line-search batch. If no candidate does, the iterate is unchanged. Thus projection is part of the search itself, rather than a modification applied after an unconstrained step has been selected. Degenerate directions leave the iterate unchanged. Subsection 4.3 analyzes the projected-candidate test.
Complete procedure
Algorithm 3.1 collects the complete procedure for a prescribed number of coarse-to-fine sweeps. The numerical experiments state their endpoint conventions separately.
Coarse-space mechanism
We analyze when a sampled coarse correction decreases a quadratic objective, without tying the mechanism to a particular local solver. Objective decrease is separate from reconstruction accuracy in noisy inverse problems; the experiments assess the latter. The results also apply to local quadratic models, but do not establish convergence for a nonlinear problem.
Exact and sampled coarse-space decrease
Let
and let be a coarse-space basis. We define
where and are the sampled Hessian and sampled gradient.
Lemma 4.1 (Exact coarse-space decrease). For the quadratic model (10), fix and a coarse basis such that is positive definite. Let and . Then every coarse correction satisfies
Algorithm 3.1 Stochastic multilevel sampling with a projected Armijo line search.
Require: ; local solver (gradient or LSQR()), Armijo constant , backtracking limit , and number of sweeps
for do
for do
draw correction rows ; form using (4)
,
compute , or by zero-start LSQR steps for ; set
if or then
else
end if
draw independent line-search rows ; form using (4)
initialize ,
for do
if and then
, ; break
end if
end for
end for
end for
return
Consequently, when , define the normalized coarse-decrease capture by
which may be negative. The correction is a descent step if and only if , equivalently .
Proof. Expanding and completing the square with gives (12). Division by gives (13).
The sampled Hessian and gradient are formed from the same rows, so their errors should not generally be treated as independent perturbations. The following result retains their coupling.
Theorem 4.2 (Coupled sampled-to-full transfer). *Suppose that and are positive definite, and let and . Define the coupled normal-
equation defect and sampled-Hessian stability factor by
Then
Consequently, is sufficient for the sampled correction to decrease the full objective.
Proof. The two normal equations give the exact relation
Therefore,
Substitution into (12) proves (15).
For , the corresponding normalized certificate is
Here measures how poorly the ideal full-data correction satisfies the sampled normal equations, while measures how strongly the sampled solve can amplify that defect. Their product bounds the distance between the sampled and ideal corrections.
Assumption 4.3 (Coarse-space concentration). The projected Hessian is positive definite. There is a constant such that the sampled projected Hessian obeys the relative spectral bound
and there is a constant such that the sampled projected gradient obeys
This assumption does not require to be positive definite on the full space; it excludes null directions only from the chosen correction space. For , write and . The corresponding relative sampled-Hessian error is
It is the smallest value of for which (17) holds on level .
Corollary 4.4 (Separate-error transfer bound). Under Theorem 4.3, the full objective decrease obtained by the sampled coarse correction satisfies
Proof. The concentration condition (17) implies
Moreover,
Substitution into the coupled bound (15) gives (20).
For , Corollary 4.4 gives
This lower bound is positive precisely when . Thus ensures that the sampled coarse Hessian is invertible, but does not by itself ensure descent. A nonpositive bound also does not imply that a realized correction fails. The separate-error bound follows from a triangle inequality applied to the coupled defect. It can therefore be much more conservative than (16), particularly when the Hessian and gradient errors formed from the same sampled rows cancel in the normal equations. For , we write the realized level- capture as .
Sample concentration on the hierarchy
For row-sampled least squares, let and be the coarse row and its leverage score, respectively. Since , the coarse-space coherence is [3]
For a sampling law , define the coarse importance mismatch
Uniform sampling gives , while the ideal coarse-leverage law on nonzero-leverage rows gives .
Proposition 4.5 (Coarse-space concentration). Fix a level , and draw rows independently with replacement from a law . Form the unbiased reweighted sampled Hessian
For any and , if
then the Hessian bound (17) of Theorem 4.3, with , holds with probability at least . For uniform iid sampling, . The diagnostics below use this with-replacement importance sampler.
Proof sketch. Write , so that and
For one random draw, the matrix has expectation and spectral norm at most . Matrix Chernoff [27] therefore gives
The right-hand side is at most under (23).
Proposition 4.6 (Projected-gradient concentration). Fix a level and an iterate . Let be the signed residual in the gradient convention, so that
For the same with-replacement importance sampler as in Proposition 4.5, define the unbiased projected-gradient estimator
Then
Consequently, with probability at least ,
Proof. Let , where . Then , and
For an average of independent copies of , the mean-square error is the single-sample variance divided by , which gives (24). Markov’s inequality gives (25).
Remark 4.7 (Inexact local solves). Theorem 4.2 concerns the exact minimizer of the sampled coarse problem. The gradient and short-LSQR corrections in Algorithm 3.1 are inexact, but their realized quality is still measured by (13). A short LSQR solve uses a Krylov space built from the same correction batch, so a concentration result for a fixed or independently chosen subspace does not apply directly. We therefore assess these corrections empirically.
Projected Armijo line search on an independent batch
The correction batch determines a direction, whereas the line-search batch tests the resulting projected candidates against independent data. This separation is needed because correction-batch decrease does not imply full-objective decrease. Condition on the iterate , correction batch , direction , and hence the finite set in (8). For each , define
Although need not be collinear with , it is fixed before the line-search batch is drawn. In particular, projection can move the realized displacement outside . The coarse-space theory therefore explains how the proposal is constructed, while the line-search test below controls the actual feasible displacement. Draw with replacement from , as in stochastic line-search methods [21, 30]. Writing , let
These estimators are conditionally unbiased, and the exact objective change is
Proposition 4.8 (Sufficient decrease for a projected candidate). Suppose that, simultaneously for every ,
with conditional probability at least . Then any candidate satisfying
strictly decreases the full objective with the same conditional probability.
Proof. Substitute (29) into (28). The bounds are simultaneous, so the conclusion remains valid when a candidate is selected from the finite set.
Scalar concentration and a union bound over can provide the radii in (29). In the experiments, starting from , they accept the first projected candidate for which
with , and halve the step otherwise. This is precisely . If no candidate satisfies the condition, rejection leaves the iterate unchanged. The rule evaluates the actual feasible update without reusing the batch that constructed the direction. It guarantees decrease of the sampled line-search objective; Proposition 4.8 gives the additional margin sufficient for decrease of the full objective. When projection is inactive, the rule reduces to an ordinary Armijo line search along .
Numerical results
The experiments address two questions. First, can a low-dimensional correction space be identified more reliably from a small sample than the fine space? Second, does that advantage translate into lower reconstruction error under the current projected Armijo line search? We study the first question through correction diagnostics and sufficient-decrease bounds, and the second through matched large-grid reconstruction experiments.
Sample identifiability and descent bounds
At , we measure curvature error, direction alignment, and realized decrease for sampled-subproblem solves. For each CT grid, we evaluate all correction spaces using the same iid row-norm batch and the inverse-probability scaling of subsection 3.1. Because small batches produce rank-deficient sampled Hessians, we use the ridge-stabilized diagnostic objective
We add to both the full and sampled Hessians and report the resulting curvature error and capture ratio . This ridge is used only for the diagnostics, not in the reconstruction algorithm.
Figure 1 compares corrections under the same batch on an , 30-angle problem with . At a 0.5% batch , the mean capture ratios on levels 1–3 are 0.319, 0.647, and 0.871; the fine and coarsest direction cosines are 0.360 and 0.858. Thus the coarsest space gives a better aligned correction in this regime. At larger batches, the coarse sampled curvature rises above the ridge floor and their corrections approach the corresponding full-data corrections. Capture and direction alignment measure the quality of a particular correction; establishing the entire coarse model additionally requires the concentration conditions.

Figure 1. Fine-versus-coarse correction diagnostics for and 30 projection angles, using identical iid importance-weighted batches at every level. Markers are means over twelve seeds, and bars show one standard deviation. (a) Ridge-model capture ratio; (b) minimum sampled curvature relative to the ridge floor; (c) cosine between sampled and full-data ridge corrections.
We next test whether the descent certificates remain informative on larger problems. We evaluate full-angle CT grids with , angles, and fixed 1% noise. The two deepest geometric correction spaces have dimensions 961 and 225, and we test batch fractions 0.5%, 5%, and 50% using six shared sampling seeds.
Table 1 reports how often the coupled lower bound is positive. A positive bound certifies that the sampled correction decreases the full-data ridge objective. At , the 0.5% batch contains 460 row draws. It certifies the 225-dimensional space in five of six trials but never certifies the 961-dimensional space, which has more unknown correction coefficients than sampled rows. Batches of 5% or larger certify both spaces in every trial. At , even the 0.5% batch contains 1847 draws and certifies both spaces in all six trials. Thus the experiment directly shows that a smaller correction space can be identified from fewer sampled rows. These ridge-quadratic diagnostics are evaluated only at the initial iterate and are not reconstruction results.
| batch | |||
| 255 | 0.5% | 5/6 | 0/6 |
| 255 | 5% | 6/6 | 6/6 |
| 255 | 50% | 6/6 | 6/6 |
| 511 | 0.5% | 6/6 | 6/6 |
| 511 | 5% | 6/6 | 6/6 |
| 511 | 50% | 6/6 | 6/6 |
Table 1. Empirical verification of the coupled descent bound (16). Entries give the number of positive bounds among six trials, evaluated at and using (32). Batch fractions count iid row draws, including repeats.
Dependence on the correction space
We also compare the geometric space with same-dimensional DCT low-pass, Haar-random, leading right-singular-vector, and full-data Krylov spaces; the complete definitions and results are given in subsection A.1. For CT, the geometric and DCT spaces have approximation defects 0.202 and 0.206 and capture ratios 0.975 and 0.976, respectively. The random space has approximation defect 0.970 and capture 0.646; the deblurring comparison shows the same qualitative separation.
Thus reliable sampling does not compensate for a correction space that poorly represents the solution. The comparison supports balancing approximation and sampling reliability, rather than assigning a universal advantage to geometric coarsening. These diagnostics use particular test images at , and the right-singular-vector and Krylov spaces are references rather than cost-matched algorithms.
Reconstruction with a projected Armijo line search
We first test whether the hierarchy remains effective as fixed-angle CT becomes increasingly ill-conditioned under grid refinement, and then test whether the same behavior persists across CT and deblurring, two grid sizes, two noise levels, three local solvers, and four batch fractions. The matched single-level control sets while retaining the same local solver, row-norm sampler, projected Armijo line search, and nonnegativity constraint. It is not a tuned full-data or hybrid-regularized Krylov solver, and no explicit regularizer is used.
We test three local solvers: gradient, LSQR(2), and LSQR(5). Each solver is run at single level, with the three-level geometric hierarchy, and with a deeper hierarchy ending on a grid. The latter has five levels at and six at . All variants retain the same row-norm sampling law and projected Armijo line search on an independent batch. The correction batch sets the step scale in (7); the line-search batch compares the resulting projected nonnegative candidates. A nonzero one-step LSQR correction is collinear with the sampled-gradient direction, and scaling the candidate grid by removes this scalar difference in exact arithmetic. The gradient control therefore tests whether hierarchy gains require the additional local Krylov steps.
To test the method beyond the fixed-angle CT sequence, we perform a matched sweep at for both CT and periodic deblurring. The CT problems use projection angles. The deblurring problems use periodic convolution with an isotropic Gaussian point-spread function whose standard deviation is pixels. Thus the blur width is fixed in pixel units as the grid grows; this is not a fixed-physical-width refinement. For both problems, we use relative noise levels .
We test iid importance-weighted batch fractions of 0.5%, 2%, 5%, and 10%. The 0.5% fraction is a small-batch stress test, not an optimized reconstruction parameter. For each configuration, six paired replicates redraw the measurement noise and sampled rows. Within a replicate, the noisy data are shared across local solvers and hierarchy choices, and the correction and line-search draws are paired by update index. The sweep contains 432 trajectories per batch fraction and 1728 trajectories in total.
To compare methods at matched computational effort, we use two endpoints. A row epoch is sampled rows, including the correction and line-search batches, and an operator epoch is scalar-row applications of the forward operator or its adjoint. We report the last completed update within twelve row epochs and, separately, within sixty operator epochs. The operator count includes inner LSQR applications, correction-batch residual and scale evaluations, and projected line-search evaluations; coarse-level applications receive no discount. We exclude setup, transfers, and diagnostic evaluations, so these endpoints normalize the principal operator applications rather than wall-clock time.
Increasingly ill-conditioned CT refinement.. We construct an increasingly ill-conditioned sequence by holding the number of CT projection angles at 128 as the image width increases through . The detector grid contains 182, 363, and 725 bins per angle, respectively, so the measurement-to-unknown ratios are , 0.71, and 0.35. Thus the number of measurements grows fourfold while the number of unknowns grows sixteenfold, and the two finer systems are underdetermined. We use 5% row batches, 5% relative noise, six paired replicates, and either gradient or LSQR(2) corrections. Figure 2 reports the last complete update within twenty-four normalized forward and adjoint applications.

Figure 2. Relative reconstruction error under CT grid refinement with 128 fixed projection angles. All cases use 5% relative noise, and the sampled methods use 5% iid row batches. Points are means over six paired replicates at the last complete update within twenty-four normalized forward and adjoint applications; bars show one standard error.
From to , the sampled single-level error increases by 32% for gradient corrections and 30% for LSQR(2). Over the same refinement, the deep-hierarchy error decreases by 12% and 21%, respectively, while the three-level error remains between 0.117 and 0.134. At , the deep hierarchy gives mean errors 0.1070 and 0.1028 for gradient and LSQR(2), compared with 0.2276 and 0.1937 for the corresponding full-data single-level controls. These reductions occur in all six paired replicates. The three grid sizes do not establish grid-independent convergence, but they show that the hierarchy prevents the loss of accuracy observed for the sampled single-level method as angular information becomes increasingly sparse relative to the image dimension. The comparison counts operator applications rather than wall-clock time.
Figure 3 shows example reconstructions for the problem with LSQR(2) corrections. In this example, the full-data single-level reconstruction is oversmoothed. Three levels reduce the artifacts in the sampled single-level reconstruction, and the deep hierarchy gives the lowest error while preserving the dominant structures.

Figure 3. Example fixed-angle CT reconstructions at with 128 projection angles, 5% relative noise, and LSQR(2) corrections. The upper row shows the reconstructions and their relative errors; the lower row shows the corresponding absolute errors.
Matched CT and deblurring comparisons.. At each of the four batch fractions, both hierarchies improve on the corresponding single-level kernel in every paired replicate of all 96 comparison groups: two problems, two sizes, two noise levels, three kernels, two endpoint definitions, and two hierarchy depths. At the headline 0.5% fraction, the deeper hierarchy also improves on three levels in every pair. The row and operator endpoints reuse the same trajectories; the six noise/sampling replicates, not the pooled endpoint count, are the replication units.
Table 2 displays the gradient control at and . At the operator-epoch endpoint, the paired single-level minus six-level error reductions are 0.07163 (0.00038) for CT and 0.03597 (0.00028) for deblurring, with one standard error in parentheses. Thus the hierarchy improves a direct-gradient baseline even when all inner operator applications are charged. Together with the LSQR(2) and LSQR(5) results, this establishes robustness to the tested local-solve depths. These values use the projected Armijo line search in Algorithm 3.1; in all four cases the hierarchy advantage remains after the feasible trial point is included in the line-search test.
| Problem | endpoint | single level | three levels | six levels |
| CT | row | 0.1080 (0.0002) | 0.0495 (0.0004) | 0.0357 (0.0004) |
| CT | operator | 0.1074 (0.0002) | 0.0495 (0.0004) | 0.0357 (0.0004) |
| Deblur | row | 0.0643 (0.0002) | 0.0465 (0.0003) | 0.0241 (0.0001) |
| Deblur | operator | 0.0597 (0.0003) | 0.0439 (0.0003) | 0.0237 (0.0001) |
Table 2. Mean relative reconstruction error for gradient corrections at , , and 0.5% iid row batches. Parentheses give one standard error over six paired replicates. CT uses 511 angles, and deblurring uses periodic Gaussian blur with pixels. Row and operator endpoints are the last complete updates within twelve row epochs and sixty forward/adjoint operator epochs, respectively.
The hierarchy gain is not specific to the 0.5% stress test. Figure 4 summarizes the matched operator-epoch comparisons at all four batch fractions. The gain remains positive at 2%, 5%, and 10% for both problems, grid sizes, hierarchy depths, noise levels, and local solvers. The 2% and 5% results are generally comparable to, and sometimes stronger than, those at 0.5%; at 10% the gain remains positive but is usually smaller. The distinction between the three-level and deeper hierarchies also narrows as the batch grows. The row-epoch endpoint gives the same qualitative conclusions.

Figure 4. Hierarchy gain versus correction-batch fraction at the sixty-operator-epoch endpoint. Gain is the percentage reduction in relative reconstruction error from the matched single-level method. Markers are means over two noise levels, three local solvers, and six paired replicates; shaded bands show one standard deviation across these 36 comparisons.
Nonlinear scope study: MAGPIE ptychography
To examine whether hierarchical correction spaces remain useful beyond linear least-squares problems, we consider known-probe ptychographic phase retrieval. We compare the MAGPIE surrogate hierarchy [34], motivated by earlier multigrid optimization for ptychography [5], with the same surrogate update run at a single level. This is a scope study of the hierarchy, not a test of the complete stochastic multilevel algorithm: MAGPIE does not use the sampling strategy or projected Armijo line search developed above.
The tests use an analytic MAGPIE-style surrogate with 49 raster scan positions and 50% overlap. For the spectral diagnostic, we use a 128 × 128 reference object and a 32 × 32 probe; the reconstruction tests use 256 × 256 and 512 × 512 objects with probe width . These measurements are nonlinear and spatially local: a scan batch covers part of the object rather than providing exchangeable global validation data. The linear theory in § 4 therefore does not apply directly.
Figure 5 identifies the phase modes on which the hierarchy acts. The band-restricted Rayleigh quotients in panel (a) show that low-frequency phase modes are weakly constrained, meaning that perturbations in these modes produce only small changes in the measured data. In contrast, low-frequency magnitude is strongly constrained. After removing the global phase null mode, the full-batch projected phase-space condition numbers are 5.3, 65, and on , , and phase grids, respectively; the coarser phase spaces are therefore better conditioned. For an aligned reconstruction , we define the pixelwise phase error as and its power in a Fourier frequency band as . Panel (b) reports the ratio , so values below one indicate less phase error in that band. The hierarchy gives its largest reduction in the same weakly constrained low-frequency band. This agreement supports the coarse phase-space interpretation, although it does not separate statistical stabilization from deterministic acceleration or update frequency.

Figure 5. Frequency-band diagnostics for the 128 × 128 MAGPIE reference problem with a 32 × 32 probe. (a) Normalized band-wise curvature of the object Gauss–Newton Hessian; smaller values indicate more weakly constrained modes. (b) Ratio of multilevel to single-level phase-error power; values below one favor the multilevel surrogate.
Large-object tests at and 512 provide a separate scope check. For noiseless intensity and , the Poisson-noise model draws and records . Thus the data have mean and variance , so larger means stronger noise; denotes noiseless data. Across the tested noise levels, scan batches, and both fixed-pass and fixed-update endpoints, both the five-level hierarchy and the deeper hierarchy—six levels at and seven at —improve single level in all three paired seeds. For , , and scan batch 8, the paired single-level minus seven-level error reductions are 0.0849 with 40 passes and 0.0724 with a fixed update count. The complete design and representative table are given in subsection A.2. These tests support the coarse phase-space interpretation, but they do not test the sampler or line search used in the linear experiments.
Discussion
The main finding is that a hierarchy can make sampled reconstruction more reliable when a local batch contains too little information for a stable fine-grid update. This behavior is clearest in the increasingly ill-conditioned CT refinement: the single-level method degrades as the image dimension grows, while the multilevel methods maintain or improve their accuracy.
The benefit is not tied to one local solver or one imaging model. It persists for gradient and short Krylov corrections, for CT and periodic deblurring, and under comparisons based on either sampled rows or forward and adjoint applications. Deeper hierarchies generally provide larger gains. The MAGPIE study suggests that the same correction-space principle can also be useful in a nonlinear inverse problem, although it does not test the complete algorithm developed for the linear setting.
The theory explains this behavior through coarse-space identifiability. A useful coarse space represents important components of the reconstruction error while reducing the number of directions that must be determined from a batch. A batch that is insufficient for a stable fine-grid correction may therefore still determine a reliable coarse correction. The independent projected line search then checks the proposed change on separate sampled data.
These experiments do not establish grid-independent convergence, a wall-clock speedup, or a universal advantage over full-data optimization. Instead, they support a practical principle: use sampled corrections in spaces that are both expressive enough to capture important errors and small enough to be identified from the available data.
Additional numerical comparisons
Correction-space comparison
We compare the geometric space with four spaces of the same dimension: Haar-random, Fourier/DCT low-pass, leading right singular vectors (RSV) of , and . Let be an orthonormal basis for a -dimensional test space , and set . We use the regularized coherence diagnostic
In orthonormal coordinates, we measure approximation defect , regularized coherence , curvature error , and capture , using (32) and identical iid importance-weighted batches.
The RSV and full-data Krylov spaces are references rather than cost-matched algorithms or tests of same-batch sampled LSQR (Theorem 4.7). The deblurring diagnostic observes a fixed half of the blurred pixels, unlike the full periodic-blur reconstruction tests in subsection 5.3.
Large-object MAGPIE reconstruction
We compare single level, the original five patch levels, and a deeper hierarchy with six levels at or seven at . For a noiseless intensity , the Poisson model draws and records , so and . We use for noiseless data. For each size, , and scan batch 2, 8, or 49, we use three paired data/sampling seeds. No independent line search is used. Relative object error is measured on the central region after complex-scale alignment.
| Subspace | approx. defect | ||||
| CT | geometric | 0.202 | 4.72 | 3.15 | 0.975 |
| low-pass (DCT) | 0.206 | 3.63 | 2.99 | 0.976 | |
| random | 0.970 | 3.69 | 2.70 | 0.646 | |
| top-RSV | 0.249 | 10.83 | 3.46 | 0.970 | |
| Krylov | 0.134 | 4.04 | 2.81 | 0.984 | |
| Deblur | geometric | 0.200 | 2.15 | 6.77 | 0.463 |
| low-pass (DCT) | 0.207 | 2.20 | 7.07 | 0.461 | |
| random | 0.972 | 1.71 | 6.88 | 0.368 | |
| top-RSV | 0.209 | 1.61 | 6.96 | 0.456 | |
| Krylov | 0.165 | 1.81 | 6.36 | 0.467 |
Table 3. Correction-space diagnostics at (level 3, ), averaged over five seeds. Curvature error uses , and ridge-model capture uses ; both are evaluated at . The full-data Krylov space is a diagnostic reference rather than the sampled Krylov space used by the reconstruction solver.
We compare two endpoints. 40 scan passes give 1000, 280, or 40 updates for batches 2, 8, or 49, respectively. The fixed-update control uses 200 updates for batches 2 and 49, and 203 for batch 8 because the implementation completes whole passes. Each single-level/multilevel comparison uses the same batch and endpoint.
| Endpoint | batch | single level | five levels | seven levels |
| 40 passes | 2 | 0.4599 | 0.3908 | 0.3701 |
| 8 | 0.4618 | 0.3962 | 0.3769 | |
| 49 | 0.4716 | 0.4298 | 0.4177 | |
| 200 updates | 2 | 0.4726 | 0.4464 | 0.4368 |
| 8 | 0.4652 | 0.4097 | 0.3927 | |
| 49 | 0.4558 | 0.3723 | 0.3573 |
Table 4. Mean aligned object relative error for known-probe ptychography at , probe width 128, and Poisson scale . Means use three paired data/sampling seeds; all standard errors are below . The upper block fixes 40 scan passes, and the lower block fixes 200 updates (203 at batch 8).
Batch-size rankings depend on the chosen endpoint; these are matched hierarchy comparisons, not evidence that smaller scan batches are intrinsically preferable.
References
References
- [1]L. Bottou, F. E. Curtis, and J. Nocedal, Optimization methods for large-scale machine learning, SIAM Review, 60 (2018), pp. 223–311.arxiv.org/abs/1606.04838
- [2]A. Brandt, Multi-level adaptive solutions to boundary-value problems, Mathematics of Computation, 31 (1977), pp. 333–390.DOI
- [3]P. Drineas, M. Magdon-Ismail, M. W. Mahoney, and D. P. Woodruff, Fast approximation of matrix coherence and statistical leverage, Journal of Machine Learning Research, 13 (2012), pp. 3475–3506.arxiv.org/abs/1109.3843
- [4]H. W. Engl, M. Hanke, and A. Neubauer, Regularization of Inverse Problems, Kluwer Academic Publishers, 1996.
- [5]S. W. Fung and Z. W. Di, Multigrid optimization for large-scale ptychographic phase retrieval, SIAM Journal on Imaging Sciences, 13 (2020), pp. 214–233, https://doi.org/10. 1137/18M1223915.
- [6]M. B. Giles, Multilevel Monte Carlo methods, Acta Numerica, 24 (2015), pp. 259–328.
- [7]R. M. Gower and P. Richtárik, Randomized iterative methods for linear systems, SIAM Journal on Matrix Analysis and Applications, 36 (2015), pp. 1660–1690.DOI
- [8]S. Gratton, A. Sartenar, and P. L. Toint, Recursive trust-region methods for multiscale nonlinear optimization, SIAM Journal on Optimization, 19 (2008), pp. 414–444.DOI
- [9]P. C. Hansen, Discrete Inverse Problems: Insight and Algorithms, SIAM, 2010.
- [10]R. Johnson and T. Zhang, Accelerating stochastic gradient descent using predictive variance reduction, in Advances in Neural Information Processing Systems (NeurIPS), vol. 26, 2013, pp. 315–323.
- [11]A. C. Kak and M. Slaney, Principles of Computerized Tomographic Imaging, Classics in Applied Mathematics, SIAM, 2001.
- [12]M. Mahsereci and P. Hennig, Probabilistic line searches for stochastic optimization, Journal of Machine Learning Research, 18 (2017), pp. 1–59.
- [13]A. Maiden, D. Johnson, and P. Li, Further improvements to the ptychographical iterative engine, Optica, 4 (2017), pp. 736–745.DOI
- [14]A. M. Maiden and J. M. Rodenburg, An improved ptychographical phase retrieval algorithm for diffractive imaging, Ultramicroscopy, 109 (2009), pp. 1256–1262.DOI
- [15]F. Marini, M. Porcelli, and E. Riccietti, A multilevel stochastic regularized first-order method with application to finite sum minimization, 2024, https://doi.org/10.48550/arXiv.2412.11630, https://arxiv.org/abs/2412.11630.
- [16]S. G. Nash, A multigrid approach to discretized optimization problems, Optimization Methods and Software, 14 (2000), pp. 99–116.DOI
- [17]F. Natterer, The Mathematics of Computerized Tomography, Classics in Applied Mathematics, SIAM, 2001.
- [18]D. Needell, N. Srebro, and R. Ward, Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm, Mathematical Programming, 155 (2016), pp. 549–573.arxiv.org/abs/1310.5715
- [19]M. Odstrčil, A. Menzel, and M. Guizar-Sicairos, Iterative least-squares solver for generalized maximum-likelihood ptychography, Optics Express, 26 (2018), pp. 3108–3123.DOI
- [20]C. C. Paige and M. A. Saunders, LSQR: An algorithm for sparse linear equations and sparse least squares, ACM Transactions on Mathematical Software, 8 (1982), pp. 43–71.DOI
- [21]C. Paquette and K. Scheinberg, A stochastic line search method with expected complexity analysis, SIAM Journal on Optimization, 30 (2020), pp. 349–376, https://doi.org/10.1137/18M1216250.
- [22]M. Pilanci and M. J. Wainwright, Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares, Journal of Machine Learning Research, 17 (2016), pp. 1–38.
- [23]M. Pilanci and M. J. Wainwright, Newton sketch: A near linear-time optimization algorithm with linear-quadratic convergence, SIAM Journal on Optimization, 27 (2017), pp. 205–245.
- [24]H. Robbins and S. Monro, A stochastic approximation method, The Annals of Mathematical Statistics, 22 (1951), pp. 400–407.
- [25]T. Strohmer and R. Vershynin, A randomized Kaczmarz algorithm with exponential convergence, Journal of Fourier Analysis and Applications, 15 (2009), pp. 262–278.arxiv.org/abs/math/0702226
- [26]P. Thibault and M. Guizar-Sicairos, Maximum-likelihood refinement for coherent diffractive imaging, New Journal of Physics, 14 (2012), p. 063004.DOI
- [27]J. A. Tropp, An introduction to matrix concentration inequalities, Foundations and Trends in Machine Learning, 8 (2015), pp. 1–230.arxiv.org/abs/1501.01571
- [28]U. Trottenberg, C. W. Oosterlee, and A. Schüller, Multigrid, Academic Press, 2001.
- [29]F. Vanmale, E. Elshatiy, and S. Petra, Multilevel optimization: Geometric coarse models and convergence analysis, 2025, https://doi.org/10.48550/arXiv.2505.11104, https://arxiv.org/abs/2505.11104.
- [30]S. Waswani, A. Mishkin, I. Laradji, M. Schmidt, G. Gidel, and S. Lacoste-Julien, Painless stochastic gradient: Interpolation, line-search, and convergence rates, in Advances in Neural Information Processing Systems, vol. 32, 2019.
- [31]Z. Wen and D. Goldfarb, A line search multigrid method for large-scale nonlinear optimization, SIAM Journal on Optimization, 20 (2009), pp. 1478–1503.DOI
- [32]D. P. Woodruff, Sketching as a tool for numerical linear algebra, Foundations and Trends in Theoretical Computer Science, 10 (2014), pp. 1–157.DOI
- [33]J. Xu, Iterative methods by space decomposition and subspace correction, SIAM Review, 34 (1992), pp. 581–613.DOI
- [34]B. Zhang, Q. Li, and Z. W. Di, MAGPIE: Multilevel-adaptive-guided solver for ptychographic phase retrieval, 2026, https://doi.org/10.48550/arXiv.2504.10118, https://arxiv.org/abs/2504.10118. Accepted for publication in SIAM Journal on Scientific Computing.