A FULL LIFE DATA QUALITY WORKFLOW RESEARCH AND PROJECT PRACTICE

With the development of technology and geospatial equipment, more and more work, particularly covering a big area survey and mapping work, are conducted with different worker and equipment, or heterogeneous time variation. With the traditional data quality focus on the geospatial data quality itself, which is not include the work files and organization. Facing the heterogeneous characteristics of geospatial data and work organization, a full life data quality workflow was proposed to manage and control geospatial data quality. The proposed workflow is extended to include the file preparation, quality evaluation, and quality calculation phrases. It is demonstrated in one real data quality project, which include vector data, raster data and other geospatial data covering 160 thousands square kilometers and 300 work zones finished by 8 teams. The usability and reliability were validated in our work. Corresponding author E-mail addresses: 397595381@qq.com (Wenchao Gao)

INTRODUCTION
Data quality is crucial for the reliability and usage of data, which provides benefit for many application and services such as urban planning, land sources and natural disaster management (Basiri et al., 2019;Birigazzi et al., 2019;Kitchin and McArdle, 2016;Li et al., 2020). As stated in many literature (Huang et al., 2019;Jing et al., 2019;Kilkenny and Robinson, 2018;Najafabadi et al., 2015), "garbage in, garbage out", which is a big challenge for various data. The poor data quality will lead to the bias decision or analysis result. The volunteered geographic information (VGI) data and government authorized data are facing this challenge. Since the born of VGI (Goodchild, 2007;Zhang and Zhou, 2018;Yamashita and Seto et al. 2019), as a crowdsourcing collected data, it impended the academic research and business. In the VGI research field, the data quality is a buzz word. Many works dedicated to this research topic, such as earth system science data quality management and control (Sun and Wang, 2010), reviewing on measures and indicators of VGI data quality (Antoniou and Skopeliti, 2015;Fonte and Antonio et al. 2017;Wu and Clarke et al. 2020) and challenge study on crowdsourced geospatial data quality (Basiri et al., 2019;Adhinugraha and Rahayu et al. 2020). These work focused on the data overall or relative data quality. The word "uncertainty" is well proper to descript its quality. That is, the different data accuracy may be allowed for neighbour spatial objects or the same area.
However, for the government authorized geospatial data, the absolute data quality is very important. Meanwhile, the same quality indicators are necessary thing for the whole data even if collected with different worker and equipment, or heterogeneous time variation. Therefore, for one geospatial data quality evaluation work covering a big area such as one or two states, how to manage and control data quality is a hard work in practice.
With the sharply development of information communication technology and internet application, the usage of geospatial data has been changed increasingly. Excepting for the professional users, it may be used by personal users for their interests with non-professional scenario. It is also possible used in many professional or non-professional software (Elshaw Thrall and Thrall, 1999;Goodchild, 1995;Devillers 2002). Geospatial data can provide services for decisionmaking and other system. Consequently, its quality is very crucial.
Generally, the data quality evaluation work is more like a working project without academic topic. In fact, how to organize the all procedures of work, data sampling method and data indicators are all including the research value. Therefore, in our work, facing the heterogeneous massive geospatial data collected by different workers and equipment at various time, a full life data evaluation workflow was proposed, and a praxis in one project was demonstrated in our work.
The remainder of this paper is structured as follows. In Section 2, the objectives of our work are introduced. Section 3 presents our contributions, a full life geospatial data evaluation workflow. The research application was shown in Section 4. Finally, Section 5 shows the simple result, furthermore provides some concluding remarks and proposes some future work.

OBJECTIVES
The objective of this paper is to provide a full life data evaluation workflow that support massive government authorized data quality control and management. This goal is The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Volume XLIII- B4-2021XXIV ISPRS Congress (2021 achieved based on the work preparing, key technologies validation, and the data itself quality evaluation. Finally, by a praxis on one project, the usability and reliability of this workflow was demonstrated.

Concept of Workflow
The proposed workflow under the guideline of data quality principle, "two-level data inspection, one-level data acceptance". For the two-level inspection, which is carried in the data procedure stages by work unit and department. This work is a kind of self-check by some criteria. The one-level acceptance is a third-party inspection of their all work, including geospatial, the organization of data collection, and the key technologies validation work. Our work is belonging to this one. From aforementioned description, we can see this work is a wide concept outside the geospatial data itself.

Organization inspection Key technologies inspection
Quality metadata inspection Spatial data quality inspection Evaluation calculation and report writing phase Evaluation phase Figure 1. the data quality evaluation workflow Figure 1 gives the proposed full life workflow. The workflow includes three phases as shown in Figure 1. For the preparation phase, the documents and files about the evaluation geospatial data were collected, about including project files and technological documents. The evaluation phase is the most important work, which covers all business work of evaluation. The data sampling, data accuracy calculation and other related works were conducted. The third phase is the data quality synthetic calculation and report writing work. In where, the calculation of data quality is almost based on the weighted calculated. For the weight of each element is decided by data type and experts' experience.
This assessment workflow is applied to a major provincial engineering project, including 1 project management unit, 1 project lead unit, and 8 production units. The data results include the surveying and mapping benchmark system (the buried and observed GNSS observation points, the secondclass levelling route with a length of about 2000 kilometres), the digital Orth-image (about 160,000 square kilometres), and the digital elevation model (about 160,000 square kilometres). Meters), terrain element data (about 300 survey areas).

Preparation
The evaluation preparation work includes three aspects: data collection, personnel organization and plan formulation.
(1) Data collection is the work of sorting out data sources for quality inspection. The required data includes, but is not limited to, organizational management documents, technical regulations, and quality management regulations. Based on these data, the inspectors can quickly understand the project background, progress, and related results to facilitate subsequent project evaluation.
(2) The determination of the technical plan is the core content of the preparation for quality inspection. The specific evaluation content and evaluation method should be included in the technical plan. For a certain inspection item, it is necessary to design the corresponding evaluation indicator and construct a table to record the inspection result.
(3) Personnel organization is the establishment of related work groups or institutions for quality inspection. The needs of personnel are mainly based on technical solutions to achieve a perfect match between personnel and work. After determining the personnel, carrying out targeted personnel training is also one of the very important tasks in personnel organization.

Organization Inspection
The purpose of organizational management evaluation is to investigate the organization and operation of the project. This work is mainly based on the organization and management documents collected in the early stage, related rules and regulations, task arrangements, equipment maintenance and other aspects. The method of work development is mainly to refine the specific content of the inspection items, establish evaluation indicators, and comprehensively analyze the project organization and management model and the operating mechanism of the organization by means of quantitative scoring. Through the above steps, we can evaluate the scientific, rationality and applicability of organization management.
A table is given below to show some of the specific content and indicators of the organizational structure inspection.

Inspecting Item
Item detail information and some indicators Organization 1. Whether an organization and management institution with clear responsibilities has been established; 2. Whether the management organization is operating effectively and performing its duties due diligence; 3. Whether the project organization unit has implemented its responsibilities in terms of implementation plan formulation, technical design preparation, quality management, results acceptance, results submission, and data archiving.

