Explore the vast range of titles available.

This paper is concerned with the problem of top-K ranking from pairwise comparisons. Given a collection of n items and a few pairwise comparisons across them, one wishes to identify the set of K items that receive the highest ranks. To tackle this problem, we adopt the logistic parametric model—the Bradley–Terry–Luce model, where each item is assigned a latent preference score, and where the outcome of each pairwise comparison depends solely on the relative scores of the two items involved. Recent works have made significant progress toward characterizing the performance (e.g., the mean square error for estimating the scores) of several classical methods, including the spectral method and the maximum likelihood estimator (MLE). However, where they stand regarding top-K ranking remains unsettled. We demonstrate that under a natural random sampling model, the spectral method alone, or the regularized MLE alone, is minimax optimal in terms of the sample complexity—the number of paired comparisons needed to ensure exact top-K identification, for the fixed dynamic range regime. This is accomplished via optimal control of the entrywise error of the score estimates. We complement our theoretical studies by numerical experiments, confirming that both methods yield low entrywise errors for estimating the underlying scores. Our theory is established via a novel leave-one-out trick, which proves effective for analyzing both iterative and noniterative procedures. Along the way, we derive an elementary eigenvector perturbation bound for probability transition matrices, which parallels the Davis–Kahan sin Θ theorem for symmetric matrices. This also allows us to close the gap between the ℓ2 error upper bound for the spectral method and the minimax lower limit.

In this paper, a new alternating direction implicit Galerkin–Legendre spectral method for the two-dimensional Riesz space fractional nonlinear reaction-diffusion equation is developed. The temporal component is discretized by the Crank–Nicolson method. The detailed implementation of the method is presented. The stability and convergence analysis is strictly proven, which shows that the derived method is stable and convergent of order 2 in time. An optimal error estimate in space is also obtained by introducing a new orthogonal projector. The present method is extended to solve the fractional FitzHugh–Nagumo model. Numerical results are provided to verify the theoretical analysis.

This paper is concerned with estimating the column space of an unknown low-rank matrix A * ∈ ℝ d 1 × d 2 , given noisy and partial observations of its entries. There is no shortage of scenarios where the observations—while being too noisy to support faithful recovery of the entire matrix—still convey sufficient information to enable reliable estimation of the column space of interest. This is particularly evident and crucial for the highly unbalanced case where the column dimension d 2 far exceeds the row dimension d 1, which is the focal point of the current paper. We investigate an efficient spectral method, which operates upon the sample Gram matrix with diagonal deletion. While this algorithmic idea has been studied before, we establish new statistical guarantees for this method in terms of both ℓ2 and ℓ2,∞ estimation accuracy, which improve upon prior results if d 2 is substantially larger than d 1. To illustrate the effectiveness of our findings, we derive matching minimax lower bounds with respect to the noise levels, and develop consequences of our general theory for three applications of practical importance: (1) tensor completion from noisy data, (2) covariance estimation/principal component analysis with missing data and (3) community recovery in bipartite graphs. Our theory leads to improved performance guarantees for all three cases.

For the first time in literature, semi-implicit spectral approximations for nonlinear Caputo time- and Riesz space-fractional diffusion equations with both smooth and non-smooth solutions are proposed. More precisely, the governing partial differential equation generalizes the Hodgkin–Huxley, the Allen–Cahn and the Fisher–Kolmogorov–Petrovskii–Piscounov equations. The schemes employ a Legendre-based Galerkin spectral method for the Riesz space-fractional derivative, and L 1-type approximations with both uniform and graded meshes for the Caputo time-fractional derivative. More importantly, by using fractional Gronwall inequalities and their associated discrete forms, sharp error estimates are proved which show an enhancement in the convergence rate compared with the standard L 1 approximation on uniform meshes. This analysis encompasses both uniform meshes as well as meshes that are graded in time, and guarantees the unconditional stability. The numerical results that accompany our analysis confirm our theoretical error estimates, and give significant insights into the convergence behavior of our schemes for problems with smooth and non-smooth solutions.

We prove the convergence of a spectral discretization of the Vlasov-Poisson system. The velocity term of the Vlasov equation is discretized using either Hermite functions on the infinite domain or Legendre polynomials on a bounded domain. The spatial term of the Vlasov and Poisson equations is discretized using periodic Fourier expansions. Boundary conditions are treated in weak form through a penalty type term that can be applied also in the Hermite case. As a matter of fact, stability properties of the approximated scheme descend from this added term. The convergence analysis is carried out in detail for the 1D-1V case, but results can be generalized to multidimensional domains, obtained as Cartesian product, in both space and velocity. The error estimates show the spectral convergence under suitable regularity assumptions on the exact solution.

