Change point estimation is often formulated as a search for the maximum of a gain function describing improved fits when segmenting the data. Searching one change point through all candidates requires $O(n)$ evaluations of the gain function for an interval with $n$ observations. If each evaluation is computationally demanding (e.g. in high-dimensional models), this can become infeasible. Instead, we propose optimistic search, a methodology that only requires $O(\log n)$ evaluations of the gain function, leading to huge computational gains for massive (large-scale, high-dimensional) data for single and multiple change point estimation. Towards solid understanding of our strategy, we investigate in detail the $p$-dimensional Gaussian changing means setup, including high-dimensional scenarios. For some of our proposals, we prove asymptotic minimax optimality for detecting change points and derive sharp asymptotic rates for localizing change points. Our search strategy generalizes far beyond the theoretically analyzed setup. We illustrate, as an example, massive computational speedup in change point detection for high-dimensional Gaussian graphical models.

We introduce a new iterative regularization method for solving inverse problems that can be written as systems of linear or nonlinear equations in Hilbert spaces. The proposed averaged Kaczmarz (AVEK) method can be seen as a hybrid method between the Landweber and the Kaczmarz methods. As the Kaczmarz method, the proposed method only requires evaluation of one direct and one adjoint subproblem per iterative update. On the other hand, similar to the Landweber iteration, it uses an average over previous auxiliary iterates which increases stability. We present a convergence analysis of the AVEK iteration. Further, detailed numerical studies are presented for a tomographic image reconstruction problem, namely the limited data problem in photoacoustic tomography. Thereby, the AVEK is compared with other iterative regularization methods including standard Landweber and Kaczmarz iterations, as well as recently proposed accelerated versions based on error minimizing relaxation strategies.

Polynomials are widely used in scientific computing and engineering. In this paper, we present an accurate and fast compensated algorithm to evaluate bivariate polynomials with floating-point coefficients. This algorithm is applying error free transformations to the bivariate Horner scheme and sum the final decomposition accurately. We also prove the proposed algorithm's accuracy with forward error analysis that the accuracy of the computed result is similar to the result computed by the bivariate Horner scheme in twice the working precision. Numerical experiments illustrate the behavior and it has higher efficiency than the bivariate Horner scheme implemented in double-double library.

Designing fast singular value decomposition (SVD) is significantly interesting in applications. The random direct SVD (RSVD) has provided a fast scheme to compute the well-approximate SVD by unilateral randomized sampling. In this paper, we present an efficient random algorithm in a bilateral sampling way. We also prove that the proposed algorithms can be bounded well and have less computational complexity compared to RSVD when the objective matrix is approximately square. Numerical experiments on graph Laplacian and Hilbert matrix demonstrate the efficiency and stability of the proposed methods.