Management guidelines
1 Whether it has formulated management rules and regulations involving project management, technical management, safety production management, quality management, results inspection and acceptance, results submission, and data archiving; 2. Whether the established management rules and regulations can be applied to the needs of management during project implementation, and provide management system guarantee for the orderly and standardized implementation of the project.
Competitive mechanism 1. Whether a competition mechanism has been introduced in the task implementation; 2. Whether the contract has been signed with the bid-winning unit through government procurement methods such as bidding and bidding, specifying responsibilities, rights, and benefits.

Logistics support
Logistics support 1. Whether the equipment can meet the production needs of domestic and foreign industries; 2. Whether to carry out the calibration and appraisal of the equipment according to the requirements. Education and training 1. Whether the project participants have carried out training related to professional technology, production safety, confidentiality education, etc.; 2. Whether the production personnel have passed the relevant assessments, and have the qualifications and ability to work. Table 1. Organization inspection item

Key Technologies Inspection
Technical management evaluation is based on technical management documents, project design documents, professional design documents, data regulations, technical standards, and new process development records. Among them, key technology research and application demonstration reports are key documents, because these represent the advancement of technology and the applicability of applications. The purpose of this evaluation is to investigate the innovation and operation of technology, evaluate the scientific level of technology management, and evaluate the applicability of new technologies.
The technical evaluation work includes: (1) Check whether the project has established a technical management system by consulting relevant technical problem management documents and communicating on-site. In the implementation of the project, whether the technical management related work is effectively implemented, and whether the technical problem handling mechanism is effectively operating.
(2) Conduct interviews with production personnel by consulting technical materials such as formulated standards and technical regulations, project design documents, and professional technical design documents to assess whether actual production is carried out in accordance with standards and technical designs, and whether technical standards and technical designs are standardized, Complete, whether the approval procedure is complete.
(3) Evaluate whether the design and production process match, whether the new technology and new equipment are complete. These tasks are generally carried out by consulting technical documents, trial production reports, and on-site inspection of production processes.
(4) Through expert review opinions on the key technology of the project, watch the demonstration on the spot, and check whether the key technology research and promotion and application have been carried out in accordance with the overall design requirements. The detail contents for technological inspection are shown below in Table 2

Quality metadata inspection
Quality evaluation is an output evaluation. The quality assessment materials mainly come from the quality management document regulations, the quality inspection process, the approval form for the use of surveying and mapping results, the inspection record form for the results, and the data inspection report. The work is mainly to evaluate the scientific and rationality of the quality management system and the quality characteristics of the data by comparing quality inspection standards with production processes and data products. This work includes: (1) Check whether the contents of relevant quality management documents are complete, whether the formulation is standardized and reasonable, whether a quality assurance system has been established, and whether a quality management operation mechanism has been established.
(2) Check whether the table item settings are complete and reasonable, whether the records are complete, and whether the storage is standardized. This includes the meeting sign-in form, training personnel record form, surveying and mapping results use approval form, quality inspection record form, etc.
(3) Check whether the sampling ratio of inspections at all levels meets the requirements, whether the record content is complete and standardized, whether the quality problem description is clear, whether the score is reasonable, whether the inspection report is standardized, etc., conduct inspections to evaluate whether the quality management system is operating effectively. The detail contents for quality inspection are shown below in Table 3.

Items Content
Management manuals and other program files 1. Is the system management-related reference document information accurate, complete and applicable? 2. Are the formulated quality policy and quality objectives reasonable? 3. Is the quality policy documented? 4. Are the countermeasures for risks and opportunities correct and feasible? 5.Do the resources of the support system meet the management needs? 6. Are the contents of environment, safety (including data confidentiality), occupational health, etc. complete, scientific and applicable? 7. Is the quality assessment reference and process quality control standardized?
Quality assurance System 1. Has a quality management and quality issue responsibility mechanism been established? 2. Can it guide the effective operation of quality management and quality problem responsibility mechanisms? 3. Has a clear quality problem handling mechanism been formed? Quality management operation mechanism 1. Are the quality level responsibilities clear, without overlap or overlap? 2. Is the definition of the two-level inspection and acceptance system clear? 3.
Are inspection and acceptance responsibilities and objectives clear? 4. Is there a mechanism for handling unqualified results?
Record form and inspection record 1. Is the type of record form complete and applicable? 2. Is the setting of the record table items complete and reasonable to meet the characteristics of controllable, traceable, and convenient management? 3.Does the first-level inspection check ratio meet, and are the inspection contents and records complete? 4.Does the secondary inspection inspection ratio comply with the inspection content, whether the inspection content and records are complete, and whether the result quality evaluation and inspection report are standardized? 5. Is the acceptance inspection ratio consistent, whether the inspection content and records are complete, and whether the result quality evaluation and acceptance report are standardized? Table 3. Quality inspection content

Spatial data quality inspection
The quality evaluation of the results adopts a sampling inspection mode. Among the completed results of the project, the samples to be inspected shall be selected and quality inspections shall be carried out in accordance with the relevant standards and regulations of the current quality inspection of the results. At present, the sample extraction work is mainly implemented in accordance with the provisions of GB/T 24356-2009 "Quality Inspection and Acceptance of Surveying and Mapping Results" and GB/T 18316-2008 "Quality Inspection and Acceptance of Digital Surveying and Mapping Results". At the current stage, the result quality assessment work is mainly applied to several achievements such as surveying and mapping datum (geodetic datum, elevation datum), digital orthophoto data, digital elevation model data, and topographic element data. Quality elements are the key components in data quality inspection. For an instance, the quality elements in geodetic datum are listed in Table 4.

Dataset
This assessment involves a major provincial engineering project, with 1 project management unit, 1 project lead unit, and 8 production units. The data set involves a surveying and mapping benchmark system (40 GNSS B-level points and 30 C-level points that have been buried and observed, and a second-class level route with a length of about 2000 kilometres that has been observed), digital ortho photos (about 16 10,000 square kilometres), digital elevation model (about 160,000 square kilometres), topographic feature data (about 300 survey areas).

Result of data inspection
In terms of organizational structure, the organization has a sound organization, a sound management system, sophisticated technical equipment, strong logistics support, and significant effects of education and training. This earned an excellent score.
For the inspection of technical management, the data production unit has established a complete technical management system; the content is complete. The data producer has very well constructed standards and technical regulations that are in line with regional characteristics, which provides non-technical guarantees for data quality. The production process developed by the project can meet the needs of basic geographic information data update and application. In addition, the key technology of data production is forwardlooking, in line with the overall design requirements of the project, and has been promoted and applied in production. This earned an excellent score.
In the production of the data set, the project party has established a complete quality management system, which effectively guarantees the data quality. The file classification system of the data set is complete, the classification and content are standardized, all kinds of records are complete, and the preservation is standardized. This gets a good score. In summary, the data quality of this project meets the technical design requirements, and the overall quality of the results is excellent.

CONCLUSION
In our work, a full life data quality evaluation workflow was proposed. The usability and reliability of the workflow was validated through the praxis on one real project. The whole datasets include vector data, raster data and other geospatial data covering 160 thousands square kilometres and 300 work zones finished by 8 teams' collaboration work. The organization quality is evaluated by the ISO standard and domain specific files. For the data quality calculation, the weighted concept was adopted and the quality of dataset was evaluated. For the reliability of weigh for each element, we will continuous work on it in future.


