Local reconstruction of low‐rank matrices and subspaces

We study the problem of reconstructing a low‐rank matrix, where the input is an n × m matrix M over a field and the goal is to reconstruct a (near‐optimal) matrix that is low‐rank and close to M under some distance function Δ. Furthermore, the reconstruction must be local, i.e., provides access to any desired entry of by reading only a few entries of the input M (ideally, independent of the matrix dimensions n and m). Our formulation of this problem is inspired by the local reconstruction framework of Saks and Seshadhri (SICOMP, 2010). Our main result is a local reconstruction algorithm for the case where Δ is the normalized Hamming distance (between matrices). Given M that is ‐close to a matrix of rank (together with d and ), this algorithm computes with high probability a rank‐d matrix that is ‐close to M. This is a local algorithm that proceeds in two phases. The preprocessing phase reads only random entries of M, and stores a small data structure. The query phase deterministically outputs a desired entry by reading only the data structure and 2d additional entries of M. We also consider local reconstruction in an easier setting, where the algorithm can read an entire matrix column in a single operation. When Δ is the normalized Hamming distance between vectors, we derive an algorithm that runs in polynomial time by applying our main result for matrix reconstruction. For comparison, when Δ is the truncated Euclidean distance and , we analyze sampling algorithms by using statistical learning tools. A preliminary version of this paper appears appears in ECCC, see: http://eccc.hpi-web.de/report/2015/128/ © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 607–630, 2017     

Approximations in Sobolev spaces by prolate spheroidal wave functions

Recently, there is a growing interest in the spectral approximation by the Prolate Spheroidal Wave Functions (PSWFs) ${\psi }_{n,c},c>0$. This is due to the promising new contributions of these functions in various classical as well as emerging applications from Signal Processing, Geophysics, Numerical Analysis, etc. The PSWFs form a basis with remarkable properties not only for the space of band-limited functions with bandwidth c, but also for the Sobolev space $H^s([?1,1])$. The quality of the spectral approximation and the choice of the parameter c when approximating a function in $H^s([?1,1])$ by its truncated PSWFs series expansion, are the main issues. By considering a function $f\in H^s([?1,1])$ as the restriction to $[?1,1]$ of an almost time-limited and band-limited function, we try to give satisfactory answers to these two issues. Also, we illustrate the different results of this work by some numerical examples.     

On the two classes of high‐order convergent methods of approximate inverse preconditioners for solving linear systems

Two classes of methods for approximate matrix inversion with convergence orders p =3?2^k +1 (Class 1) and p =5?2^k ?1 (Class 2), k ≥1 an integer, are given based on matrix multiplication and matrix addition. These methods perform less number of matrix multiplications compared to the known hyperpower method or p th‐order method for the same orders and can be used to construct approximate inverse preconditioners for solving linear systems. Convergence, error, and stability analyses of the proposed classes of methods are provided. Theoretical results are justified with numerical results obtained by using the proposed methods of orders p =7,13 from Class 1 and the methods with orders p =9,19 from Class 2 to obtain polynomial preconditioners for preconditioning the biconjugate gradient (BICG) method for solving well‐ and ill‐posed problems. From the literature, methods with orders p =8,16 belonging to a family developed by the effective representation of the p th‐order method for orders p =2^k , k is integer k ≥1, and other recently given high‐order convergent methods of orders p =6,7,8,12 for approximate matrix inversion are also used to construct polynomial preconditioners for preconditioning the BICG method to solve the considered problems. Numerical comparisons are given to show the applicability, stability, and computational complexity of the proposed methods by paying attention to the asymptotic convergence rates. It is shown that the BICG method converges very quickly when applied to solve the preconditioned system. Therefore, the cost of constructing these preconditioners is amortized if the preconditioner is to be reused over several systems of same coefficient matrix with different right sides.     

Error estimates for space–time discontinuous Galerkin formulation based on proper orthogonal decomposition

