Source-linked AI summary
A Semismooth Newton Method for Tikhonov Functionals with Sparsity Constraints
Roland Griesse, Dirk A. Lorenz
TL;DR
The paper studies regularization for noisy inverse problems whose solutions are sparse in a basis. It applies a semismooth Newton method to the optimality condition and reports local superlinear convergence, with experiments comparing favorably to existing approaches.
Problem
Noisy measurements can make inversion of Ku = f ill-posed, motivating regularization for stable recovery of quantities sparse in a countable basis.
Source: §1 · p. 2Method
The paper applies a semismooth Newton method to the necessary and sufficient optimality condition, using its slant differentiability.
Source: §1 · p. 1, §3.1 · p. 6Results
The method has proved local superlinear convergence, and numerical experiments report robustness to initial values and favorable computation time versus existing approaches.
Source: §1 · pp. 1–2Takeaways & Limitations
The active-set method solves linear systems on active coefficients, which experiments found reasonably small and well conditioned.
Source: §5 · p. 20The superlinear convergence neighborhood is unknown and may be small, and global convergence behavior remains to be investigated.
Source: §3.4 · p. 13
Abstract
from arXiv · showhide
Minimization problems in $\ell^2$ for Tikhonov functionals with sparsity constraints are considered. Sparsity of the solution is ensured by a weighted $\ell^1$ penalty term. The necessary and sufficient condition for optimality is shown to be slantly differentiable (Newton differentiable), hence a semismooth Newton method is applicable. Local superlinear convergence of this method is proved. Numerical examples are provided which show that our method compares favorably with existing approaches.
1 Introduction
The paper addresses noisy, ill-posed inverse problems where the quantity of interest is sparse in a countable basis. It proposes a semismooth Newton active-set method and reports local superlinear convergence and favorable numerical comparisons.
1 Introduction
- Iterated soft-thresholding converges linearly with a constant near one [2], while iterated hard-thresholding converges at O(n^-1/2).The paper notes that hard-thresholding can nevertheless be faster in practice in many cases.Source: §1 · p. 1
- The proposed active-set semismooth Newton method has proved local superlinear convergence in the infinite-dimensional setting.Its analysis uses slant differentiability.Source: §1 · p. 1
- Numerical experiments report robustness to the initial value and favorable computation time compared with existing approaches.The paper presents these as experimental findings.Source: §1 · p. 2
- Weighted ℓ1 regularization promotes solutions with few nonzero basis coefficients, and each weight regularizes its coefficient individually.The underlying inverse problem is unstable under noisy measurements, motivating a regularized formulation.Source: §1 · p. 2
2 Optimality Conditions
The section characterizes the minimizer through necessary and sufficient optimality conditions, including a soft-thresholding formulation. The resulting equation is the basis for the semismooth Newton method.
2 Optimality Conditions
- Soft-thresholding provides a compact formulation of the optimality condition characterizing the minimizer.The section introduces the weighted soft-thresholding map and then uses it to express the condition.Source: §2 · p. 3
- Injectivity of K yields a unique minimizer, which is finitely supported.The uniqueness follows from strict convexity and coercivity; finite support is stated as a corollary.Source: §2 · pp. 3–4
- The dual formulation imposes coordinatewise bounds |K*p|_k ≤ w_k on the dual variable.The dual variable is introduced specifically for this duality derivation.Source: §2 · p. 4
- Equation (11) is equivalent to the earlier optimality condition and is a semismooth equation in ℓ2 suitable for Newton's method.The paper contrasts this approach with interior-point regularization, which introduces additional nonlinearities.Source: §2 · p. 5
3 Semismooth Newton Method
The paper formulates the optimality condition as a semismooth equation and develops a Newton method that can also be viewed as an active-set method. It proves local superlinear convergence, while noting that the convergence neighborhood may be unknown and small.
3.1. Semismoothness of the optimality condition.
- The soft-thresholding operator is Newton differentiable from ℓp to ℓq for 1 ≤ p < ∞ and 1 ≤ q ≤ ∞, with a generalized derivative usable in the semismooth equation.The paper contrasts this with max/min operations, for which it reports no simple algorithmically exploitable slanting function in this setting.Source: §3 · p. 5, §3.1 · p. 6
3.2. Semismooth Newton method.
- The generalized Newton iteration uses the derivative from (14) and can be implemented as an active-set method; it is well-defined for initial values in ℓ2.After the first update, iterates are finitely supported, although K∗(Ku − f) may require truncation in practice.Source: §3.2 · p. 8
3.3. Active set method.
- The active-set formulation makes the next iterate depend on the current iterate only through its active set, so distinct iterates can produce the same update.The numerical examples use the residual norm as a stopping criterion because it drops suddenly before the minimizer is identified.Source: §3.3 · pp. 10–11
3.4. Local convergence of the semismooth Newton method.
- The generalized derivative is boundedly invertible; uniform boundedness of its inverse near the solution supports the local convergence proof.The proof uses the finite active set and invertibility of its restricted operator.Source: §3.4 · pp. 11–12
- Starting within a sufficiently small radius of the minimizer keeps the iterates in that neighborhood and yields superlinear convergence.The radius is not known and may be small; the authors say global convergence behavior needs further investigation.Source: §3.4 · pp. 12–13
- The method's local superlinear guarantee does not establish global convergence, and the neighborhood for that guarantee may be small and unknown.The authors report that γ is essential for achieving convergence from a bad initial guess in their numerical experiments.Source: §3.4 · p. 13
- The local convergence proof can be extended beyond injective K when every finite active-set submatrix M_AA is invertible, as under the stated FBI property.The paper relates FBI to the restricted isometry property used in compressed sensing.Source: §3.4 · p. 13
4 Numerical Results
The numerical experiments compare the semismooth Newton (SSN) method with existing approaches on inverse integration, Haar-basis deblurring, and compressive sampling. They report computational scaling and runtime comparisons, reconstruction results, and conditions affecting convergence.
4 Numerical Results
- The infinite-dimensional analysis yields SSN results independent of discretization size N, which the authors say means the algorithm scales well.The numerical comparison included GPSR, l1_ls, and iterative soft-thresholding.Source: §4 · p. 13, §4.1 · p. 14
4.1. Inverse integration.
- When noise increased with fixed wk=10^-5, iteration counts fell but CPU time rose because active sets grew; setting wk=δ produced comparably small CPU times across noise levels.Both tests used N=500; the coupled-parameter test used γ=5 · 10^5.Source: §4.1 · p. 14, Table 2 · p. 16, Table 3 · p. 16
- In the N=500 inverse-integration example, SSN reconstructed the solution after 11 iterations with residual norm 1.7 · 10^-10.Convergence was similar across several starting values, but too-small or too-large γ required starting close to the solution.Source: §4.1 · p. 14, Figure 1 · p. 15
- For inverse integration, empirical cost scaled as O(N^2.20) for SSN, O(N^2.71) for GPSR, O(N^2.70) for l1_ls, and O(N^2.15) for iterative thresholding.The constant hidden in the O notation was considerably smaller for SSN; the authors note scaling can vary across problem structures.Source: §4.1 · pp. 15–16, Figure 2 · p. 17, Table 4 · p. 17
4.2. Deblurring in a Haar basis.
- On Haar-basis deblurring, SSN converged in 0.3 seconds versus 0.5 seconds for GPSR and 5.3 seconds for l1_ls, despite taking six iterations.The reconstruction used 1024 Haar wavelets; the data were sparse in that basis, and ℓ1 reconstruction was much better than ℓ2 regularization.Source: §4.2 · p. 18, Figure 3 · p. 18
4.3. Compressive Sampling.
- For compressive sampling with N=8192, K=512, and 64 randomly placed ±1 spikes, SSN converged in six iterations and about 1.2 seconds with very small active sets.The stated condition is that active sets remain small enough: the restricted isometry property makes small-column submatrices injective.Source: §4.3 · p. 19, Figure 4 · p. 19, Table 6 · p. 20
5 Conclusion
The semismooth Newton method is a fast, easily implemented active set method for Tikhonov functionals with sparsity constraints. Experiments support favorable comparisons and robustness to initial values, while global convergence remains unresolved.
5 Conclusion
- Each iteration solves a linear system on active coefficients only, and these systems remain reasonably small and well conditioned.The method is presented as fast and easy to implement as an active set method.Source: §5 · p. 20
- Experiments indicate that the method compares favorably with state-of-the-art methods for ill-posed problems and is robust to initial values.The paper investigated only local convergence behavior.Source: §5 · p. 20
- Convergence is slow far from the minimizer and speeds up as the solution is approached; global convergence is not explained by the theory.The authors identify globalization, such as merit functions with line search or trust-region methods, as future work.Source: §5 · p. 20
Appendix
The appendix fragment mentions calculating conjugate (polar) functions and states where a supremum is attained.
Appendix
- The passage mentions calculating conjugate (polar) functions.It cites [12, Ch. I.4].Source: Appendix · p. 21
- The supremum is attained at h = p + f.Source: Appendix · p. 21