Super-Resolution from Noisy Data

This paper studies the recovery of a superposition of point sources from noisy bandlimited data. In the fewest possible words, we only have information about the spectrum of an object in the low-frequency band [?f _lo,f _lo] and seek to obtain a higher resolution estimate by extrapolating the spectrum up to a frequency f _hi>f _lo. We show that as long as the sources are separated by 2/f _lo, solving a simple convex program produces a stable estimate in the sense that the approximation error between the higher-resolution reconstruction and the truth is proportional to the noise level times the square of the super-resolution factor (SRF) f _hi/f _lo.     

Note on the reconstruction of infinite graphs with a fixed finite number of components

For every positive integer c, we construct a pair G_c, H_c of infinite, nonisomorphic graphs both having exactly c components such that G_c and H_c are hypomorphic, i.e., G_c and H_c have the same families of vertex-deleted subgraphs. This solves a problem of Bondy and Hemminger. Furthermore, the pair G₁, H₁ is an example for a pair of non-isomorphic, hypomorphic, connected graphs also having connected complements—a property not shared by any of the previously known counterexamples to the reconstruction conjecture for infinite graphs.     

Pf ≠ NPf for almost all f

We discuss the question of Ralf‐Dieter Schindler whether for infinite time Turing machines P^f = NP^f can be true for any function f from the reals into ω₁. We show that “almost everywhere” the answer is negative.     

An algorithm for selecting a good value for the parameter c in radial basis function interpolation

The accuracy of many schemes for interpolating scattered data with radial basis functions depends on a shape parameter c of the radial basis function. In this paper we study the effect of c on the quality of fit of the multiquadric, inverse multiquadric and Gaussian interpolants. We show, numerically, that the value of the optimal c (the value of c that minimizes the interpolation error) depends on the number and distribution of data points, on the data vector, and on the precision of the computation. We present an algorithm for selecting a good value for c that implicitly takes all the above considerations into account. The algorithm selects c by minimizing a cost function that imitates the error between the radial interpolant and the (unknown) function from which the data vector was sampled. The cost function is defined by taking some norm of the error vector E = (E ₁, ... , E_N)^T where E _k = E_k = f_k - S^k x_k) and S _k is the interpolant to a reduced data set obtained by removing the point x _k and the corresponding data value f _k from the original data set. The cost function can be defined for any radial basis function and any dimension. We present the results of many numerical experiments involving interpolation of two dimensional data sets by the multiquadric, inverse multiquadric and Gaussian interpolants and we show that our algorithm consistently produces good values for the parameter c. This revised version was published online in June 2006 with corrections to the Cover Date.     

Integral representation with respect to stopped continuous local martingales

We consider a Markovian jump process θ, with finite state space, feeding the parameters of a nonlinear diffusion process X. We observe θ and X in white noise, and—given a function f—we want to construct a finite filter for the f(X _t )-process. An algorithm is investigated which will produce a finite filter if it halts after a finite number of steps, and we give necessary and. sufficient conditions for this to happen.     

A refined Schwarz inequality on the boundary

We consider a function f holomorphic in the unit disc D with f(D)???D and f(0)?=?f(z ₀)?=?0, for 0?<?|z ₀|?<?1. We obtain sharp lower bounds on the angular derivative f′(c) at the point c where |c|?=?|f(c)|?=?1.     

An Arc as the Inverse Limit of a Single Bonding Map of Type N on [0,1]

Let I = [0, 1], c ₁, c ₂ ∈ (0, 1) with c ₁ < c ₂ and f : I⊸I be a continuous map satisfying: are both strictly increasing and is strictly decreasing. Let A = {x ∈ [0, c ₁]∣f(x) = x}, a=max A, a ₁ =max(A\{a}), and B = {x ∈ [c ₂, 1]∣f(x) = x}, b=minB, b ₁ =min(B\{b}). Then the inverse limit (I, f) is an arc if and only if one of the following three conditions holds: (1) If c ₁ < f (c ₁) ≤ c ₂ (resp. c ₁ ≤ f (c ₂) < c ₂), then f has a single fixed point, a period two orbit, but no points of period greater than two or f has more than one fixed point but no points of other periods, furthermore, if A≠φ and B≠φ, then f (c ₂) > a (resp. f (c ₁) < b). (2) If f (c ₁) ≤ c ₁ (resp. f (c ₂) ≥ c ₂), then f has more than one fixed point, furthermore, if B≠φ and A\ {a} ≠φ, f (c ₂) ≥ a or if a ₁ < f (c ₂) < a, f ² (c ₂) > f (c ₂), (resp. f has more than one fixed point, furthermore, if A≠φ and B\{b}≠φ, f (c ₁) ≤ b or if b < f (c ₂) < b ₁, f ² (c ₁) < f (c ₁)). (3) If f (c ₁) > c ₂ and f (c ₂) < c ₁, then f has a single fixed point, a single period two orbit lying in I\(u, v) but no points of period greater than two, where u, v ∈ [c ₁, c ₂] such that f (u) = c ₂ and f (v) = c ₁. Supported by the National Natural Science Foundation of China (No. 19961001, No. 60334020) and Outstanding Young Scientist Research Fund. (No. 60125310)     

