Abstract We establish a new perturbation theory for orthogonal polynomials using a Riemann–Hilbert approach and consider applications in numerical linear algebra and random matrix theory. This new approach shows that the orthogonal polynomials with respect to two measures can be effectively compared using the difference of their Stieltjes transforms on a suitably chosen contour. Moreover, when two measures are close and satisfy some regularity conditions, we use the theta functions of a hyperelliptic Riemann surface to derive explicit and accurate expansion formulae for the perturbed orthogonal polynomials. In contrast to other approaches, a key strength of the methodology is that estimates can remain valid as the degree of the polynomial grows. The results are applied to analyze several numerical algorithms from linear algebra, including the Lanczos tridiagonalization procedure, the Cholesky factorization, and the conjugate gradient algorithm. As a case study, we investigate these algorithms applied to a general spiked sample covariance matrix model by considering the eigenvector empirical spectral distribution and its limits. For the first time, we give precise estimates on the output of the algorithms, applied to this wide class of random matrices, as the number of iterations diverges. In this setting, beyond the first order expansion, we also derive a new mesoscopic central limit theorem for the associated orthogonal polynomials and other quantities relevant to numerical algorithms.
more »
« less
Dimension Quasi-polynomials of Inversive Difference Field Extensions with Weighted Translations
We consider Hilbert-type functions associated with finitely
generated inversive difference field extensions and systems of
algebraic difference equations in the case when the translations are
assigned positive integer weights. We prove that such functions are
quasi-polynomials that can be represented as alternating sums of
Ehrhart quasi-polynomials of rational conic polytopes. In
particular, we generalize the author's results on difference
dimension polynomials and their invariants to the case of inversive
difference fields with weighted basic automorphisms.
more »
« less
- Award ID(s):
- 1714425
- NSF-PAR ID:
- 10066958
- Date Published:
- Journal Name:
- Mathematical Aspects of Computer and Information Sciences
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)We present approximation and exact algorithms for piecewise regression of univariate and bivariate data using fixed-degree polynomials. Specifically, given a set S of n data points (x1, y1), . . . , (xn, yn) ∈ Rd × R where d ∈ {1, 2}, the goal is to segment xi’s into some (arbitrary) number of disjoint pieces P1, . . . , Pk, where each piece Pj is associated with a fixed-degree polynomial fj : Rd → R, to minimize the total loss function λk+ni=1(yi −f(xi))2, where λ ≥ 0 is a regularization term that penalizes model complexity (number of pieces) and f : kj=1 Pj → R is the piecewise polynomial function defined as f|Pj = fj. The pieces P1,...,Pk are disjoint intervals of R in the case of univariate data and disjoint axis-aligned rectangles in the case of bivariate data. Our error approximation allows use of any fixed-degree polynomial, not just linear functions. Our main results are the following. For univariate data, we present a (1 + ε)-approximation algorithm with time complexity O(nε log1ε), assuming that data is presented in sorted order of xi’s. For bivariate data, we √ present three results: a sub-exponential exact algorithm with running time nO( n); a polynomial-time constant- approximation algorithm; and a quasi-polynomial time approximation scheme (QPTAS). The bivariate case is believed to be NP-hard in the folklore but we could not find a published record in the literature, so in this paper we also present a hardness proof for completeness.more » « less
-
null (Ed.)Abstract We introduce two new bases of the ring of polynomials and study their relations to known bases. The first basis is the quasi-Lascoux basis, which is simultaneously both a $K$ -theoretic deformation of the quasi-key basis and also a lift of the $K$ -analogue of the quasi-Schur basis from quasi-symmetric polynomials to general polynomials. We give positive expansions of this quasi-Lascoux basis into the glide and Lascoux atom bases, as well as a positive expansion of the Lascoux basis into the quasi-Lascoux basis. As a special case, these expansions give the first proof that the $K$ -analogues of quasi-Schur polynomials expand positively in multifundamental quasi-symmetric polynomials of T. Lam and P. Pylyavskyy. The second new basis is the kaon basis, a $K$ -theoretic deformation of the fundamental particle basis. We give positive expansions of the glide and Lascoux atom bases into this kaon basis. Throughout, we explore how the relationships among these $K$ -analogues mirror the relationships among their cohomological counterparts. We make several “alternating sum” conjectures that are suggestive of Euler characteristic calculations.more » « less
-
We present a difference algebraic technique for the evaluation of the Einstein's strength of quasi-linear partial difference equations and some systems of such equations. Our approach is based on the properties of difference dimension polynomials that express the Einstein's strength and on the characteristic set method for computing such polynomials. The obtained results are applied to the comparative analysis of difference schemes for some chemical reaction-diffusion equations.more » « less
-
null (Ed.)To Nicolás Andruskiewitsch on his 60th birthday, with admiration We introduce bivariate versions of the continuous [Formula: see text]-Hermite polynomials. We obtain algebraic properties for them (generating function, explicit expressions in terms of the univariate ones, backward difference equations and recurrence relations) and analytic properties (determining the orthogonality measure). We find a direct link between bivariate continuous [Formula: see text]-Hermite polynomials and the star product method of [S. Kolb and M. Yakimov, Symmetric pairs for Nichols algebras of diagonal type via star products, Adv. Math. 365 (2020), Article ID: 107042, 69 pp.] for quantum symmetric pairs to establish deformed quantum Serre relations for quasi-split quantum symmetric pairs of Kac–Moody type. We prove that these defining relations are obtained from the usual quantum Serre relations by replacing all monomials by multivariate orthogonal polynomials.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