extfieldsofstudy:
Computer Science
Engineering

text:
Interpolation of CT Projections by Exploiting Their Self-Similarity and Smoothness

As the medical usage of computed tomography (CT) continues to grow, the radiation dose should remain at a low level to reduce the health risks. Therefore, there is an increasing need for algorithms that can reconstruct high-quality images from low-dose scans. In this regard, most of the recent studies have focused on iterative reconstruction algorithms, and little attention has been paid to restoration of the projection measurements, i.e., the sinogram. In this paper, we propose a novel sinogram interpolation algorithm. The proposed algorithm exploits the self-similarity and smoothness of the sinogram. Sinogram self-similarity is modeled in terms of the similarity of small blocks extracted from stacked projections. The smoothness is modeled via second-order total variation. Experiments with simulated and real CT data show that sinogram interpolation with the proposed algorithm leads to a substantial improvement in the quality of the reconstructed image, especially on low-dose scans. The proposed method can result in a significant reduction in the number of projection measurements. This will reduce the radiation dose and also the amount of data that need to be stored or transmitted, if the reconstruction is to be performed in a remote site.

Introduction
There is a great interest in reducing the radiation dose in computed tomography (CT). In practice, this can be done by either lowering the x-ray photon current or reducing the number of projection measurements taken. However, reconstructing a diagnostically useful image from such noisy and/or undersampled measurements is very challenging. As a result, recent years have witnessed a substantial growth in research on more sophisticated image reconstruction and processing algorithms for CT. Most of the published research have focused on iterative reconstruction algorithms [21] [14] [16] or on image-domain denoising and restoration algorithms [7] [12] [5] [25] [23] [11]. Comparatively, many fewer studies have been reported on denoising [10] [15] [13], or otherwise improving [8], the CT projection measurements (i.e., the sinogram). In this paper, we propose a sinogram interpolation algorithm for cone-beam CT. Our algorithm exploits both the smoothness and the self-similarity of the sinogram. We apply the proposed algorithm on simulated and real CT scans and compare it with an algorithm that is based on learned dictionaries.

Materials and Methods
A schematic of the cone-beam CT and a sample sinogram of a brain phantom are shown in Figure 1(a). The variation of the photon flux incident on the detectors follows a Poisson distribution. However, after the logarithm transformation, the noise follows approximately a Gaussian distribution with signaldependent variance. Specifically, let us denote the true line integral of the attenuation coefficient along the line from the x-ray source to the detector indexed with (i, j) in the k th projection with y t (i, j, k). Then the noisy measurement We assume that only a portion of the desired projections have been directly measured and the rest are to be estimated (i.e., interpolated). Due to the lack of space and in order to simplify the presentation of the algorithm, we focus on the case depicted in Figure 1(b). Specifically, we assume that half of the n θ desired projection views have been measured and the remaining half are to be estimated. In other words, the measured sinogram is y n ∈ R nu×nv×n θ /2 and we would like to estimate the interpolated sinogram y ∈ R nu×nv×n θ . As we will explain later, even though our main goal is sinogram interpolation, the proposed algorithm also has an excellent denoising effect. Therefore, we estimate the full set of n θ projection views, not only the missing n θ /2 views.
We propose to estimate y by minimizing the following cost function: The first term in J is obtained simply by maximizing the log-likelihood of the measurements. In this term, M is a binary mask matrix that removes from y those projection views that have not been measured and W is a diagonal weight matrix whose diagonal elements are inversely proportional to the measurement variance. The regularization functions R s and R h will be explained below, and λ s and λ h are regularization parameters.

Regularization in terms of sinogram self-similarity, R s
In the past decade, patch-based models have emerged as one of the most powerful models in image processing. Much of the research on these models was inspired by the success of the non-local means (NLM) denoising algorithm [2]. Let us denote the noisy image with x = x 0 + w, where x 0 and w are the true image and the noise, respectively. We also denote the i th pixel of x with x(i) and a patch centered on x(i) with x[i]. NLM estimates the value of x 0 (i) as follows: where G a denotes a Gaussian kernel with bandwidth a and N is the total number of pixels. The intuition behind this algorithm is that patches that are similar must have similar pixels at their centers. This simple idea has led to some of the best image denoising algorithms and has produced state-of-the-art results in many other image processing applications as well. Many studies have suggested solving various types of inverse problems by introducing regularization terms that are motivated by the same idea [20,24]. Because this type of self-similarity is very abundant in sinogram (even more than in natural images, as can be seen in the sample sinogram in Figure 1(a)), we suggest a similar form for R s : where we have used simplified pixel index notation I = (i, j, k) and I = (i , j , k ). Computation of y * has a few differences with the basic NLM in (2). Firstly, we work with 3D blocks instead of 2D patches. We stack the 2D projections to form a 3D image, as shown in Figure 1(b), and work with small blocks of this image. This will allow us to exploit both the correlation between adjacent pixels within a projection as well as the correlation between pixels in adjacent projection views. Secondly, for computing y * (i, j, k), we first find a small number of blocks that are very similar to y[i, j, k] and use those blocks only, instead of all blocks in the image. In (3), Ω i,j,k denotes the indices of these blocks. Thirdly, unlike (2) where patch similarities in the same image are exploited, in (3) we use a second image, as shown in Figure 2. This second image, denoted with z in Equation (3) and Figure 2 is built by stacking the projections of the normal-dose (i.e., low-noise) scan of a similar object. For instance, this can be a normal-dose prior scan of the same patient or of a different patient. Our experience shows that with a proper choice of z, this approach works much better than finding similar blocks from the same noisy scan. Therefore, computation of R s requires that for each pixel y(i, j, k) we find a set of blocks sufficiently similar to y[i, j, k] in z. We use the Generalized PatchMatch algorithm [1] for this purpose. We should also note that in finding similar blocks and in computing the block differences in (3), we only include the pixels from projections that have been directly measured. Block matching between the noisy scan to be restored y and the high-dose reference scan z.

Regularization in terms of sinogram smoothness, R h
An important characteristic of sinogram is its smoothness. We model this smoothness via the 1 norm of the Hessian of the sinogram. This is a generalization of the 1 norm of the gradient, also known as total variation (TV). TV is a good model for piecewise-constant images, but for smooth signals such as sinogram, it leads to staircase artifacts and higher-order differentials need to be considered [18]. Therefore, we suggest the following form for R h : In other words, we compute the 2D Hessians in the three orthogonal planes and add their 1 norms. We compute |∇ 2 uv y(i, j, k)| as: where Ds are second-order difference operators. Expressions for |∇ 2 vθ y(i, j, k)| and |∇ 2 θu y(i, j, k)| are very similar.

