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.

Given partially observed pairwise comparison data generated by the Bradley–Terry–Luce (BTL) model, we study the problem of top-k ranking. That is, to optimally identify the set of top-k players. We derive the minimax rate with respect to a normalized Hamming loss. This provides the first result in the literature that characterizes the partial recovery error in terms of the proportion of mistakes for top-k ranking. We also derive the optimal signal to noise ratio condition for the exact recovery of the top-k set. The maximum likelihood estimator (MLE) is shown to achieve both optimal partial recovery and optimal exact recovery. On the other hand, we show another popular algorithm, the spectral method, is in general suboptimal. Our results complement the recent work (Ann. Statist. 47 (2019) 2204–2235) that shows both the MLE and the spectral method achieve the optimal sample complexity for exact recovery. It turns out the leading constants of the sample complexity are different for the two algorithms. Another contribution that may be of independent interest is the analysis of the MLE without any penalty or regularization for the BTL model. This closes an important gap between theory and practice in the literature of ranking.

We consider fully discrete schemes based on the scalar auxiliary variable (SAV) approach and stabilized SAV approach in time and the Fourier-spectral method in space for the phase field crystal (PFC) equation. Unconditionally, energy stability is established for both first- and second-order fully discrete schemes. In addition to the stability, we also provide a rigorous error estimate which shows that our second-order in time with Fourier-spectral method in space converges with order O(Δt2 + N−m), where Δt, N, and m are time step size, number of Fourier modes in each direction, and regularity index in space, respectively. We also present numerical experiments to verify our theoretical results and demonstrate the robustness and accuracy of the schemes.

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.

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.

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.

Physics-informed Neural Networks (PINNs) have emerged as a popular method for solving both forward and inverse differential equations. However, the automatic differentiation techniques employed by PINNs face challenges when solving fractional-order equations. To address this issue, we propose a spectral method-based fractional PINN framework, referred to as spectral-fPINNs. This method adopts a more efficient global discretization approach based on Jacobi polynomials, which reduces the need for auxiliary points. Meanwhile, the transformation between physical value and expansion coefficients is computed efficiently by a standard matrix–vector multiplication, thereby increasing the efficiency of the algorithm. An error analysis of spectral-fPINNs is performed, and their performance is validated through a series of numerical examples. First, we assess the accuracy, stability, and efficiency of the proposed method in solving steady-state fractional partial differential equations, including a detailed error analysis under varying parameter settings. Next, we extend the evaluation to more complex time-dependent equations. In addition, we demonstrate the application of this method in financial modeling, different types of fractional-order equations, and inverse problems. These results highlight the distinct advantages of spectral-fPINNs, particularly their efficiency in solving fractional partial differential equations.

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.