Color Chain of a Graph

For a simple connected undirected graph G, c(G), c_f(G), Y_f(G), f(G), ?G(G){\chi(G), \chi_f(G), \Psi_f(G), \phi(G), \partial \Gamma (G)} and Ψ(G) denote respectively the chromatic number, fall chromatic number (assuming that it exists for G), fall achromatic number, b-chromatic number, partial Grundy number and achromatic number of G. It is shown in Dunbar et al. (J Combin Math & Combin Comput 33:257–273, 2000) that for any graph G for which fall coloring exists, c(G) ￡ c_f(G) ￡ Y_f (G) ￡ f(G) ￡ ?G(G) ￡ Y(G){\chi (G)\leq \chi_f(G) \leq \Psi_f (G) \leq \phi(G) \leq \partial \Gamma (G)\leq \Psi (G)} . In this paper, we exhibit an infinite family of graphs G with a strictly increasing color chain: c(G) < c_f(G) < Y_f (G) < f(G) < ?G(G) < Y(G){\chi (G) < \chi_f(G) < \Psi_f (G) < \phi(G) < \partial \Gamma (G) < \Psi (G)} . The existence of such a chain was raised by Dunbar et al.     

Decomposition of positive definite functions defined on a neighbourhood of the identity

LetV be a symmetric open neighbourhood of the identity of a topological groupG. We show that every positive definite functionf onV can be written asf=f _c +f _s wheref _c andf _s are positive definite functions onV, f _c is continuous andf _s averages to zero. IfG is locally compact with Haar measurem _G andf ism _G -measurable thenf _s =0m _G -almost everywhere.     

Hermite Interpolation and Sobolev Orthogonality

In this paper, we study orthogonal polynomials with respect to the bilinear form (f, g) _S = V(f) A V(g) ^T + <u, f ^(N) g ^(N)V(f) =(f(c ₀), f "(c ₀), ..., f ^{(n – 1)} ₀(c ₀), ..., f(c _p ), f "(c _p ), ..., f ^{(n – 1)} _p(c _p )) u is a regular linear functional on the linear space P of real polynomials, c ₀, c ₁, ..., c _p are distinct real numbers, n ₀, n ₁, ..., n _p are positive integer numbers, N=n ₀+n ₁+...+n _p , and A is a N × N real matrix with all its principal submatrices nonsingular. We establish relations with the theory of interpolation and approximation.     

On a conjecture by Plummer and Toft

The cyclic chromatic number χ_c(G) of a 2‐connected plane graph G is the minimum number of colors in an assigment of colors to the vertices of G such that, for every face‐bounding cycle f of G, the vertices of f have different colors. Plummer and Toft proved that, for a 3‐connected plane graph G, under the assumption Δ*(G) ≥ 42, where Δ*(G) is the size of a largest face of G, it holds that χ_c(G) ≤ Δ*(G) + 4. They conjectured that, if G is a 3‐connected plane graph, then χ_c>(G) ≤ Δ*(G) + 2. In the article the conjecture is proved for Δ*(G) ≥ 24. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 177–189, 1999     

Fourier type 2 operators with respect to locally compact abelian groups

A linear and bounded operator T between Banach spaces X and Y has Fourier type 2 with respect to a locally compact abelian group G if there exists a constant c > 0 such that∥T ∥₂ ≤ c∥f∥₂ holds for all X‐valued functions f ∈ L^X₂(G) where is the Fourier transform of f. We show that any Fourier type 2 operator with respect to the classical groups has Fourier type 2 with respect to any locally compact abelian group. This generalizes previous special results for the Cantor group and for closed subgroups of ?ⁿ. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Detecting and creating oscillations using multifractal methods

By comparing the Hausdorff multifractal spectrum with the large deviations spectrum of a given continuous function f, we find sufficient conditions ensuring that f possesses oscillating singularities. Using a similar approach, we study the nonlinear wavelet threshold operator which associates with any function f = ∑_j ∑_k d_j,k ψ _j,k ∈ L ²(?) the function series f^t whose wavelet coefficients are d ^t _j,k = d_j,k 1 , for some fixed real number γ > 0. This operator creates a context propitious to have oscillating singularities. As a consequence, we prove that the series f^t may have a multifractal spectrum with a support larger than the one of f . We exhibit an example of function f ∈ L ²(?) such that the associated thresholded function series f^t effectively possesses oscillating singularities which were not present in the initial function f . This series f^t is a typical example of function with homogeneous non‐concave multifractal spectrum and which does not satisfy the classical multifractal formalisms. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Super magic strength of a graph