Optimization algorithm
The proposed cost function has this form: where we have dropped the pixel indices to simplify the expressions. An estimate of the interpolated (and denoised) projections is obtained as a minimizer of J(y).
To perform this minimization, we use the split Bregman iterative algorithm [6]. The split Bregman method first converts the unconstrained optimization problem of minimizing J(y) into a constrained problem: subject to: f = y, g 1 = ∇ 2 uv y, g 2 = ∇ 2 vθ y, g 3 = ∇ 2 θu y This constrained optimization problem is solved via Bregman iteration: In this algorithm, µ i are algorithm parameters and b i are auxiliary variables. The advantage of this reformulation is that the above minimization problem can be split into five smaller problems, one for each of the five variables that can be solved more easily. Minimization with respect to f has a simple closed-form solution. Minimizations with respect to g 1 , g 2 , and g 3 also have simple softthresholding solutions [18]. Minimization with respect to y is more difficult. We solve this optimization by considering each of the three Hessian terms in turn, each of which can be approximately solved using the Gauss-Seidel method. The regularization parameters λ s and λ h influence the recovered solution, whereas µ 1 and µ 2 influence the convergence speed. A study of the effect of these parameters is beyond the limits of this paper. A discussion of the role of these parameters for image restoration with second-order TV can be found in [19,18]. In our experiments we used λ h = 0.0001, µ 1 = µ 2 = 0.001, and λ s = 1.

Results and Discussion
As we mentioned above, unlike the iterative reconstruction methods that aim at reconstructing a high-quality image from undersampled projections, our goal is to estimate the "missing" projections. Therefore, in all of the experiments reported here we used the FDK algorithm for image reconstruction [4] [9]. We compare our algorithm with the dictionary-based sinogram interpolation method proposed in [17], which was shown to be better than spline interpolation.

Experiment with simulated data
We first applied our algorithm on scans simulated from a brain phantom, which we obtained from the BrainWeb database [3]. We simulated n θ projections from this phantom, for two values of n θ = 1440 and 960. For each n θ , we first reconstructed the image of the phantom from the full set of n θ projections and from n θ /2 projections; we denote these images with x n θ and x n θ /2 , respectively. We then applied the proposed algorithm and the dictionary-based interpolation algorithm to interpolate the subset of n θ /2 projections to generate n θ projections and reconstructed the image of the phantom from the interpolated projections. We will denote these images with x proposed n θ /2 and x dict.
n θ /2 . We simulated two levels of noise in the projections with different number of incident photons: N 0 = 10 6 and N 0 = 5 × 10 4 . We will refer to these simulations as low-noise and high-noise, respectively. For both simulations, we assumed the detector electronic noise to be additive Gaussian with a standard deviation of 40. As the reference scan that we need for block matching for computation of R s , we used the simulated scan of a different brain phantom from the same database.
We compared the reconstructed images with the true phantom image by computing the root-mean-square of error (RMSE) and the Structural Similarity (SSIM) index. The results of this comparison are presented in Table 1. Sinogram interpolation with the propsoed algorithm has resulted in a large improvement in the objective quality of the reconstructed image. The improvement is more substantial in the case of high-noise projections. This is because, as we mentioned above, both regularization terms R s and R h have excellent denoising effects. The proposed algorithm has also outperformed the interpolation algorithm based on learned dictionaries. The objective quality of x proposed n θ /2 is very close to x n θ in the low-noise case and better than x n θ in the high-noise case. As shown in Figure 3, sinogram interpolation with the proposed algorithm has resulted in a substantial improvement in the visual quality of the reconstructed image. Not only artifacts have been significantly reduced, noise has also been decreased substantially.  Table 1. Objective quality of the reconstructed images of the brain phantom.

Experiment with real CT data
We used two micro-CT scans of a rat for this experiment: (1) a normal-dose scan obtained at normal dose used for routine imaging, (2) a low-dose scan obtained at much reduced dose (by reducing the mAs setting to half of that in routine imaging and using additional copper filtration). Each scan consisted of 720 projections. We reconstructed a high-quality "reference" image of the rat from all 720 projections of the normal-dose scan. Then, for each of the two scans we selected subsets of n θ projections for two values of n θ = 360 and 180 and, for each n θ , performed the same analysis as described above for simulation experiment. For the block-matching in the computation of R s we used the scan of a different rat.
To assess the quality of the reconstructed images, we computed the RMSE and SSIM with respect to the reference image as well as the contrast-to-noise ratio (CNR). The results of this evaluation have been summarized in Table 2. There is a substantial improvement in image quality metrics as a result of sinogram interpolation with the proposed algorithm. The proposed algorithm has led to much better image quality than the dictionary-based sinogram interpolation. The gain in image quality is more pronounced in the low-dose case. In fact, the objective quality of x proposed n θ /2 is even better than x n θ on the low-dose scan. For a visual comparison, Figure 4 shows a slice from the reconstructed images of the rat from the low-dose scan with n θ = 240. There is a remarkable improvement in image quality as a result of sinogram interpolation with the proposed algorithm. The visual quality of x proposed n θ /2 seems to be better than both x dict. n θ /2 and x n θ . n θ = 360 n θ = 240 xn θ x n θ /2 x proposed n θ /2  Table 2. Objective quality of the reconstructed images of the rat.

Conclusion
Our experiments show that the proposed sinogram interpolation algorithm can lead to large improvements in image quality. Due to the additional denoising effect of both regularization functions used by the proposed algorithm, this improvement is more significant when applied on low-dose scans. This means that the proposed algorithm is especially well-suited for sinogram restoration in lowdose CT. Our other experiments, not reported in this paper because of space limitations, show that the proposed algorithm can also be used to effectively interpolate the sinogram in more general cases than the case considered in this paper, for example when the angular spacing of the missing projection views is non-uniform or when some detector measurements are corrupted. The experimental results suggest that our proposed method can reduce the number of projection measurements that are needed to reconstruct an image with diagnostic quality. The reduction in the number of projection measurements also means that less data will need to be transmitted in situations where the image reconstruction is performed in a different site.


extfieldsofstudy:
Computer Science
Mathematics

text:
The Impact of Noise on Evaluation Complexity: The Deterministic Trust-Region Case

Intrinsic noise in objective function and derivatives evaluations may cause premature termination of optimization algorithms. Evaluation complexity bounds taking this situation into account are presented in the framework of a deterministic trust-region method. The results show that the presence of intrinsic noise may dominate these bounds, in contrast with what is known for methods in which the inexactness in function and derivatives' evaluations is fully controllable. Moreover, the new analysis provides estimates of the optimality level achievable, should noise cause early termination. It finally sheds some light on the impact of inexact computer arithmetic on evaluation complexity.

