Abstract We study the ubiquitous superresolution problem, in which one aims at localizing positive point sources in an image, blurred by the point spread function of the imaging device. To recover the point sources, we propose to solve a convex feasibility program, which simply finds a nonnegative Borel measure that agrees with the observations collected by the imaging device. In the absence of imaging noise, we show that solving this convex program uniquely retrieves the point sources, provided that the imaging device collects enough observations. This result holds true if the point spread function of the imaging device can be decomposed into horizontal and vertical components and if the translations of these components form a Chebyshev system, i.e., a system of continuous functions that loosely behave like algebraic polynomials. Building upon the recent results for onedimensional signals, we prove that this superresolution algorithm is stable, in the generalized Wasserstein metric, to model mismatch (i.e., when the image is not sparse) and to additive imaging noise. In particular, the recovery error depends on the noise level and how well the image can be approximated with wellseparated point sources. As an example, we verify these claims for the important case of amore »
Lower and Upper Bounds for Positive Bases of Skein Algebras
Abstract We show that if a sequence of normalized polynomials gives rise to a positive basis of the skein algebra of a surface, then it is sandwiched between the two types of Chebyshev polynomials. For the closed torus, we show that the normalized sequence of Chebyshev polynomials of type one $(\hat{T}_n)$ is the only one that gives a positive basis.
 Publication Date:
 NSFPAR ID:
 10219417
 Journal Name:
 International Mathematics Research Notices
 Volume:
 2021
 Issue:
 4
 Page Range or eLocationID:
 3186 to 3202
 ISSN:
 10737928
 Sponsoring Org:
 National Science Foundation
More Like this


In this paper we consider the following sparse recovery problem. We have query access to a vector 𝐱 ∈ ℝ^N such that x̂ = 𝐅 𝐱 is ksparse (or nearly ksparse) for some orthogonal transform 𝐅. The goal is to output an approximation (in an 𝓁₂ sense) to x̂ in sublinear time. This problem has been wellstudied in the special case that 𝐅 is the Discrete Fourier Transform (DFT), and a long line of work has resulted in sparse Fast Fourier Transforms that run in time O(k ⋅ polylog N). However, for transforms 𝐅 other than the DFT (or closely related transforms like the Discrete Cosine Transform), the question is much less settled. In this paper we give sublineartime algorithms  running in time poly(k log(N))  for solving the sparse recovery problem for orthogonal transforms 𝐅 that arise from orthogonal polynomials. More precisely, our algorithm works for any 𝐅 that is an orthogonal polynomial transform derived from Jacobi polynomials. The Jacobi polynomials are a large class of classical orthogonal polynomials (and include Chebyshev and Legendre polynomials as special cases), and show up extensively in applications like numerical analysis and signal processing. One caveat of our work is that wemore »

Semiring provenance is a successful approach, originating in database theory, to providing detailed information on how atomic facts combine to yield the result of a query. In particular, general provenance semirings of polynomials or formal power series provide precise descriptions of the evaluation strategies or “proof trees” for the query. By evaluating these descriptions in specific application semirings, one can extract practical information for instance about the confidence of a query or the cost of its evaluation. This paper develops semiring provenance for very general logical languages featuring the full interaction between negation and fixedpoint inductions or, equivalently, arbitrary interleavings of least and greatest fixed points. This also opens the door to provenance analysis applications for modal μcalculus and temporal logics, as well as for finite and infinite modelchecking games. Interestingly, the common approach based on Kleene’s FixedPoint Theorem for ωcontinuous semirings is not sufficient for these general languages. We show that an adequate framework for the provenance analysis of full fixedpoint logics is provided by semirings that are (1) fully continuous, and (2) absorptive. Full continuity guarantees that provenance values of least and greatest fixedpoints are welldefined. Absorptive semirings provide a symmetry between least and greatest fixedpoints and makemore »

We extend unsteady thin aerofoil theory to aerofoils with generalised chordwise porosity distributions by embedding the material characteristics of the porous medium into the linearised boundary condition. Application of the Plemelj formulae to the resulting boundary value problem yields a singular Fredholm–Volterra integral equation which does not admit an analytical solution. We develop a numerical solution scheme by expanding the bound vorticity distribution in terms of appropriate basis functions. Asymptotic analysis at the leading and trailing edges reveals that the appropriate basis functions are weighted Jacobi polynomials whose parameters are related to the porosity distribution. The Jacobi polynomial basis enables the construction of a numerical scheme that is accurate and rapid, in contrast to the standard choice of Chebyshev basis functions that are shown to be unsuitable for porous aerofoils. Applications of the numerical solution scheme to discontinuous porosity profiles, quasistatic problems and the separation of circulatory and noncirculatory contributions are presented. Further asymptotic analysis of the singular Fredholm–Volterra integral equation corroborates the numerical scheme and elucidates the behaviour of the unsteady solution for small or large reduced frequency in the form of scaling laws. At low frequencies, the porous resistance dominates, whereas at high frequencies, an asymptotic inner regionmore »

Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics [Puk06], convex geometry [Kha96], fair allocations [AGSS16], combinatorics [AGV18], spectral graph theory [NST19a], network design, and random processes [KT12]. In an instance of a determinant maximization problem, we are given a collection of vectors U = {v1, . . . , vn} ⊂ Rd , and a goal is to pick a subset S ⊆ U of given vectors to maximize the determinant of the matrix ∑i∈S vivi^T. Often, the set S of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint (S ≤ k) or matroid constraint (S is a basis of a matroid defined on the vectors). In this paper, we give a polynomialtime deterministic algorithm that returns a r O(r)approximation for any matroid of rank r ≤ d. This improves previous results that give e O(r^2)approximation algorithms relying on e^O(r)approximate estimation algorithms [NS16, AG17,AGV18, MNST20] for any r ≤ d. All previous results use convex relaxations and their relationship to stable polynomials and strongly logconcave polynomials. In contrast, our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improve any solution by finding an alternating negative cyclemore »