The Experts below are selected from a list of 327 Experts worldwide ranked by ideXlab platform
Raymond H Chan - One of the best experts on this subject based on the ideXlab platform.
-
parameter selection for total variation based image restoration using Discrepancy Principle
IEEE Transactions on Image Processing, 2012Co-Authors: Youwei Wen, Raymond H ChanAbstract:There are two key issues in successfully solving the image restoration problem: 1) estimation of the regularization parameter that balances data fidelity with the regularity of the solution and 2) development of efficient numerical techniques for computing the solution. In this paper, we derive a fast algorithm that simultaneously estimates the regularization parameter and restores the image. The new approach is based on the total-variation (TV) regularized strategy and Morozov's Discrepancy Principle. The TV norm is represented by the dual formulation that changes the minimization problem into a minimax problem. A proximal point method is developed to compute the saddle point of the minimax problem. By adjusting the regularization parameter adaptively in each iteration, the solution is guaranteed to satisfy the Discrepancy Principle. We will give the convergence proof of our algorithm and numerically show that it is better than some state-of-the-art methods in terms of both speed and accuracy.
Alexander G. Ramm - One of the best experts on this subject based on the ideXlab platform.
-
A Discrepancy Principle for equations with monotone continuous operators
arXiv: Numerical Analysis, 2009Co-Authors: Nguyen S. Hoang, Alexander G. RammAbstract:A Discrepancy Principle for solving nonlinear equations with monotone operators given noisy data is formulated. The existence and uniqueness of the corresponding regularization parameter $a(\delta)$ is proved. Convergence of the solution obtained by the Discrepancy Principle is justified. The results are obtained under natural assumptions on the nonlinear operator.
-
Dynamical Systems Method and Applications: Theoretical Developments and Numerical Examples - A Discrepancy Principle for equations with monotone continuous operators
Nonlinear Analysis: Theory Methods & Applications, 2009Co-Authors: Nguyen S. Hoang, Alexander G. RammAbstract:A Discrepancy Principle for solving nonlinear equations with monotone operators given noisy data is formulated. The existence and uniqueness of the corresponding regularization parameter a(δ) are proved. Convergence of the solution obtained by the Discrepancy Principle is justified. The results are obtained under natural assumptions on the nonlinear operator.
-
Discrepancy Principle for DSM II
Communications in Nonlinear Science and Numerical Simulation, 2008Co-Authors: Alexander G. RammAbstract:Abstract Let Ay = f, A is a linear operator in a Hilbert space H, y ⊥ N(A) ≔ {u : Au = 0}, R(A) ≔ {h : h = Au, u ∈ D(A)} is not closed, ∥fδ − f∥ ⩽ δ. Given fδ, one wants to construct uδ such that limδ→0∥uδ − y∥ = 0. Two versions of Discrepancy Principles for the DSM (dynamical systems method) for finding the stopping time and calculating the stable solution uδ to the original equation Ay = f are formulated and mathematically justified.
-
Discrepancy Principle for DSM
arXiv: Functional Analysis, 2006Co-Authors: Alexander G. RammAbstract:Let $Ay=f$, $A$ is a linear operator in a Hilbert space $H$, $y\perp N(A):=\{u:Au=0\}$, $R(A):=\{h:h=Au,u\in D(A)\}$ is not closed, $\|f_\delta-f\|\leq\delta$. Given $f_\delta$, one wants to construct $u_\delta$ such that $\lim_{\delta\to 0}\|u_\delta-y\|=0$. A version of the DSM (dynamical systems method) for finding $u_\delta$ consists of solving the problem \bee \dotu_\delta(t)=-u_\delta(t)+T^{-1}_{a(t)} A^\ast f_\delta, \quad u(0)=u_0, \eqno{(\ast)}\eee where $T:=A^\ast A$, $T_a:=T+aI$, and $a=a(t)>0$, $a(t)\searrow 0$ as $t\to\infty$ is suitably chosen. It is proved that $u_\delta:=u_\delta(t_\delta)$ has the property $\lim_{\delta\to 0}\|u_\delta-y\|=0$. Here the stopping time $t_\delta$ is defined by the Discrepancy Principle: \bee \eqno{(\ast\ast)}\eee $c\in(1,2)$ is a constant. Equation $(\ast)$ defines $t_\delta$ uniquely and $\lim_{\delta\to 0}t_\delta=\infty$. Another version of the Discrepancy Principle is also proved in this paper.
-
Discrepancy Principle for the dynamical systems method
Communications in Nonlinear Science and Numerical Simulation, 2005Co-Authors: Alexander G. RammAbstract:Assume that Au=f is a solvable linear equation in a Hilbert space, ∥A∥<∞, and R(A) is not closed, so this problem is ill-posed. Here R(A) is the range of the linear operator A. A dynamical systems method for solving this problem, consists of solving the following Cauchy problem: u=−u+(B+ϵ(t))−1A∗f,u(0)=u0, where B:=A∗A, u:=du/dt, u0 is arbitrary, and ϵ(t)>0 is a continuously differentiable function, monotonically decaying to zero as t→∞. Ramm has proved [Commun Nonlin Sci Numer Simul 9(4) (2004) 383] that, for any u0, the Cauchy problem has a unique solution for all t>0, there exists y:=w(∞):=limt→∞u(t), Ay=f, and y is the unique minimal-norm solution to Au=f. If fδ is given, such that ∥f−fδ∥⩽δ, then uδ(t) is defined as the solution to the Cauchy problem with f replaced by fδ. The stopping time is defined as a number tδ such that limδ→0∥uδ(tδ)−y∥=0 and limδ→0tδ=∞. A Discrepancy Principle is proposed and proved in this paper. This Principle yields tδ as the unique solution to the equation: ∥A(B+ϵ(t))−1A∗fδ−fδ∥=δ, where it is assumed that ∥fδ∥>δ and fδ⊥N(A∗). The last assumption is removed, and if it does not hold, then the right-hand side of the above equation is replaced by Cδ, where C=const>1, and one assumes that ∥fδ∥>Cδ. For nonlinear monotone A a Discrepancy Principle is formulated and justified.
Youwei Wen - One of the best experts on this subject based on the ideXlab platform.
-
parameter selection for total variation based image restoration using Discrepancy Principle
IEEE Transactions on Image Processing, 2012Co-Authors: Youwei Wen, Raymond H ChanAbstract:There are two key issues in successfully solving the image restoration problem: 1) estimation of the regularization parameter that balances data fidelity with the regularity of the solution and 2) development of efficient numerical techniques for computing the solution. In this paper, we derive a fast algorithm that simultaneously estimates the regularization parameter and restores the image. The new approach is based on the total-variation (TV) regularized strategy and Morozov's Discrepancy Principle. The TV norm is represented by the dual formulation that changes the minimization problem into a minimax problem. A proximal point method is developed to compute the saddle point of the minimax problem. By adjusting the regularization parameter adaptively in each iteration, the solution is guaranteed to satisfy the Discrepancy Principle. We will give the convergence proof of our algorithm and numerically show that it is better than some state-of-the-art methods in terms of both speed and accuracy.
Alain Celisse - One of the best experts on this subject based on the ideXlab platform.
-
Minimum Discrepancy Principle strategy for choosing k in k-NN regression.
arXiv: Machine Learning, 2020Co-Authors: Yaroslav Averyanov, Alain CelisseAbstract:This paper presents a novel data-driven strategy to choose the hyperparameter $k$ in the $k$-NN regression estimator. We treat the problem of choosing the hyperparameter as an iterative procedure (over $k$) and propose using an easily implemented in practice strategy based on the idea of early stopping and the minimum Discrepancy Principle. This estimation strategy is proven to be minimax optimal, under the fixed-design assumption on covariates, over different smoothness function classes, for instance, the Lipschitz functions class on a bounded domain. After that, the novel strategy shows consistent simulations results on artificial and real-world data sets in comparison to other model selection strategies such as the Hold-out method.
-
Analyzing the Discrepancy Principle for kernelized spectral filter learning algorithms
2020Co-Authors: Alain Celisse, Martin WahlAbstract:We investigate the construction of early stopping rules in the non-parametric regression problem where iterative learning algorithms are used and the optimal iteration number is unknown. More precisely, we study the Discrepancy Principle, as well as modifications based on smoothed residuals, for kernelized spectral filter learning algorithms including gradient descent. Our main theoretical bounds are oracle inequalities established for the empirical estimation error (fixed design), and for the prediction error (random design). From these finite-sample bounds it follows that the classical Discrepancy Principle is statistically adaptive for slow rates occurring in the hard learning scenario, while the smoothed Discrepancy Principles are adaptive over ranges of faster rates (resp. higher smoothness parameters). Our approach relies on deviation inequalities for the stopping rules in the fixed design setting, combined with change-of-norm arguments to deal with the random design setting.
-
Smoothed Discrepancy Principle as an early stopping rule in RKHS
2019Co-Authors: Yaroslav Averyanov, Alain CelisseAbstract:In this paper we work on the estimation of a regression function that belongs to a polynomial decay reproducing kernel Hilbert space (RKHS). We describe spectral filter framework for our estimator that allows us to deal with several iterative algorithms: gradient descent, Tikhonov regularization, etc. The main goal of the paper is to propose a new early stopping rule by introducing smoothing parameter for empirical risk of the estimator in order to improve the previous results [1] on Discrepancy Principle. Theoretical justifications as well as simulations experiments for the proposed rule are provided.
Ulrich Tautenhahn - One of the best experts on this subject based on the ideXlab platform.
-
Implicit iteration methods in Hilbert scales under general smoothness conditions
Inverse Problems, 2011Co-Authors: Qinian Jin, Ulrich TautenhahnAbstract:For solving linear ill-posed problems, regularization methods are required when the right-hand side is with some noise. In this paper regularized solutions are obtained by implicit iteration methods in Hilbert scales. By exploiting operator monotonicity of certain functions and interpolation techniques in variable Hilbert scales, we study these methods under general smoothness conditions. Order optimal error bounds are given in case the regularization parameter is chosen either a priori or a posteriori by the Discrepancy Principle. For realizing the Discrepancy Principle, some fast algorithm is proposed which is based on Newton's method applied to some properly transformed equations.
-
on the generalized Discrepancy Principle for tikhonov regularization in hilbert scales
Journal of Integral Equations and Applications, 2010Co-Authors: Sergei V Pereverzev, Y Shao, Ulrich TautenhahnAbstract:For solving linear ill-posed problems regularization methods are required when the right hand side and the operator are with some noise. In the present paper regularized solutions are obtained by Tikhonov regularization in Hilbert scales and the regularization parameter is chosen by the generalized Discrepancy Principle. Under certain smoothness assumptions we provide order optimal error bounds that characterize the accuracy of the regularized solution. It appears that for getting small error bounds a proper scaling of the penalizing operator B is required. For the computation of the regularization parameter fast algorithms of Newton type are constructed which are based on special transformations. These algorithms are globally and monotonically convergent. The results extend earlier results where the problem operator is exactly given. Some of our theoretical results are illustrated by numerical experiments.
-
On the Discrepancy Principle for some Newton type methods for solving nonlinear inverse problems
Numerische Mathematik, 2009Co-Authors: Ulrich TautenhahnAbstract:We consider the computation of stable approximations to the exact solution $${x^\dagger}$$ of nonlinear ill-posed inverse problems F ( x ) = y with nonlinear operators F : X → Y between two Hilbert spaces X and Y by the Newton type methods $$x_{k+1}^{\delta}=x_{0}-g_{\alpha_{k}}\left(F'(x_{k}^{\delta})^*F'(x_{k}^{\delta})\right) F'(x_{k}^{\delta})^*\left(F(x_{k}^{\delta})-y^{\delta}-F'(x_{k}^{\delta})(x_{k}^{\delta}-x_{0})\right)$$ in the case that only available data is a noise $${y^\delta}$$ of y satisfying $${\|y^\delta - y\| \le \delta}$$ with a given small noise level $${\delta > 0}$$ . We terminate the iteration by the Discrepancy Principle in which the stopping index $${k_\delta}$$ is determined as the first integer such that $$\|F(x_{k_\delta}^{\delta})-y^{\delta}\|\le \tau \delta < \|F(x_{k}^{\delta})-y^{\delta}\|, \quad 0\le k < k_{\delta}$$ with a given number τ > 1. Under certain conditions on { α _ k }, { g _ α } and F , we prove that $${x_{k_\delta}^{\delta}}$$ converges to $${x^\dagger}$$ as $${\delta \rightarrow 0}$$ and establish various order optimal convergence rate results. It is remarkable that we even can show the order optimality under merely the Lipschitz condition on the Fréchet derivative F ′ of F if $${x_{0} - x^\dagger}$$ is smooth enough.
-
On the Discrepancy Principle for some Newton type methods for solving nonlinear inverse problems
Numerische Mathematik, 2008Co-Authors: Qinian Jin, Ulrich TautenhahnAbstract:We consider the computation of stable approximations to the exact solution $${x^\dagger}$$of nonlinear ill-posed inverse problems F(x) = y with nonlinear operators F : X → Y between two Hilbert spaces X and Y by the Newton type methods $$x_{k+1}^{\delta}=x_{0}-g_{\alpha_{k}}\left(F'(x_{k}^{\delta})^*F'(x_{k}^{\delta})\right) F'(x_{k}^{\delta})^*\left(F(x_{k}^{\delta})-y^{\delta}-F'(x_{k}^{\delta})(x_{k}^{\delta}-x_{0})\right)$$of y satisfying $${\|y^\delta - y\| \le \delta}$$with a given small noise level $${\delta > 0}$$. We terminate the iteration by the Discrepancy Principle in which the stopping index $${k_\delta}$$ is determined as the first integer such that $$\|F(x_{k_\delta}^{\delta})-y^{\delta}\|\le \tau \delta < \|F(x_{k}^{\delta})-y^{\delta}\|, \quad 0\le k < k_{\delta}$$converges to $${x^\dagger}$$as $${\delta \rightarrow 0}$$and establish various order optimal convergence rate results. It is remarkable that we even can show the order optimality under merely the Lipschitz condition on the Frechet derivative F′ of F if $${x_{0} - x^\dagger}$$ is smooth enough.
-
On the Discrepancy Principle for some Newton type methods for solving nonlinear inverse problems
arXiv: Numerical Analysis, 2008Co-Authors: Qinian Jin, Ulrich TautenhahnAbstract:We consider the computation of stable approximations to the exact solution $x^\dag$ of nonlinear ill-posed inverse problems $F(x)=y$ with nonlinear operators $F:X\to Y$ between two Hilbert spaces $X$ and $Y$ by the Newton type methods $$ x_{k+1}^\delta=x_0-g_{\alpha_k} (F'(x_k^\delta)^*F'(x_k^\delta)) F'(x_k^\delta)^* (F(x_k^\delta)-y^\delta-F'(x_k^\delta)(x_k^\delta-x_0)) $$ in the case that only available data is a noise $y^\delta$ of $y$ satisfying $\|y^\delta-y\|\le \delta$ with a given small noise level $\delta>0$. We terminate the iteration by the Discrepancy Principle in which the stopping index $k_\delta$ is determined as the first integer such that $$ \|F(x_{k_\delta}^\delta)-y^\delta\|\le \tau \delta 1$. Under certain conditions on $\{\alpha_k\}$, $\{g_\alpha\}$ and $F$, we prove that $x_{k_\delta}^\delta$ converges to $x^\dag$ as $\delta\to 0$ and establish various order optimal convergence rate results. It is remarkable that we even can show the order optimality under merely the Lipschitz condition on the Fr\'{e}chet derivative $F'$ of $F$ if $x_0-x^\dag$ is smooth enough.