Introduction
This paper attempts to answer a simple question: how does noise in function values and derivatives affect evaluation complexity of smooth optimization? While analysis has been produced to indicate how high accuracy can be reached by optimization algorithms even in the presence of inexact but deterministic (1) function and derivatives' values (see [8,16,28,3,29,21,14]), these approaches crucially rely on the assumption that the inexactness is controllable, in that it can be made arbitrarily small if required so by the algorithm. But what happens in practical applications where significant noise is intrinsic and can't be assumed away? How is the evaluation complexity of the optimization algorithm altered?
To limit the scope of this analysis, we focus here on trust-region methods for unconstrained problems, a well known class of algorithms (see [16] for an in-depth coverage and [30] for a more recent survey), whose complexity was first investigated in [20]. We choose to base our present developements on the existing analysis of [14], where the evaluation complexity of trust-region methods with explicit dynamic accuracy is presented. It is shown in this paper that, under standard Lipschitz continuity assumptions, a variant of the classical trust-region algorithm using derivatives of degree one to q and allowing the control of inexactness in objective function and derivatives' values will find a q-th order ǫ-approximate minimizer of the objective function in O(ǫ −(q+1) ) evaluations of f and its derivatives.
Our purpose in this paper is to extend these results to the case where such favourable assumptions of the noise can no longer be made, in that evaluation of f or its derivatives may simply fail if the requested accuracy is too high. In that case, the desired ǫ optimality may not be reachable, and our minimization algorithm may be forced to terminate before approximate convergence can be declared. The question then arises to establish not only an upper bound on the number of evaluations for this event to occur, but also bounds, if possible, on the level of optimality achieved at termination. However, since noisy problems often occur in a context where even moderate accuracy is expensive to obtain, we wish our algorithms to preserve the ability of the methods described in [14,5] to dynamically adjust accuracy requests in the limits imposed by noise.
Contributions. We will present a trust-region method allowing dynamic accuracy control whenever possible given the level of noise, and show that termination of this algorithm will occur in at most O min[ϑ −1 f , ϑ −1 d ǫ −(q+1) , ǫ −(q+1) ] evaluations, where ϑ f and ϑ d are the absolute noise levels in f and its derivatives, respectively, ǫ is the (ideally) sought optimality threshold and q ≥ 1 is the sought optimality order. In addition, we will derive upper bounds on the value of optimality measures at termination that depend on ϑ f . To the best of our knowledge, these results are the first of their kind. Finally, a brief discussion will illustrate our results in the case where intrinsic noise is caused by computer arithmetic and round-off errors. Because our development heavily hinges on [14], repeating some material from this source is necessary to keep our argument understandable. We have however done our best to limit this repetition as much as possible, pushing some of it in an appendix when possible.
Even if the analysis presented below does not depend in any way on the choice of the optimality order q, the authors are well aware that, while requests for optimality of orders q ∈ {1, 2} lead to practical, implementable algorithms, this may no longer be the case for q > 2, at least for now. For high orders, the methods discussed in the paper therefore constitute an "idealized" setting (in which complicated subproblems can be approximately solved without affecting the evaluation complexity) and thus indicate the limits of achievable results.
Outline. A first section briefly recalls the context and the notion of high-order approximate minimizers. Section 3 then presents a "noise-aware" inexact trust-region algorithm and its evaluation complexity. Brief conclusions and perspectives are finally presented in Section 4.
Basic notations. Unless otherwise specified, · denotes the standard Euclidean norm for vectors and matrices. For a general symmetric tensor S of order p, we define the induced Euclidean norm. We also denote by ∇ j x f (x) the j-th order derivative tensor of f evaluated at x and note that such a tensor is always symmetric for any j ≥ 2. ∇ 0 x f (x) is a synonym for f (x). ⌊α⌋ denotes the largest integer not exceeding α. For symmetric matrices, λ min [M ] is the leftmost eigenvalue of M .
2 High-Order Taylor Decrements and High-Order Optimality Throughout this paper, we consider the unconstrained problem given by where we assume that the values of the objective function f and its derivatives are computed inexactly and are subject to noise. Inexact quantities will be denoted by an overbar, so that f (s) is an inexact value of f (x) and ∇ j x f (x) an inexact value of ∇ j x f (x). We will also assume that AS.1: the objective function f is q times continuously differentiable in R n , for some q ≥ 1; AS.2: the first q derivative tensors of f are globally Lipschitz continuous, that is, for each j ∈ {1, . . . , q} there exist a constant L f,j ≥ 0 such that, for all x, y in R n , In what follows, we consider algorithms that are able to exploit all available derivatives of f . As in many minimization methods, we would like to build a model of the objective function f using the truncated Taylor expansions (now of degree j for j ∈ {1, . . . , q}) given by where ∇ ℓ x f (x) is a ℓ-th order symmetric tensor and ∇ ℓ x f (x)[s] ℓ is this tensor applied to ℓ copies of the vector s. More specifically, we will be interested, at a given iterate x k , in finding a step s ∈ R n which makes the Taylor decrements . When this is possible, we anticipate from the approximating properties of the Taylor expansion that some significant decrease is also possible in f . Conversely, if ∆T f,j (x, s) cannot be made large in a neighbourhood of x, we must be close to an approximate minimizer. More formally, we define, for some optimality radius δ ∈ (0, 1], the measure that is the maximal decrease in T f,j (x, d) achievable in a ball of radius δ centered at x. We then define x to be a q-th order (ǫ, δ)-approximate minimizer (for some accuracy requests ǫ ∈ (0, 1] q ) if and only if (a vector d solving the optimization problem defining φ δ f,j (x) in (2.3) is called an optimality displacement). In other words, a q-th order (ǫ, δ)-approximate minimizer is a point from which no significant decrease of the Taylor expansions of degree one to q can be obtained in a ball of optimality radius δ. This notion is coherent with standard optimality measures for low orders (2) and has the advantage of being well-defined and continuous in x for every order.
Unfortunately, the exact values of f (x) and ∇ ℓ x f (x) may be unavailable, and we then face several difficulties. The first is that we can't consider the optimality measure (2.3) anymore, but could replace it by the inexact variant However, computing the exact global maximum in this definition may also be too expensive, and we follow [16, Theorem 6.3.5] and [14] in choosing to use the approximate version given by for some displacement d such that d ≤ δ and some constant ς ∈ (0, 1]. Note that (2.6) does not assume the knowledge of the global maximizer or φ δ f,j (x), but merely that we can ensure (2.6) (see [17,18,27] for research in this direction). Note also that, by definition, (2.7) The second difficulty occurs when computing a step s k which is supposed to make the exact Taylor decrement ∆T f,j (x k , s k ) large, since we now have to resort to making the inexact decrement large. It is therefore necessary to ensure, somehow, that the error on this decrement does not dominate its value. The theory developed in this paper depends on making the relative error on ∆T f,j (x k , s k ) (for a chosen step s k ) smaller than one, which is to require that for some constant ω ∈ (0, 1) to be specified later. It is clearly not obvious at this point how to enforce this relative error bound. For now, we simply assume that it can be done in a finite number of evaluations of The third difficulty arises when assessing the performance of the computed step: is the predicted decrease in objective function predicted by the (inexact) decrement significant in view of the (absolute) noise level in computing f (x k ) and f (x k + s)? If not, the obtained decrease is dominated by noise in f and thus unreliable. To avoid this, our algorithms will attempt to require that (2) It is easy to verify that, irrespective of δ, (2.4) holds for j = 1 if and only if ∇ 1 x f (x) ≤ ǫ1 and that, if where ω is the parameter occuring in (2.8). The fourth, and for our present purpose, most significant difficulty is that achieving (2.8) or (2.9) may require an accuracy of f and its derivatives which is not feasible for noisy problems, and we will have to prematurely terminate the algorithm. In what follows, we make the assumption that this situation may occur (and thus does occur in the worst case) if, for some x k of interest and j ∈ {1, . . . , q}, for some non-negative absolute noise levels ϑ f and ϑ d . The rest of our analysis will therefore focus on analyzing trust-region algorithms which ensure that (2.8) and (2.9) hold as long as (2.10) fail. Like many trust-region methods, our proposed algorithms will consist of an initialization followed by a loop, performed until termination, in which one successively 1. evaluates the function's derivatives and checks for termination, 2. computes a step s k which approximately minimizes an (inexact) Taylor model T f,j (x k , s) while remaining the inequality s k ≤ ∆ k , where ∆ k is the current trust-region radius, 3. evaluates the objective function at the new potential iterate and accepts or refuses the step, 4. updates the trust-region radius ∆ k .
The discussion above suggests that, at the very least, specialized versions of the first three steps will be necessary.

