We develop a framework for reconstructing images that are sparse in an appropriate transform domain from polychromatic computed tomography (CT) measurements under the blind scenario where the material of the inspected object and incidentenergy spectrum are unknown. Assuming that the object that we wish to reconstruct consists of a single material, we obtain a parsimonious measurementmodel parameterization by changing the integral variable from photon energy to mass attenuation, which allows us to combine the variations brought by the unknown incident spectrum and mass attenuation into a single unknown massattenuation spectrum function; the resulting measurement equation has the Laplaceintegral form. The massattenuation spectrum is then expanded into basis functions using B splines of order one. We consider a Poisson noise model and establish conditions for biconvexity of the corresponding negative loglikelihood (NLL) function with respect to the densitymap and massattenuation spectrum parameters. We derive a blockcoordinate descent algorithm for constrained minimization of a penalized NLL objective function, where penalty terms ensure nonnegativity of the massattenuation spline coefficients and nonnegativity and gradientmap sparsity of the densitymap image, imposed using a convex totalvariation (TV) norm; the resulting objective function is biconvex. This algorithm alternates between a Nesterov’s proximalgradient (NPG) step and a limitedmemory BroydenFletcherGoldfarbShanno with box constraints (LBFGSB) iteration for updating the image and massattenuation spectrum parameters, respectively. We prove the KurdykaŁojasiewicz property of the objective function, which is important for establishing local convergence of blockcoordinate descent schemes in biconvex optimization problems. Our framework applies to other NLLs and signalsparsity penalties, such as lognormal NLL and ℓ₁ norm of 2D discrete wavelet transform (DWT) image coefficients. Numerical experiments
with simulated and real Xray CT data demonstrate the performance of the proposed scheme.
more »
« less
Minimizing L 1 over L 2 norms on the gradient
Abstract In this paper, we study the L 1 / L 2 minimization on the gradient for imaging applications. Several recent works have demonstrated that L 1 / L 2 is better than the L 1 norm when approximating the L 0 norm to promote sparsity. Consequently, we postulate that applying L 1 / L 2 on the gradient is better than the classic total variation (the L 1 norm on the gradient) to enforce the sparsity of the image gradient. Numerically, we design a specific splitting scheme, under which we can prove subsequential and global convergence for the alternating direction method of multipliers (ADMM) under certain conditions. Experimentally, we demonstrate visible improvements of L 1 / L 2 over L 1 and other nonconvex regularizations for image recovery from lowfrequency measurements and two medical applications of magnetic resonance imaging and computed tomography reconstruction. Finally, we reveal some empirical evidence on the superiority of L 1 / L 2 over L 1 when recovering piecewise constant signals from lowfrequency measurements to shed light on future works.
more »
« less
 NSFPAR ID:
 10349406
 Date Published:
 Journal Name:
 Inverse Problems
 Volume:
 38
 Issue:
 6
 ISSN:
 02665611
 Page Range / eLocation ID:
 065011
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric tspanner of ℳ if for every u,v ∈ X, δ(u,v) ≤ δ_G(u,v) ≤ t⋅ δ(u,v), where δ_G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s₁, …, s_n), where the points are presented one at a time (i.e., after i steps, we have seen S_i = {s₁, … , s_i}). The algorithm is allowed to add edges to the spanner when a new point arrives, however, it is not allowed to remove any edge from the spanner. The goal is to maintain a tspanner G_i for S_i for all i, while minimizing the number of edges, and their total weight. Under the L₂norm in ℝ^d for arbitrary constant d ∈ ℕ, we present an online (1+ε)spanner algorithm with competitive ratio O_d(ε^{d} log n), improving the previous bound of O_d(ε^{(d+1)}log n). Moreover, the spanner maintained by the algorithm has O_d(ε^{1d}log ε^{1})⋅ n edges, almost matching the (offline) optimal bound of O_d(ε^{1d})⋅ n. In the plane, a tighter analysis of the same algorithm provides an almost quadratic improvement of the competitive ratio to O(ε^{3/2}logε^{1}log n), by comparing the online spanner with an instanceoptimal spanner directly, bypassing the comparison to an MST (i.e., lightness). As a counterpart, we design a sequence of points that yields a Ω_d(ε^{d}) lower bound for the competitive ratio for online (1+ε)spanner algorithms in ℝ^d under the L₁norm. Then we turn our attention to online spanners in general metrics. Note that, it is not possible to obtain a spanner with stretch less than 3 with a subquadratic number of edges, even in the offline setting, for general metrics. We analyze an online version of the celebrated greedy spanner algorithm, dubbed ordered greedy. With stretch factor t = (2k1)(1+ε) for k ≥ 2 and ε ∈ (0,1), we show that it maintains a spanner with O(ε^{1}logε^{1})⋅ n^{1+1/k} edges and O(ε^{1}n^{1/k}log² n) lightness for a sequence of n points in a metric space. We show that these bounds cannot be significantly improved, by introducing an instance that achieves an Ω(1/k⋅ n^{1/k}) competitive ratio on both sparsity and lightness. Furthermore, we establish the tradeoff among stretch, number of edges and lightness for points in ultrametrics, showing that one can maintain a (2+ε)spanner for ultrametrics with O(ε^{1}logε^{1})⋅ n edges and O(ε^{2}) lightness.more » « less

Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric tspanner of ℳ if for every u,v ∈ X, δ(u,v) ≤ δ_G(u,v) ≤ t⋅ δ(u,v), where δ_G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s₁, …, s_n), where the points are presented one at a time (i.e., after i steps, we have seen S_i = {s₁, … , s_i}). The algorithm is allowed to add edges to the spanner when a new point arrives, however, it is not allowed to remove any edge from the spanner. The goal is to maintain a tspanner G_i for S_i for all i, while minimizing the number of edges, and their total weight. Under the L₂norm in ℝ^d for arbitrary constant d ∈ ℕ, we present an online (1+ε)spanner algorithm with competitive ratio O_d(ε^{d} log n), improving the previous bound of O_d(ε^{(d+1)}log n). Moreover, the spanner maintained by the algorithm has O_d(ε^{1d}log ε^{1})⋅ n edges, almost matching the (offline) optimal bound of O_d(ε^{1d})⋅ n. In the plane, a tighter analysis of the same algorithm provides an almost quadratic improvement of the competitive ratio to O(ε^{3/2}logε^{1}log n), by comparing the online spanner with an instanceoptimal spanner directly, bypassing the comparison to an MST (i.e., lightness). As a counterpart, we design a sequence of points that yields a Ω_d(ε^{d}) lower bound for the competitive ratio for online (1+ε)spanner algorithms in ℝ^d under the L₁norm. Then we turn our attention to online spanners in general metrics. Note that, it is not possible to obtain a spanner with stretch less than 3 with a subquadratic number of edges, even in the offline setting, for general metrics. We analyze an online version of the celebrated greedy spanner algorithm, dubbed ordered greedy. With stretch factor t = (2k1)(1+ε) for k ≥ 2 and ε ∈ (0,1), we show that it maintains a spanner with O(ε^{1}logε^{1})⋅ n^{1+1/k} edges and O(ε^{1}n^{1/k}log² n) lightness for a sequence of n points in a metric space. We show that these bounds cannot be significantly improved, by introducing an instance that achieves an Ω(1/k⋅ n^{1/k}) competitive ratio on both sparsity and lightness. Furthermore, we establish the tradeoff among stretch, number of edges and lightness for points in ultrametrics, showing that one can maintain a (2+ε)spanner for ultrametrics with O(ε^{1}logε^{1})⋅ n edges and O(ε^{2}) lightness.more » « less