Many chemical systems exhibit a range of patterns, a noticeable and interesting class of numerical patterns that arise in autocatalytic reactions which changes with increasing spatial domains. In this paper, autocatalytic spatiotemporal patterns were demonstrated using the system of chemical species modeled with the time-fractional Caputo derivatives of subdiffusive orders. It is not new that a spectral algorithm with its entire nature is more accurate when compared with a finite-difference scheme to solve a range of integer and non-integer order time partial differential equations. This is because the Fourier spectral techniques have the upper hand on high-order spectral accuracy, and are computationally efficient. Hence, it is regarded as the best approach to existing lower-order methods for integrating the second-order partial derivatives in space. This motivates the present study to explore the usefulness of Fourier spectral methods in resolving and obtaining complex Turing patterns arising from nonlinear fractional autocatalytic reaction-diffusion problems in high dimensions. The autocatalysis model was examines for linear stability in an attempt to obtain the correct choice of parameters that are likely to lead to the formation of new complex turing-like patterns. Numerical experiments in the 2D lead to a striking range of patterns arising from catalytic reactions of fractional-order labyrinthine pattern-like structures. Analysis of pattern formation was also extended to 3D dynamics to obtain a new set of patterns like a star-, cyclic-, diamond-like, and the emergence of apple-shaped structures, which are greatly influenced by either the choice parameters that are involved or that of the initial conditions.

We propose and analyze a multiscale time integrator Fourier pseudospectral (MTI-FP) method for solving the Klein–Gordon (KG) equation with a dimensionless parameter 0 < ε ≤ 1 which is inversely proportional to the speed of light. In the nonrelativistic limit regime, i.e., 0 < ε ≪ 1, the solution of the KG equation propagates waves with amplitude at O(1) and wavelength at O(ε2) in time and O(1) in space, which causes significantly numerical burdens due to the high oscillation in time. The MTI-FP method is designed by adapting a multiscale decomposition by frequency (MDF) to the solution at each time step and applying an exponential wave integrator to the nonlinear Schrödinger equation with wave operator under well-prepared initial data for ε2-frequency and O(1)-amplitude waves and a KG-type equation with small initial data for the reminder waves in the MDF. We rigorously establish two independent error bounds in H2-norm to the MTI-FP method at $\\mathrm{O}({\\mathrm{h}}^{{\\mathrm{m}}_{0}}+{\\mathrm{\\tau }}^{2}+{\\mathrm{\\varepsilon }}^{2})$ and $\\mathrm{O}({\\mathrm{h}}^{{\\mathrm{m}}_{0}}+{\\mathrm{\\tau }}^{2}+{\\mathrm{\\varepsilon }}^{2})$ with h mesh size, τ time step, and m0 ≥ 2 an integer depending on the regularity of the solution, which immediately imply that the MTI-FP converges uniformly and optimally in space with exponential convergence rate if the solution is smooth, and uniformly in time with linear convergence rate at O(τ) for all ε ∈ (0, 1] and optimally with quadratic convergence rate at O(τ2) in the regimes when eithe ε = O(1) or 0 < ε ≤ τ. Numerical results are reported to confirm the error bounds and demonstrate the efficiency and accuracy of the MTI-FP method for the KG equation, especially in the nonrelativistic limit regime.

The main aim of this paper is to construct an efficient Galerkin–Legendre spectral approximation combined with a finite difference formula of L 1 type to numerically solve the generalized nonlinear fractional Schrödinger equation with both space- and time-fractional derivatives. We discretize the Riesz space-fractional derivative using the Legendre–Galerkin spectral method and the time-fractional derivative using the L 1 scheme on nonuniform meshes. The stability and convergence analyses of the numerical scheme are studied in detail. The scheme is unconditionally stable and convergent of min { κ θ , 2 - θ } order convergence in time and of spectral accuracy in space, where θ is the order of fractional derivative and κ is the grading mesh parameter. To verify the efficiency of the proposed algorithm, two numerical test problems are performed with convergence and error analysis.

In this paper, we investigate Petrov–Galerkin spectral element spectral method for mixed inhomogeneous boundary value problems defined on polyhedrons. Some results on three-dimensional Legendre quasi-orthogonal approximation in certain Jacobi weighted Sobolev spaces are established. These results play an important role in numerical solutions of partial differential equations defined on polyhedrons. As examples of applications, spectral element schemes are provided for two model problems, with the global spectral accuracy. Efficient numerical implementations are described. Numerical results demonstrate the high efficiency of suggested algorithms.

We first develop a spectrally accurate Petrov--Galerkin spectral method for fractional delay differential equations (FDDEs). This scheme is developed based on a new spectral theory for fractional Sturm--Liouville problems (FSLPs), which has been recently presented in [M. Zayernouri and G. E. Karniadakis, J. Comput. Phys. , 252 (2013), pp. 495--517]. Specifically, we obtain solutions to FDDEs in terms of new nonpolynomial basis functions, called Jacobi polyfractonomials , which are the eigenfunctions of the FSLP of the first kind (FSLP-I). Correspondingly, we employ another space of test functions as the span of polyfractonomial eigenfunctions of the FSLP of the second kind (FSLP-II). We prove the wellposedness of the problem and carry out the corresponding stability and error analysis of the PG spectral method. In contrast to standard (nondelay) fractional differential equations, the delay character of FDDEs might induce solutions, which are either nonsmooth or piecewise smooth. In order to effectively treat such cases, we first develop a discontinuous spectral method (DSM) of Petrov--Galerkin type for FDDEs, where the basis functions do not satisfy the initial conditions. Consequently, we extend the DSM scheme to a discontinuous spectral element method (DSEM) for possible adaptive refinement and long time-integration. In DSM and DSEM schemes, we employ the asymptotic eigensolutions to FSLP-I and FSLP-II, which are of Jacobi polynomial form, both as basis and test functions. Our numerical tests demonstrate spectral convergence for a wide range of FDDE model problems with different benchmark solutions.