A Trust-Region Algorithm with Explicit Dynamic Accuracy and Noise
Because our analysis is based on (2.8) and (2.9), we have to discuss how these conditions can be achieved. For this purpose, we will use the "Explicit Dynamic Accuracy" (EDA) framework already used in [16,4,21], in which absolute accuracies on the function and derivatives values may be specified by the algorithm by imposing the bounds and before the actual computation of f (x) and ∇ ℓ x f (x) takes place (3) . Such a framework is applicable for instance to multiprecision computations [23,22] or to problems where the desired values are computed by an iterative process whose accuracy can be monitored. In our trustregion algorithm, the thresholds ζ f and ζ d will be adaptively updated in the course of the iterations, but it is already clear that requesting ζ d < ϑ d will be impossible when (2.10) holds.

Checking the accuracy of the model decrease
However, before this happens, the algorithm will need to verify that the model decrease relative accuracy bound (2.8) holds when the "derivative-by-derivative" absolute errors ζ d are known. As it turns out, this request has to be relaxed somewhat whenever the right-hand side ω∆T f,j (x k , s k ) is small, as can be expected near a minimizers, and we have to replace the relative accuracy bound (2.8) by an absolute error bound in that case. The management of these crucial details is the object of the CHECK algorithm on this page. To describe this algorithm in a general context, we suppose that we have a r-th degree Taylor series T r (x, v) of a given function about x in the direction v, along with an approximation T r (x, v) and its decrement ∆T r (x, v). Additionally, we suppose that a bound δ ≥ v is given, and that required relative and absolute accuracies ω and ξ > 0 are on hand. Moreover, we assume that the current upper bound ζ d,i ζ on absolute accuracies of the derivatives of T r (x, v) with respect to v at v = 0 are provided. Because it will always be the case when we need it, we will assume for simplicity that ∆T r (x, v) ≥ 0. Finally, the relative accuracy constant ω ∈ (0, 1) will be fixed in our trust-region algorithm, and we assume that it is given when needed in CHECK. The constants γ ζ , ϑ f and ϑ d of (2.10) are also assumed to be known.
set accuracy to relative.
set accuracy to absolute.
and accuracy to insufficient.
Otherwise, set accuracy to terminal.
Note that the integer i ζ counts the number of times the accuracy threshold has been reduced by a factor γ ζ . The outcome of the CHECK algorithm can then characterized as follows.
Moreover, the outcome accuracy = insufficient indicates that new values of the required approximate derivatives should be computed with the updated accuracy thresholds, while accuracy = terminal indicates that the minimization algorithm has reached the noise level and should be terminated.
Proof. We note that the CHECK algorithm is identical to the VERIFY algorithm of [14] (itself inspired by [4]) whenever accuracy is either absolute or relative. Lemma 2.1 in that reference therefore ensures the conclusions (i) to (iii). If accuracy = insufficient, then (3.5) ensures that the accuracy threshold update (3.6) has been performed safely ((2.10) remains violated), while accuracy = terminal indicates that this was not the case, suggesting termination. ✷ Note that case (ii) is the case where relative accuracy would be excessively requiring and absolute accuracy is preferred.

Testing for termination
We now start constructing our new algorithm (which we call the TRqEDAN algorithm because it uses the EDA framework and handles Noise) step by step, following the outline given at the end of Section 2. Consider Step 1 first. Since we have to rely on ∇ ℓ x f (x k ) rather than ∇ ℓ x f (x k ), it is clear that our optimality measure (2.3) and test (2.4) should be modified to use the inexact values. Ideally, we could mimic [14] and terminate because of (2.7) as soon as and where ω ∈ (0, 1) is the (still unspecified) relative accuracy parameter of (2.8), and δ k is the optimality radius at iteration k (which we leave again unspecified at this stage). However, we now have to take into account the fact that noise in the values of the derivatives may prevent a meaningful computation of ∆T f,j (x k , d k,j ). We therefore have to modify the technique proposed in [14,Algorithm 2.2]. Assuming that the optimality radius δ k is given, we thus consider Algorithm 3.2 for computing the j-th approximate optimality measure which is needed in (3.7) to test for termination in the first step of the TRqEDAN algorithm.
Note that, when termination occurs, this algorithm (and other algorithms we will meet later) sets the four flags status, order, delta and radius, which will allow the user to determine the reason of termination once it occured and, as we will see in Theorem 3.12 below, derive some useful properties of the pointx returned.
Otherwise, if it terminates with accuracy j being relative, then Moreover, termination with one of these two outcomes must occur if Of course, termination may occur before (3.11) occurs (for instance because of (2.10) in the call to CHECK in Step 1.2), but the bound (3.11) shows that, if this doesn't happen, the accuracy threshold ζ d,i ζ can not be reduced infinitely often by the factor γ ζ and thus the loop between Steps 1.4 and 1.1 is finite. Note that the rightmost inequality in (3.10) and (3.7) together also imply (3.9) for order j, justifying our choice of the scaling by (1 + ω) in the former.
Refering now to our outline on the trust-region method at the end of Section 2, we may now use Algorithm 3.2 to implement a complete Step 1. The idea is first to identify a suitable optimality radius, which we choose to be (3.12) (for some constant θ ≤ 1), estimate the needed (inexact) derivatives and φ δ k f,j (x k ) for j ∈ {1, . . . , q} and decide on termination. The result is the STEP1 algorithm on the next page.
Before progressing any further, we state an easy but useful technical inequality. (3.14) Proof. The bounds (3.14) easily follow from 1 ≤ j ℓ=1 1 ℓ! < e − 1 < 2. ✷ We now consider what can be said if the TRqEDAN algorithm terminates within STEP1.
2. If termination of the TRqEDAN algorithm has not happened in Step 1.4 of Algorithm 3.2 and exit STEP1 with the current value of j and the optimality displacement d k,j asso- Otherwise consider the next j. Terminate the TRqEDAN algorithm withx = x k , status = approximate-minimizer, order = q and delta = radius = δ k .

