Weyl eigenvalue asymptotics and sharp adaptation on vector bundles

This paper examines the estimation of an indirect signal embedded in white noise on vector bundles. It is found that the sharp asymptotic minimax bound is determined by the degree to which the indirect signal is embedded in the linear operator. Thus when the linear operator has polynomial decay, recovery of the signal is polynomial where the exact minimax constant and rate are determined. Adaptive sharp estimation is carried out using a blockwise shrinkage estimator. Application to the spherical deconvolution problem for the polynomially bounded case is made.     

Wavelet Shrinkage Denoising Using the Non-Negative Garrote

Abstract

In this article, we combine Donoho and Johnstone's wavelet shrinkage denoising technique (known as WaveShrink) with Breiman's non-negative garrote. We show that the non-negative garrote shrinkage estimate enjoys the same asymptotic convergence rate as the hard and the soft shrinkage estimates. Simulations are used to demonstrate that garrote shrinkage offers advantages over both hard shrinkage (generally smaller mean-square-error and less sensitivity to small perturbations in the data) and soft shrinkage (generally smaller bias and overall mean-square-error). The minimax thresholds for the non-negative garrote are derived and the threshold selection procedure based on Stein's unbiased risk estimate (SURE) is studied. We also propose a threshold selection procedure based on combining Coifman and Donoho's cycle-spinning and SURE. The procedure is called SPINSURE. We use examples to show that SPINSURE is more stable than SURE: smaller standard deviation and smaller range.     

Adaptive estimates of linear functionals

Summary Given a collection of nested closed, convex symmetric sets and a linear functional, we find estimates which are within a logarithm term of being simultaneously asymptotically minimax. Moreover, these estimates can be constructed so that the loss of this logarithm term only occurs on a small subset of functions. These estimates are quasi-optimal since there do not exist estimators which do not lose a logarithm term on some part of the parameter spaces.This author was partially supported by an NSF Grant DMS-9123956This author was supported by an NSF Postdoctoral Research Fellowship     

Sharp adaptation for spherical inverse problems with applications to medical imaging

This paper examines the estimation of an indirect signal embedded in white noise for the spherical case. It is found that the sharp minimax bound is determined by the degree to which the indirect signal is embedded in the linear operator. Thus, when the linear operator has polynomial decay, recovery of the signal is polynomial, whereas if the linear operator has exponential decay, recovery of the signal is logarithmic. The constants are determined for these classes as well. Adaptive sharp estimation is also carried out. In the polynomial case a blockwise shrinkage estimator is needed while in the exponential case, a straight projection estimator will suffice. The framework of this paper include applications to medical imaging, in particular, to cone beam image reconstruction and to diffusion magnetic resonance imaging. Discussion of these applications are included.     

Oracle Inequalities for Efromovich–Pinsker Blockwise Estimates

Oracle inequality is a relatively new statistical tool for the analysis of nonparametric adaptive estimates. Oracle is a good pseudo-estimate that is based on both data and an underlying estimated curve. An oracle inequality shows how well an adaptive estimator mimics the oracle for a particular underlying curve. The most advanced oracle inequalities have been recently obtained by Cavalier and Tsybakov (2001) for Stein type blockwise estimates used in filtering a signal from a stationary white Gaussian process. The authors also conjecture that a similar result can be obtained for Efromovich–Pinsker (EP) type blockwise estimators where their approach, based on Stein's formula for risk calculation, does not work. This article proves the conjecture and extends it upon more general models which include not stationary and dependent processes. Other possible extensions, a discussion of practical implications and a numerical study are also presented.     

A new expected-improvement algorithm for continuous minimax optimization

Worst-case design is important whenever robustness to adverse environmental conditions must be ensured regardless of their probability. It leads to minimax optimization, which is most often treated assuming that prior knowledge makes the worst environmental conditions obvious, or that a closed-form expression for the performance index is available. This paper considers the important situation where none of these assumptions is true and where the performance index must be evaluated via costly numerical simulations. Strategies to limit the number of these evaluations are then of paramount importance. One such strategy is proposed here, which further improves the performance of an algorithm recently presented that combines a relaxation procedure for minimax search with the well-known Kriging-based EGO algorithm. Expected Improvement is computed in the minimax optimization context, which allows to further reduce the number of costly evaluations of the performance index. The interest of the approach is demonstrated on test cases and a simple engineering problem from the literature, which facilitates comparison with alternative approaches.     

A lexicographic minimax algorithm for multiperiod resource allocation

Resource allocation problems are typically formulated as mathematical programs with some special structure that facilitates the development of efficient algorithms. We consider a multiperiod problem in which excess resources in one period can be used in subsequent periods. The objective minimizes lexicographically the nonincreasingly sorted vector of weighted deviations of cumulative activity levels from cumulative demands. To this end, we first develop a new minimax algorithm that minimizes the largest weighted deviation among all cumulative activity levels. The minimax algorithm handles resource constraints, ordering constraints, and lower and upper bounds. At each iteration, it fixes certain variables at their lower bounds, and sets groups of other variables equal to each other as long as no lower bounds are violated. The algorithm takes advantage of the problem's special structure; e.g., each term in the objective is a linear decreasing function of only one variable. This algorithm solves large problems very fast, orders of magnitude faster than well known linear programming packages. (The latter are, of course, not designed to solve such minimax problems efficiently.) The lexicographic procedure repeatedly employs the minimax algorithm described above to solve problems, each of the same format but with smaller dimension.     