In this study, proper orthogonal decomposition (POD) method is applied to diffusion–convection–reaction equation, which is discretized using space–time discontinuous Galerkin (dG) method. We provide estimates for POD truncation error in dG-energy norm, dG-elliptic projection, and space–time projection. Using these new estimates, we analyze the error between the dG and the POD solution, and the error between the exact and the POD solution. Numerical results, which are consistent with theoretical convergence rates, are presented.     

Remarks on the Born approximation and the Factorization Method

In this paper, we compare the far-field operators for the full nonlinear inverse scattering problem with the Born approximation as its linearization. The Factorization Method shows that both operators share the same behavior with respect to illposedness of the inverse problem. The results are derived for acoustic and electromagnetic scattering problems and the corresponding problem in electrical impedance tomography.     

A new scheme for solving nonlinear Stratonovich Volterra integral equations via Bernoulli’s approximation

In this paper, an efficient method for solving nonlinear Stratonovich Volterra integral equations is proposed. By using Bernoulli polynomials and their stochastic operational matrix of integration, these equations can be reduced to the system of nonlinear algebraic equations with unknown Bernoulli coefficient which can be solved by numerical methods such as Newton’s method. Also, an error analysis is valid under fairly restrictive conditions. Furthermore, in order to show the accuracy and reliability of the proposed method, the new approach is compared with the block pulse functions method by some examples. The obtained results reveal that the proposed method is more accurate and efficient than the block pulse functions method.     

Full Bayesian analysis of claims reserving uncertainty

We revisit the gamma–gamma Bayesian chain-ladder (BCL) model for claims reserving in non-life insurance. This claims reserving model is usually used in an empirical Bayesian way using plug-in estimates for the variance parameters. The advantage of this empirical Bayesian framework is that allows us for closed form solutions. The main purpose of this paper is to develop the full Bayesian case also considering prior distributions for the variance parameters and to study the resulting sensitivities.     

Incorporating model uncertainty into optimal insurance contract design

In stochastic optimization models, the optimal solution heavily depends on the selected probability model for the scenarios. However, the scenario models are typically chosen on the basis of statistical estimates and are therefore subject to model error. We demonstrate here how the model uncertainty can be incorporated into the decision making process. We use a nonparametric approach for quantifying the model uncertainty and a minimax setup to find model-robust solutions. The method is illustrated by a risk management problem involving the optimal design of an insurance contract.     

Some closed form robust moment‐based estimators for the MEM(1,1)

In this paper, we extend the closed form moment estimator (ordinary MCFE) for the autoregressive conditional duration model given by Lu et al (2016) and propose some closed form robust moment‐based estimators for the multiplicative error model to deal with the additive and innovational outliers. The robustification of the closed form estimator is done by replacing the sample mean and sample autocorrelation with some robust estimators. These estimators are more robust than the quasi‐maximum likelihood estimator (QMLE) often used to estimate this model, and they are easy to implement and do not require the use of any numerical optimization procedure and the choice of initial value. The performance of our proposal in estimating the parameters and forecasting conditional mean μ_t of the MEM(1,1) process is compared with the proposals existing in the literature via Monte Carlo experiments, and the results of these experiments show that our proposal outperforms the ordinary MCFE, QMLE, and least absolute deviation estimator in the presence of outliers in general. Finally, we fit the price durations of IBM stock with the robust closed form estimators and the benchmarks and analyze their performances in estimating model parameters and forecasting the irregularly spaced intraday Value at Risk.     

Stochastic optimization of an urban rail timetable under time‐dependent and uncertain demand

Urban rail planning is extremely complex, mainly because it is a decision problem under different uncertainties. In practice, travel demand is generally uncertain, and therefore, the timetabling decisions must be based on accurate estimation. This research addresses the optimization of train timetable at public transit terminals of an urban rail in a stochastic setting. To cope with stochastic fluctuation of arrival rates, a two‐stage stochastic programming model is developed. The objective is to construct a daily train schedule that minimizes the expected waiting time of passengers. Due to the high computational cost of evaluating the expected value objective, the sample average approximation method is applied. The method provided statistical estimations of the optimality gap as well as lower and upper bounds and the associated confidence intervals. Numerical experiments are performed to evaluate the performance of the proposed model and the solution method.