Lemma 3.4
(i) Suppose that termination of the TRqEDAN algorithm occurs within STEP1 with status = in-noise-phi, order = j and delta = δ k . Then (ii) Suppose that termination of the TRqEDAN algorithm occurs with status = approximate-minimizer and delta = δ k . Then (2.4) holds andx is a q-th order (ǫ, δ k )-approximate minimizer.
Consider now case (i), that is when the call CHECK in Step 1.2 of Algorithm 3.2 returns accuracy j = terminal for some j ∈ {1, . . . , q}. Thus Algorithm 3.2 has terminated within Step 1.3 and (3.13) has failed for every order of index smaller than j − 1. Applying the same reasoning as for case (ii), we obtain that the first part of (3.15) holds. Now suppose that, instead of the call (3.8) resulting in accuracy j being terminal, we had made the hypothetical call Observe first that, since the call (3.8) returned terminal, (3.3) failed on that call, and thus, since this is independent of the last argument of the call, it also fails for the call (3.16). However, one easily checks that (3.4) holds as an equality for this hypothetical call, and thus (3.16) would return accuracy j as absolute. We may then use case (ii) in Lemma 3.1 and deduce from the triangular inequality that, for somed with d ≤ δ k , Moreover, since the call (3.8) returned terminal, we have that γ ζ ζ d,i ζ < ϑ d , and we deduce that The second part of (3.15) then results from this inequality and (3.14) for δ = δ k ≤ θ ≤ 1. ✷ We also have the following useful result.
Lemma 3.5 Suppose that, at iteration k, termination of the TRqEDAN algorithm does not happen during execution of STEP1. Then where the threshold ζ d,i ζ refers to its value at the end of STEP1. Moreover, Proof.
Suppose that the last value of accuracy j computed during the execution of STEP1 is absolute. Then Lemma 3.2 implies that (3.9) holds. But, since ω ∈ (0, 1), this and Lemma 3.1 (ii) contradict (3.13). As a consequence, the last value of accuracy j must be relative, in which case (3.3) ensures (3.18). The first part of (3.19) again follows from the reasoning of Lemma 3.4(ii) for i ∈ {1, . . . , j − 1}. Finally, the fact that accuracy j is relative implies that (3.10) holds in Lemma 3.2, which gives the second part of (3.19). ✷

Computing a step
Given Step 1, constructing Step 2 of our TRqEDAN algorithm is relatively straightforward and we immediately provide the details in the STEP2 algorithm on this page. The iterate x k , the relative accuracy ω, the requested accuracy ǫ j ∈ (0, 1] q , the constant γ ζ ∈ (0, 1) the counter i ζ and the absolute accuracy threshold ζ d,i ζ are given. The index j ∈ {1, . . . , q}, the optimality displacement d k,j resulting from Step 1 and the constant θ ∈ (0, 1], are also given such that, by (3.13), (3.20) Step 2.1: If they are not yet available, compute {∇ ℓ x f (x k )} j i=1 satisfying (3.2) for ζ d = ζ d,i ζ and recompute ∆T f,j (x k , d k,j ) for this accuracy threshold.
Step 2.2: Step computation. If ∆ k ≤ θ, set s k = d k,j and exit the STEP2 algorithm with ∆T f,j (x k , s k ) = ∆T f,j (x k , d k,j ). Otherwise, find s k such that s k ≤ ∆ k and and compute accuracy s = CHECK s k , ∆T f,j (x k , s k ), ζ d,i ζ , ςǫ j 4(1 + ω) θ max θ, s k j .

(3.22)
Step 2.3: If accuracy s is relative, exit the STEP2 algorithm with the step s k and the associated ∆T f,j (x k , s k ).
Step 2.4: If accuracy s is insufficient, return to Step 2.1 (with the tightened accuracy thresholds). Otherwise, if accuracy s is terminal, terminate the TRqEDAN algorithm withx = x k , status = in-noise-s, order = j, delta = δ k and radius = s k .
Note that setting s k = d k,j when ∆ k < θ makes sense since d k,j , computed in Step 1.2, is already a (CHECKed) approximate global maximizer of ∆T f,j (x k , s) in the ball of radius δ k = ∆ k . Two features of this algorithm remain nevertheless somewhat mysterious at this stage. The first is the complicated function of s k and ǫ j occuring in the last argument of the call to the CHECK algorithm. As it turns out, it is possible to show that the conjunction of (3.13) and this particular call to CHECK (4) ensures that accuracy s cannot be absolute. This then also clarifies the second mysterious feature, which is why this value of accuracy s is not considered in the rest of the algorithm. This is part of the following lemma, which was proved as Lemma 3.2 in [14] and which we can reuse since the step computation in that (4) VERIFY in [14].
reference (5) Lemma 3.7 Suppose that, at iteration k, the TRqEDAN algorithm terminates within STEP2 with status = in-noise-s, order= j and radius = s k . Then Proof. The fact that status = in-noise-s implies that termination occurs in Step 2.4, and it must be because the call (3.22) returns accuracy s equal to terminal. As in the proof of Lemma 3.4, we consider replacing this call by the hypothetical 3.25) and verify that this call must return accuracy s equal to absolute. We also deduce from case (ii) in Lemma 3.1, the triangular inequality and the bound γ ζ ζ d, and (3.24) follows from (3.14). ✷

The complete TRqEDAN algorithm
Having constructed the first two steps of the TRqEDAN algorithm, we are now in position to specify the algorithm in its entirety (see on page 15), making the necessary changes to handle (5) In [14], the step computation is the combination of Step 2 in Algorithm 3.1 and Algorithm 3.2 for the case where ∆ k ≥ θ. Note that, in this case, δ k = θ and thus δ k may be replaced by θ in the right-hand side of (3.20), as stated in Algorithm 3.2 of [14].
(2.10) in Step 3 along the way.
We immediately note the condition, at the beginning of Step 3, that ∆T f,j (x k , s k ) > ϑ f /ω. This guarantees that the limit in noise imposed by (2.10) will not come into play when computing f (x k + s k ) (and possibly recomputing f (x k )).
We also note that, except for that feature, our specialized STEP1 and STEP2 using the CHECK algorithm to handle intrinsic noise on the derivatives, and the relevant initialization of ω, the TRqEDAN algorithm is identical to that analyzed in [14] (6) . Again, this allows us to reuse results in this reference as needed, the first of which relates the number of iterations of "successful" iterations (those where the new iterate is accepted in Step 3) and "unsuccessful" ones. If, as is standard, we define the following useful result is applicable to the TRqEDAN algorithm.
Lemma 3.8 [14, Lemma 3.1] Suppose that the TRqEDAN algorithm is used and that ∆ k ≥ ∆ min for some ∆ min ∈ (0, ∆ 0 ]. Then, if k is the index of an iteration before termination,