Linearly constrained minimax optimization

We present an algorithm for nonlinear minimax optimization subject to linear equality and inequality constraints which requires first order partial derivatives. The algorithm is based on successive linear approximations to the functions defining the problem. The resulting linear subproblems are solved in the minimax sense subject to the linear constraints. This ensures a feasible-point algorithm. Further, we introduce local bounds on the solutions of the linear subproblems, the bounds being adjusted automatically, depending on the quality of the linear approximations. It is proved that the algorithm will always converge to the set of stationary points of the problem, a stationary point being defined in terms of the generalized gradients of the minimax objective function. It is further proved that, under mild regularity conditions, the algorithm is identical to a quadratically convergent Newton iteration in its final stages. We demonstrate the performance of the algorithm by solving a number of numerical examples with up to 50 variables, 163 functions, and 25 constraints. We have also implemented a version of the algorithm which is particularly suited for the solution of restricted approximation problems.This work has been supported by the Danish Natural Science Research Council, Grant No. 511-6874.     

On the efficiency of optimal grid synthesis in optimal control problems with fixed terminal time

In the paper, we consider nonlinear optimal control problems with the Bolza functional and with fixed terminal time. We suggest a construction of optimal grid synthesis. For each initial state of the control system, we obtain an estimate for the difference between the optimal result and the value of the functional on the trajectory generated by the suggested grid positional control. The considered feedback control constructions and the estimates of their efficiency are based on a backward dynamic programming procedure. We also use necessary and sufficient optimality conditions in terms of characteristics of the Bellman equation and the sub-differential of the minimax viscosity solution of this equation in the Cauchy problem specified for the fixed terminal time. The results are illustrated by the numerical solution of a nonlinear optimal control problem.     

Monotonicity of quadratic-approximation algorithms

It is desirable that a numerical maximization algorithm monotonically increase its objective function for the sake of its stability of convergence. It is here shown how one can adjust the Newton-Raphson procedure to attain monotonicity by the use of simple bounds on the curvature of the objective function. The fundamental tool in the analysis is the geometric insight one gains by interpreting quadratic-approximation algorithms as a form of area approximation. The statistical examples discussed include maximum likelihood estimation in mixture models, logistic regression and Cox's proportional hazards regression.The second author's research was partially supported by the National Science Foundation under Grant DMS-8402735.     

An estimate of the gradient characteristics and source intensity of an acoustic field

An algorithm is proposed for estimating characteristic wave processes in underwater acoustics. We obtain minimax mean-square estimates for functionals which determine the solutions and right sides of the Helmholtz equation. Relations are presented which are satisfied by the minimax estimates; results of numerical computations are also given.Translated fromVychislitel'naya i Prikladnaya Matematika, No. 69, pp. 128–134, 1989.     

Nonparametric estimation for irregularly sampled Lévy processes

We consider nonparametric statistical inference for Lévy processes sampled irregularly, at low frequency. The estimation of the jump dynamics as well as the estimation of the distributional density are investigated. Non-asymptotic risk bounds are derived and the corresponding rates of convergence are discussed under global as well as local regularity assumptions. Moreover, minimax optimality is proved for the estimator of the jump measure. Some numerical examples are given to illustrate the practical performance of the estimation procedure.     

Differential variational inequalities

This paper introduces and studies the class of differential variational inequalities (DVIs) in a finite-dimensional Euclidean space. The DVI provides a powerful modeling paradigm for many applied problems in which dynamics, inequalities, and discontinuities are present; examples of such problems include constrained time-dependent physical systems with unilateral constraints, differential Nash games, and hybrid engineering systems with variable structures. The DVI unifies several mathematical problem classes that include ordinary differential equations (ODEs) with smooth and discontinuous right-hand sides, differential algebraic equations (DAEs), dynamic complementarity systems, and evolutionary variational inequalities. Conditions are presented under which the DVI can be converted, either locally or globally, to an equivalent ODE with a Lipschitz continuous right-hand function. For DVIs that cannot be so converted, we consider their numerical resolution via an Euler time-stepping procedure, which involves the solution of a sequence of finite-dimensional variational inequalities. Borrowing results from differential inclusions (DIs) with upper semicontinuous, closed and convex valued multifunctions, we establish the convergence of such a procedure for solving initial-value DVIs. We also present a class of DVIs for which the theory of DIs is not directly applicable, and yet similar convergence can be established. Finally, we extend the method to a boundary-value DVI and provide conditions for the convergence of the method. The results in this paper pertain exclusively to systems with “index” not exceeding two and which have absolutely continuous solutions. The work of J.-S. Pang is supported by the National Science Foundation under grants CCR-0098013 CCR-0353074, and DMS-0508986, by a Focused Research Group Grant DMS-0139715 to the Johns Hopkins University and DMS-0353016 to Rensselaer Polytechnic Institute, and by the Office of Naval Research under grant N00014-02-1-0286. The work of D. E. Stewart is supported by the National Science Foundation under a Focused Research Group grant DMS-0138708.     

