More Like this

1. Stable super-resolution of images: theoretical study

   https://doi.org/10.1093/imaiai/iaaa029  

   Eftekhari, Armin ; Bendory, Tamir ; Tang, Gongguo ( November 2020 , Information and Inference: A Journal of the IMA)

   null (Ed.)

   Abstract We study the ubiquitous super-resolution 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 non-negative 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 one-dimensional signals, we prove that this super-resolution 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 well-separated point sources. As an example, we verify these claims for the important case of a Gaussian point spread function. The proofs rely on the construction of novel interpolating polynomials—which are the main technical contribution of this paper—and partially resolve the question raised in Schiebinger et al. (2017, Inf. Inference, 7, 1–30) about the extension of the standard machinery to higher dimensions. 

   more » « less
2. Sparse Recovery for Orthogonal Polynomial Transforms

   https://doi.org/10.4230/LIPIcs.ICALP.2020.58  

   Gilbert, Anna ; Gu, Albert ; Re, Christopher ; Rudra, Atri ; Wootters, Mary ( June 2020 , Leibniz international proceedings in informatics)

   null (Ed.)

   In this paper we consider the following sparse recovery problem. We have query access to a vector 𝐱 ∈ ℝ^N such that x̂ = 𝐅 𝐱 is k-sparse (or nearly k-sparse) for some orthogonal transform 𝐅. The goal is to output an approximation (in an 𝓁₂ sense) to x̂ in sublinear time. This problem has been well-studied 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 sublinear-time 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 we require an assumption on the sparsity structure of the sparse vector, although we note that vectors with random support have this property with high probability. Our approach is to give a very general reduction from the k-sparse sparse recovery problem to the 1-sparse sparse recovery problem that holds for any flat orthogonal polynomial transform; then we solve this one-sparse recovery problem for transforms derived from Jacobi polynomials. Frequently, sparse FFT algorithms are described as implementing such a reduction; however, the technical details of such works are quite specific to the Fourier transform and moreover the actual implementations of these algorithms do not use the 1-sparse algorithm as a black box. In this work we give a reduction that works for a broad class of orthogonal polynomial families, and which uses any 1-sparse recovery algorithm as a black box. 

   more » « less
3. Unsteady aerodynamics of porous aerofoils

   https://doi.org/10.1017/jfm.2020.1031  

   Baddoo, Peter J. ; Hajian, Rozhin ; Jaworski, Justin W. ( April 2021 , Journal of Fluid Mechanics)

   null (Ed.)

   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, quasi-static problems and the separation of circulatory and non-circulatory 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 region develops near the trailing edge and the effective mass of the porous medium dominates. Analogues to the classical Theodorsen and Sears functions are computed numerically, and Fourier transform inversion of these frequency-domain functions produces porous extensions to the Wagner and Küssner functions for transient aerofoil motions or gust encounters, respectively. Results from the present analysis and its underpinning numerical framework aim to enable the unsteady aerodynamic assessment of design strategies using porosity, with implications for unsteady gust rejection, noise-reducing aerofoil design and biologically inspired flight. 

   more » « less
4. Semiring Provenance for Fixed-Point Logic

   https://doi.org/10.4230/LIPIcs.CSL.2021.17  

   Dannert, K ; Graedel, E ; Naaf, N ; Tannen, V ( January 2021 , Conference on Computer Science Logic, CSL 2021,)

   null (Ed.)

   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 fixed-point 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 model-checking games. Interestingly, the common approach based on Kleene’s Fixed-Point Theorem for ω-continuous semirings is not sufficient for these general languages. We show that an adequate framework for the provenance analysis of full fixed-point logics is provided by semirings that are (1) fully continuous, and (2) absorptive. Full continuity guarantees that provenance values of least and greatest fixed-points are well-defined. Absorptive semirings provide a symmetry between least and greatest fixed-points and make sure that provenance values of greatest fixed points are informative. We identify semirings of generalized absorptive polynomials S∞[X] and prove universal properties that make them the most general appropriate semirings for our framework. These semirings have the further property of being (3) chain-positive, which is responsible for having truth-preserving interpretations that give non-zero values to all true formulae. We relate the provenance analysis of fixed-point formulae with provenance values of plays and strategies in the associated model-checking games. Specifically, we prove that the provenance value of a fixed point formula gives precise information on the evaluation strategies in these games. 

   more » « less
5. Determinant Maximization via Matroid Intersection Algorithms

   Brown, A ; Laddha, A. ; Pittu, M. ; Singh, M. ; Tetali, P. ( October 2022 , Annual Symposium on Foundations of Computer Science)

   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 polynomial-time 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 log-concave polynomials. In contrast, our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improve any solution by finding an alternating negative cycle in the exchange graph defined by the matroids. While the det(.) function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm. 

   more » « less