Evaluation complexity and optimality at termination
Readers with some background in evaluation complexity analysis will not be surprised by the fact that the complexity of the TRqEDAN algorithm crucially depends on the decrease that can be achieved on the exact objective function at successful iterations. This will in turn depend on the achievable decrease in inexact values of the objective, which is itself depending on the decrease ∆T f,j (x k , s k ) on the inexact model. Fortunately, we can again call on the analysis of [14] for help, since such decreases necessarily happen in the TRqEDAN algorithm, before early termination due to (2.10) possibly occurs.
Step 1: Termination test. Apply the STEP1 algorithm (p. 10), resulting in either termination, or a model degree j and the associated displacement d k,j and decrease ∆T f,j (x k , d k,j ).
Step 2: Step computation. Apply the STEP2 algorithm (p. 12) to compute a step s k such that ∆T f,j (x k , s k ) ≥ ∆T f,j (x k , d k,j ).
Otherwise, compute f (x k + s k ) ensuring that (3.26) and ensure (by setting f (x k ) = f (x k−1 + s k−1 ) or by recomputing f (x k )) that Then compute Step 4: Update the trust-region radius. Set Increment k by one and go to Step 1.
where j is the model's degree resulting from STEP1 at iteration k. Then, with ǫ min = min j∈{1,...,q} ǫ j . Moreover, Using these results, we may consider the all-important lower bound on the model decrease at successful iterations.
Lemma 3.10 Suppose that ϑ d > 0 and let k be the index of a successful iteration of the TRqEDAN algorithm before termination. Then Proof.
Observe first that, since iteration k is successful, the algorithm must have reached the end of Step 3 at this iteration, and thus termination did not occur in Steps 1 or 2. This means in particular, in view of (3.5), that ζ d,i ζ > ϑ d (3.36) for all values of the accuracy threshold ζ d,i ζ encountered during Steps 1 and 2 of iteration k. Moreover Lemma 3.5 applies and (3.18) and (3.36) imply that again irrespective of the accuracy threshold ζ d,i ζ encountered during Steps 1 and 2.
We now distinguish two cases, depending on the ratio between ∆ k and θ.
• Suppose now that ∆ k > θ, (or, equivalently, that δ k < ∆ k ). Then δ k = θ. Suppose first that s k ≥ δ k = θ. Lemma 3.6 ensures that STEP2 terminates with accuracy s being relative and (3.3) holds for x = x k and v = s k . As a consequence, using (3.33), (3.35) and the fact that ςǫ min ≤ 1, again implying (3.34). Suppose finally that s k < δ k = θ. Then we deduce from (3.37) and (3.21) that and (3.34) also holds in this last case. ✷ Of course, this lemma does not allow any useful conlusion if ϑ d = 0, that is in the noiseless case. But we can call on the noiseless analysis of [14] to cover this case.
Proof. See [14,Lemma 3.7]. The proof is based on using (3.32) and (3.31) in Lemma 3.9. ✷ We may finally combine Lemmas 3.4, 3.7, 3.10 and 3.11 to derive a upper-bound on the number of evaluations required by the TRqEDAN algorithm for termination.
evaluations of f (x) itself to terminate with flags status, order, delta, radius and a pointx at which and if status = approximate-minimizer; if status = in-noise-phi; where j = order, δ = delta and ν = radius. If, in addition, at iteration k at which termination occurs with status = in-noise-f, then Proof.
We note that the various flag-dependent optimality guarantees (3.42)-(3.45) are a simple compilation of the results of Lemmas 3.4 and 3.7. To prove (3.47), observe that, if termination occurs in Step 3 (as indicated by status = in-noise-f), it must be because ∆T f,j (x k , s k ) ≤ ϑ f /ω. But (3.12) and (3.46) imply that Moreover, the fact that Step 3 has been reached ensures that termination did not occur in either Step 1 or Step 2. Thus (3.19) in Lemma 3.5 with the definition radius = max[δ k , s k ] gives (3.47).
We now focus on proving (3.40) and (3.41). Let k be the index of a successful iteration before termination. Because (3.26) and (3.27) both hold at every successful iteration before termination, we have that, Combining now this inequality with Lemmas 3.10 and 3.11 we obtain that Moreover, the mechanism of Step 3 of the TRqEDAN algorithm implies that From (3.48) and (3.49), we thus deduce that Using now the standard "telescoping sum" argument and AS. 3, we obtain that so that the total number of successful iterations before termination is Now (3.31), the second part of (3.32) and (3.35) imply that so that, invoking now Lemma 3.8, we deduce that the total number of iterations before termination is bounded above by Since each iteration of the TRqEDAN algorithm inexactly compute the objective function's value at most twice (in Step 3), we obtain that the total number of such evaluations before termination is bounded above by 2n it , yielding (3.41) with To complete the proof, we need to elaborate on (3.50) to derive an upper bound on the number of derivatives evaluations. While the TRqEDAN algorithm evaluates at least once in Step 1, it may need to evaluate the derivatives also when CHECK returns insufficient, and this can happen in the loops between Steps 1.4 and 1.1 in Algorithm 3.2 and between Steps 2.4 and 2.1 in the STEP2 algorithm. Thus the total number of derivatives' evaluations is given by |S k | plus the total number of accuracy tightenings (counted by i ζ ). The next step is therefore to establish an upper bound on this latter number. This part of the proof is a variation on that of Theorem 3.8 in [14], now involving the bounds (3.11) and (3.23) but also the additional inequality ζ d,i ζ ≥ ϑ d which must hold as long as termination has not occured. To summarize the argument, these three bounds ensure a global lower bound ζ d,min on ζ d,i ζ , while an upper bound is given by κ ζ . Since each tightening proceeds by multiplying the accuracy threshold by γ ζ , one then deduces that the maximum number of such tightenings is O | log(ζ d,min /κ ζ )| , which then leads to (3.40). The details are given in appendix. ✷ Observe that condition (3.46) needs only to be enforced if the bound (3.47) is desired and when termination occurs with status = in-noise-f. Should (3.47) be of interest, the step may have to be recomputed in the course of the algorithm to ensure (3.46), whenever ∆T f,j (x k , s k ) < ϑ f /ω. Termination is then declared if this inequality still holds for the new step, or the algorithm is continued otherwise. The results of Theorem 3.12 merit some comments. Firstly, and as expected, we see in the bounds (3.40) and (3.41) that the total number of evaluations needed for the TRqEDAN to terminate may be considerably smaller when intrinsic noise is present (ϑ d > 0 and ϑ f > 0) than in the noiseless situation (ϑ d = ϑ f = 0), in which case we recover the bound in O(ǫ −(q+1) min ) + O(| log(ǫ min )|) of [14]. More interestingly, we note that, for the intrinsic noise to be small enough to let the trust-region algoritm run its course unimpeded, we need that ϑ d = O(ǫ q min ) and ϑ f = O(ǫ q+1 min ). Since ϑ d and ϑ f are intrinsic to the problem, it means that we expect the algorithm to run unimpeded (in the worst case) only if (3.52) To give an example, suppose that we are applying the TRqEDAN algorithm to find secondorder approximate minimizers on a machine whose machine precision is 10 −15 . This suggest that (in the worst case again), the algorithm could work as if noise where absent for ǫ min of order 10 −5 and above. Of course, this ignores that some of the deterministic bounds we have imposed could fail and yet the algorithm could proceed without trouble. We also note that the second term in (3.40), which accounts for the additional evaluations due to inexact but still acceptable evaluations, now involves a term in | log(ϑ d /κ ζ )| (the magnitude of the accuracy range between it initial value and noise) along with the term in log(ǫ min ) = log(ǫ q min ) of [14]. This is coherent with our observation (3.52). We finally note the difference between the impact of the absolute noise on the objective function's values (ϑ f ) and that on the derivatives (ϑ d ), the former being significantly more limitative than the latter. This is reminiscent of similar observations and assumptions in the stochastic context [6,2,7].