minTolIn
Inner tolerance principle to stop the primal-dual algorithm.
Contents
Syntax
ThetaiOut = minTolIn(ThetaiOut,pdaNv,iOut,FFq,seti) ThetaiOut = minTolIn(ThetaiOut,pdaNv,iOut,FFq,seti,dispDepth)
Description
ThetaiOut = minTolIn(ThetaiOut,pdaNv,iOut,FFq,seti) computes the inner tolerance ThetaiOut. See "More About" for details. ThetaiOut = minTolIn(ThetaiOut,pdaNv,iOut,FFq,seti,dispDepth) does the same but allows to control the displayed messages by dispDepth.
To use it in context of computational framework set seti.useTolIn = 1.
Example
See minPda.html to see the usage in computational framework.
Here we give a small example.
init;
seti.ThetaStart = 0.925 seti.ThetaMax = 0.95 seti.TolGamma = 0.90
ThetaiOut = seti.ThetaStart;
seti.nOut = 30; % maximal number of outer iterations
pdaNv = zeros(1,seti.nOut);
iOut = 1;
seti.incNb = 2; % number of transmitters seti.measNb = 5; % number of receivers
FFq = rand(seti.measNb, seti.incNb);
seti.tau = 2.5; seti.delta = 0.01; seti.FmeasDelta = rand(seti.measNb,seti.incNb);
seti.pNorm = 2; % pNorm..., see normws.m seti.dSMeas = 1; % see setMeasPnts.m
ThetaiOut = minTolIn(ThetaiOut,pdaNv,iOut,FFq,seti)
Input Arguments
- ThetaiOut : inner tolerance of last outer iteration
- pdaNv : numbers of inner iterations stored in a vector (size 1 x seti.nOut, where nOut is the maximal number of outer iterations)
- iOut : iteration number of outer iterations
- FFq = FFqMeas : scattered field evaluated on receivers positions (matrix of size seti.measNb x seti.incNb)
Parameters for inner tolerance, see Section "More About". We give values of parameters, which worked fine in [2].
- seti.ThetaStart = 0.925
- seti.ThetaMax = 0.95
- seti.TolGamma = 0.90
Other parameters in struct seti:
- seti.tau : Discrepancy principle stops at parameter tau . delta.
- seti.delta : relative noise level
- seti.FmeasDelta : scattered field at receivers positions (i.e. 'the data') (uScaRX = uTotRX - uIncRX, i.e. total field minus incident field) (complex matrix of size seti.measNb x seti.incNb)
Some more parameters in struct seti are given in the Example above.
Optional Input Argument
- dispDepth : Depth of displayed messages (0: no, 4 or greater: yes).
Output Arguments
- ThetaiOut : inner tolerance
More About
The primal-dual algorithm is the inner iteration in the computational framework. The inner tolerance principle is applied to stop this inner iteration within itself.
This method is described in paragraph "Stopping strategy 2" of Section 4.10 in [2] and bases on the inexact stopping rule for a Newton-like method in Chapter 7.5.3 in [1]. We give a brief introduction here.
Notation
: outer iteration number
: inner iteration number
: inner tolerance
Scheme
- Compute the quotient of linarized and non-linearized discrepancy, i.e.
.
- The non-linearized discrepancy is fixed to save computational time.
- The iteration is stopped if
for inner tolerance
.
Algorithm: Compute inner tolerance
- Choose
,
, and
.
- Auxiliary tolerances for
:
- Auxiliary tolerances for
:
With notation: and
: number of steps in inner iteration for the two previous outer iterations.
- Compute inner tolerance:
References
- [1] Andreas Rieder. Keine Probleme mit Inversen Problemen. Vieweg, Wiesbaden, 2003. URL: https://doi.org/10.1007/978-3-322-80234-7.
- [2] Florian Bürgel, Kamil S. Kazimierski, and Armin Lechleiter. A sparsity regularization and total variation based computational framework for the inverse medium problem in scattering. Journal of Computational Physics, 339:1-30, 2017. URL: https://doi.org/10.1016/j.jcp.2017.03.011.
See Also
Code
function ThetaiOut = minTolIn(ThetaiOut,pdaNv,iOut,FFq,seti,varargin) if nargin == 6 dispDepth = varargin{1}; else dispDepth = 0; end seti.useTolInFix = 0; % default: 0 % Do not use option tolInFix because it needs more outer iterations... if seti.useTolInFix ThetaiOut = seti.ThetaStart; else ThetaMax = seti.ThetaMax; gamma = seti.TolGamma; % Compute help tolerances \hat{Theta}_i = ThetaHati if iOut > 2 if pdaNv(iOut-1) >= pdaNv(iOut-2) ThetaHati = 1-pdaNv(iOut-2)/pdaNv(iOut-1)*(1-ThetaiOut); else ThetaHati = gamma*ThetaiOut; end else ThetaHati = seti.ThetaStart; % start... end disPri = seti.tau*seti.delta/((normws(FFq-seti.FmeasDelta,seti)/normws(seti.FmeasDelta,seti))); ThetaiOut = ThetaMax*max(disPri,ThetaHati); % Rieder p. 265 %fprintf(' disPri = %1.2g | ThetaHati = %1.2g | ThetaiOut = %1.2g \n',disPri,ThetaHati,ThetaiOut) if dispDepth >= 4 disp('----- inner tolerance principle -----') if iOut > 2 fprintf('r_{n-1} = %g | r_{n-2} = %g',pdaNv(iOut-1),pdaNv(iOut-2)); end fprintf(' | ThetaHati = %g | disPri = %g | ThetaiOut = %g\n',ThetaHati,disPri,ThetaiOut); disp('-------------------------------------') end end end