By G(p, q) we denote a graph having p vertices and q edges, by V and E the vertex set and edge set of G respectively. A graph G(p, q) is said to have an edge magic labeling (valuation) with the constant (magic number) c(f) if there exists a one-to-one and onto function f: V ∪ E → {1, 2, …., p + q} such that f(u)+f(v)+f(uv) = c(f) for all uv ∈ E. An edge magic labeling f of G is called a super magic labeling if f(E) ={1, 2, …., q}. In this paper the concepts of the super magic and super magic strength of a graph are introduced. The super magic strength (sms) of a graph G is defined as the minimum of all constants c′(f) where the minimum is taken over all super magic labeling of G and is denoted by sms(G). This minimum is defined only if the graph has at least one such super magic labeling. In this paper, the super magic strength of some well known graphs P _2n , P _2n+1, K _1,n , B _n,n , < K _1,n : 2 >, P _n ² and (2 _{n + 1})P ₂, C _n and W _n are obtained, where P _n is a path on n vertices, K _1,n is a star graph on n+1 vertices, n-bistar B _n,n is the graph obtained from two copies of K _1,n by joining the centres of two copies of K _1,n by an edge e, if e is subdivided then B _n,n becomes < K _1,n : 2 >, (2 _{n + 1}) P ₂ is 2 _{n + 1} disjoint copies of P ₂, P _n ² is a square graph of P _n . C _n is a cycle on n vertices and W _n = C _n + K ₁ is wheel on n + 1 vertices.     

Estimates for the zeros of differences of meromorphic functions

Let f be a transcendental meromorphic function and g(z)=f(z+c1)+f(z+c2)-2f(z) and g2(z)=f(z+c1)·f(z+c2)-f2(z).The exponents of convergence of zeros of differences g(z),g2(z),g(z)/f(z),and g2(z)/f2(z) are estimated accurately.     

Identification of temperature‐dependent thermophysical properties in a partial differential equation subject to extra final measurement data

We consider an inverse problem for estimating the two coefficient functions c and k in a parabolic type partial differential equation c(u)u_t = ?[k(u)u_x]/?x with the aid of the measurements of u at two different times. The first‐ and second‐order one‐step group preserving schemes are developed. Solving the resultant algebraic equations with a closed‐form, we can estimate the unknown temperature‐dependent thermal conductivity and heat capacity. The new methods possess threefold advantages: they do not require any a priori information on the functional forms of thermal conductivity and heat capacity; no initial guesses are required; and no iterations are required. Numerical examples are examined to show that the new approaches have high accuracy and efficiency, even there are rare measured data. When the measured temperatures are polluted by uniform or normal random noise, the estimated results are also good. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

Roots of mappings on nonorientable surfaces¶and equations in free groups

Let f:M ₁→M ₂ be a continuous map and c:M ₁→M ₂ a constant map between closed (not necessarily orientable) surfaces. By definition the pair (f,c) has the Wecken property if f can be deformed into a map f' such that the number of coincidence points of (f',c) is the same as the number of essential coincidence classes of (f,c) and, hence, every essential coincidence class consists of exactly one point. When both surfaces are orientable the problem to determine all maps which have the Wecken property was solved in [14]. Let A(f) denote the absolute degree as defined in [6] or [15] and . Here we show that a map f has the Wecken property iff either the Euler characteristic or . In free groups there are solved certain quadratic equations closely related to the root problem. Received: Received: 18 January 2001 / Revised version: 27 November 2001     

Nonfree actions of countable groups and their characters

The paper studies the region of values of the system {c ₂, c ₃, f(z ₁), f′(z ₁)},where z ₁ is an arbitrary fixed point of the disk |z| < 1; f ∈ T,and the class T consists of all the functions f(z) = z + c ₂ z ² + c ₃z³ + ⋯ regular in the disk |z| < 1 that satisfy the condition Im z · Im f(z) > 0 for Im z ≠ 0. The region of values of f′(z ₁) in the subclass of functions f ∈ T with prescribed values c ₂, c ₃, and f(z ₁) is determined. Bibliography: 10 titles.     

A phase transition for avoiding a giant component

Let c be a constant and (e₁,f₁),(e₂,f₂),…,(e_cn,f_cn) be a sequence of ordered pairs of edges from the complete graph K_n chosen uniformly and independently at random. We prove that there exists a constant c₂ such that if c > c₂, then whp every graph which contains at least one edge from each ordered pair (e_i,f_i) has a component of size Ω(n), and, if c < c₂, then whp there is a graph containing at least one edge from each pair that has no component with more than O(n^1?? vertices, where ? is a constant that depends on c₂ ? c. The constant c₂ is roughly 0.97677. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Linear lower bounds for δc(p) for a class of 2D self‐destructive percolation models

The self‐destructive percolation model is defined as follows: Consider percolation with parameter p > p_c. Remove the infinite occupied cluster. Finally, give each vertex (or, for bond percolation, each edge) that at this stage is vacant, an extra chance δ to become occupied. Let δ_c(p) be the minimal value of δ, needed to obtain an infinite occupied cluster in the final configuration. This model was introduced by van den Berg and Brouwer. They showed, for the site model on the square lattice (and a few other 2D lattices satisfying a special technical condition) that δ_c(p) ≥ . In particular, δ_c(p) is at least linear in p ? p_c. Although the arguments used by van den Berg and Brouwer look very lattice‐specific, we show that they can be suitably modified to obtain similar linear lower bounds for δ_c(p) (with p near p_c) for a much larger class of 2D lattices, including bond percolation on the square and triangular lattices, and site percolation on the star lattice (or matching lattice) of the square lattice. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009