Eigenvalue perturbation bounds for Hermitian block tridiagonal matrices

We derive new perturbation bounds for eigenvalues of Hermitian matrices with block tridiagonal structure. The main message of this paper is that an eigenvalue is insensitive to blockwise perturbation, if it is well-separated from the spectrum of the diagonal blocks nearby the perturbed blocks. Our bound is particularly effective when the matrix is block-diagonally dominant and graded. Our approach is to obtain eigenvalue bounds via bounding eigenvector components, which is based on the observation that an eigenvalue is insensitive to componentwise perturbation if the corresponding eigenvector components are small. We use the same idea to explain two well-known phenomena, one concerning aggressive early deflation used in the symmetric tridiagonal QR algorithm and the other concerning the extremal eigenvalues of Wilkinson matrices.     

Ridge Fusion in Statistical Learning

This article proposes a penalized likelihood method to jointly estimate multiple precision matrices for use in quadratic discriminant analysis (QDA) and model-based clustering. We use a ridge penalty and a ridge fusion penalty to introduce shrinkage and promote similarity between precision matrix estimates. We use blockwise coordinate descent for optimization, and validation likelihood is used for tuning parameter selection. Our method is applied in QDA and semi-supervised model-based clustering.     

GMRES and the minimal polynomial

We present a qualitative model for the convergence behaviour of the Generalised Minimal Residual (GMRES) method for solving nonsingular systems of linear equationsAx =b in finite and infinite dimensional spaces. One application of our methods is the solution of discretised infinite dimensional problems, such as integral equations, where the constants in the asymptotic bounds are independent of the mesh size.Our model provides simple, general bounds that explain the convergence of GMRES as follows: If the eigenvalues ofA consist of a single cluster plus outliers then the convergence factor is bounded by the cluster radius, while the asymptotic error constant reflects the non-normality ofA and the distance of the outliers from the cluster. If the eigenvalues ofA consist of several close clusters, then GMRES treats the clusters as a single big cluster, and the convergence factor is the radius of this big cluster. We exhibit matrices for which these bounds are tight.Our bounds also lead to a simpler proof of existing r-superlinear convergence results in Hilbert space.This research was partially supported by National Science Foundation grants DMS-9122745, DMS-9423705, CCR-9102853, CCR-9400921, DMS-9321938, DMS-9020915, and DMS-9403224.     

On the convergence of operator splitting for the Rosenau–Burgers equation

We present convergence analysis of operator splitting methods applied to the nonlinear Rosenau–Burgers equation. The equation is first splitted into an unbounded linear part and a bounded nonlinear part and then operator splitting methods of Lie‐Trotter and Strang type are applied to the equation. The local error bounds are obtained by using an approach based on the differential theory of operators in Banach space and error terms of one and two‐dimensional numerical quadratures via Lie commutator bounds. The global error estimates are obtained via a Lady Windermere's fan argument. Lastly, a numerical example is studied to confirm the expected convergence order.     

Hidden convexity in some nonconvex quadratically constrained quadratic programming

We consider the problem of minimizing an indefinite quadratic objective function subject to twosided indefinite quadratic constraints. Under a suitable simultaneous diagonalization assumption (which trivially holds for trust region type problems), we prove that the original problem is equivalent to a convex minimization problem with simple linear constraints. We then consider a special problem of minimizing a concave quadratic function subject to finitely many convex quadratic constraints, which is also shown to be equivalent to a minimax convex problem. In both cases we derive the explicit nonlinear transformations which allow for recovering the optimal solution of the nonconvex problems via their equivalent convex counterparts. Special cases and applications are also discussed. We outline interior-point polynomial-time algorithms for the solution of the equivalent convex programs. This author's work was partially supported by GIF, the German-Israeli Foundation for Scientific Research and Development and by the Binational Science Foundation. This author's work was partially supported by National Science Foundation Grants DMS-9201297 and DMS-9401871.     

EMPIRICAL LIKELIHOOD APPROACH FOR LONGITUDINAL DATA WITH MISSING VALUES AND TIME-DEPENDENT COVARIATES

Missing data and time-dependent covariates often arise simultaneously in longitudinal studies, and directly applying classical approaches may result in a loss of efficiency and biased estimates. To deal with this problem, we propose weighted corrected estimating equations under the missing at random mechanism, followed by developing a shrinkage empirical likelihood estimation approach for the parameters of interest when time-dependent covariates are present. Such procedure improves efficiency over generalized estimation equations approach with working independent assumption, via combining the independent estimating equations and the extracted additional information from the estimating equations that are excluded by the independence assumption. The contribution from the remaining estimating equations is weighted according to the likelihood of each equation being a consistent estimating equation and the information it carries. We show that the estimators are asymptotically normally distributed and the empirical likelihood ratio statistic and its profile counterpart follow central chi-square distributions asymptotically when evaluated at the true parameter. The practical performance of our approach is demonstrated through numerical simulations and data analysis.