null (Ed.)Deep neural networks give stateoftheart accuracy for reconstructing images from few and noisy measurements, a problem arising for example in accelerated magnetic resonance imaging (MRI). However, recent works have raised concerns that deeplearningbased image reconstruction methods are sensitive to perturbations and are less robust than traditional methods: Neural networks (i) may be sensitive to small, yet adversariallyselected perturbations, (ii) may perform poorly under distribution shifts, and (iii) may fail to recover small but important features in an image. In order to understand the sensitivity to such perturbations, in this work, we measure the robustness of different approaches for image reconstruction including trained and untrained neural networks as well as traditional sparsitybased methods. We find, contrary to prior works, that both trained and untrained methods are vulnerable to adversarial perturbations. Moreover, both trained and untrained methods tuned for a particular dataset suffer very similarly from distribution shifts. Finally, we demonstrate that an image reconstruction method that achieves higher reconstruction quality, also performs better in terms of accurately recovering fine details. Our results indicate that the stateoftheart deeplearningbased image reconstruction methods provide improved performance than traditional methods without compromising robustness.more » « less

We develop a sparse image reconstruction method for Poissondistributed polychromatic Xray computed tomography (CT) measurements under the blind scenario where the material of the inspected object and the incident energy spectrum are unknown. We employ our massattenuation spectrum parameterization of the noiseless measurements for singlematerial objects and express the massattenuation spectrum as a linear combination of Bspline basis functions of order one. A block coordinatedescent algorithm is developed for constrained minimization of a penalized Poisson negative loglikelihood (NLL) cost function, where constraints and penalty terms ensure nonnegativity of the spline coefficients and nonnegativity and sparsity of the densitymap image; the image sparsity is imposed using a convex totalvariation (TV) norm penalty term. This algorithm alternates between a Nesterov’s proximalgradient (NPG) step for estimating the densitymap image and a limitedmemory BroydenFletcherGoldfarbShanno with box constraints (LBFGSB) step for estimating the incidentspectrum parameters. We establish conditions for biconvexity of the penalized NLL objective function, which, if satisfied, ensures monotonicity of the NPGBFGS iteration. We also show that the penalized NLL objective satisfies the KurdykaŁojasiewicz property, which is important for establishing local convergence of blockcoordinate descent schemes in biconvex optimization problems. Simulation examples demonstrate the performance of the proposed scheme.more » « less