Optimal Reconstruction Might be Hard

Given as input a point set $\mathcal S $ that samples a shape $\mathcal A $ , the condition required for inferring Betti numbers of $\mathcal A $ from $\mathcal S $ in polynomial time is much weaker than the conditions required by any known polynomial time algorithm for producing a topologically correct approximation of $\mathcal A $ from $\mathcal S $ . Under the former condition which we call the weak precondition, we investigate the question whether a polynomial time algorithm for reconstruction exists. As a first step, we provide an algorithm which outputs an approximation of the shape with the correct Betti numbers under a slightly stronger condition than the weak precondition. Unfortunately, even though our algorithm terminates, its time complexity is unbounded. We then identify at the heart of our algorithm a test which requires answering the following question: given 2 two-dimensional simplicial complexes $L \subset K$ , does there exist a simplicial complex containing $L$ and contained in $K$ which realizes the persistent homology of $L$ into $K$ ? We call this problem the homological simplification of the pair $(K,L)$ and prove that this problem is NP-complete, using a reduction from 3SAT.     

Thresholded covering algorithms for robust and max–min optimization

In a two-stage robust covering problem, one of several possible scenarios will appear tomorrow and require to be covered, but costs are higher tomorrow than today. What should you anticipatorily buy today, so that the worst-case cost (summed over both days) is minimized? We consider the \(k\) -robust model where the possible scenarios tomorrow are given by all demand-subsets of size \(k\) . In this paper, we give the following simple and intuitive template for \(k\) -robust covering problems: having built some anticipatory solution, if there exists a single demand whose augmentation cost is larger than some threshold, augment the anticipatory solution to cover this demand as well, and repeat. We show that this template gives good approximation algorithms for \(k\) -robust versions of many standard covering problems: set cover, Steiner tree, Steiner forest, minimum-cut and multicut. Our \(k\) -robust approximation ratios nearly match the best bounds known for their deterministic counterparts. The main technical contribution lies in proving certain net-type properties for these covering problems, which are based on dual-rounding and primal–dual ideas; these properties might be of some independent interest. As a by-product of our techniques, we also get algorithms for max–min problems of the form: “given a covering problem instance, which \(k\) of the elements are costliest to cover?” For the problems mentioned above, we show that their \(k\) -max–min versions have performance guarantees similar to those for the \(k\) -robust problems.     

The elliptic functions and integrals of the “{1 \mathord{\left/ {\vphantom {1 9}} \right. \kern-\nulldelimiterspace} 9}” problem

We describe the functions needed in the determination of the rate of convergence of best $L^\infty $ rational approximation to $\exp ( - x)$ on [0,∞) when the degree n of the approximation tends to ∞ (“1/9” problem).     

On some extremal problems of approximation theory of functions on the real axis I

A number of extremal problems of approximation theory of functions have been solved on the real line $ \mathbb{R} $ . Exact constants in the Jackson-type inequalities in the space L ₂( $ \mathbb{R} $ ) are calculated. The exact values of average ν-widths are obtained for the classes of functions from L ₂( $ \mathbb{R} $ ) defined by averaged moduli of continuity of the k-th order, as well as for the classes of functions defined by K-functionals. The quite complete analysis of the final results related to the solution of extremal problems of approximation theory in the periodic case and for the whole real axis is carried out in the chronological order.     

Linear deviations of the classes\tilde W_p^\alpha and approximations in spaces of multipliers

We consider the problem of the asymptotically best linear method of approximation in the metric of L_s[?π, π] of the set \(\tilde W_p^\alpha (1)\) of periodic functions with a bounded in L_p[?π, π] fractional derivative, by functions from \(\tilde W_p^\beta (M)\) ,β >α, for sufficiently large M, and the problem about the best approximation in L_s[?π, π] of the operator of differentiation on \(\tilde W_p^\alpha (1)\) by continuous linear operators whose norm (as operators from L_r[?π, π] into L_q[?π, π])does not exceed M. These problems are reduced to the approximation of an individual element in the space of multipliers, and this allows us to obtain estimates that are exact in the sense of the order.     

On some extremal problems of approximation theory of functions on the real axis II

The work is devoted to the solution of a number of extremal problems of approximation theory of functions on the real axis $ \mathbb{R} $ . In the space L ₂( $ \mathbb{R} $ ), the exact constants in Jackson-type inequalities are calculated. The exact values of average ν-widths are obtained for the classes of functions from L ₂( $ \mathbb{R} $ ) that are defined by averaged k-order moduli of continuity and for the classes of functions defined by K-functionals. In the chronological order, the sufficiently complete analysis of the final results related to the solution of extremal problems of approximation theory in the periodic case and on the whole real axis is carried out.     

Democracy functions and optimal embeddings for approximation spaces

We prove optimal embeddings for nonlinear approximation spaces $\mathcal{A}^{\alpha}_q$ , in terms of weighted Lorentz sequence spaces, with the weights depending on the democracy functions of the basis. As applications we recover known embeddings for N-term wavelet approximation in L ^p , Orlicz, and Lorentz norms. We also study the ??greedy classes?? ${\mathcal{G}_{q}^{\alpha}}$ introduced by Gribonval and Nielsen, obtaining new counterexamples which show that ${\mathcal{G}_{q}^{\alpha}}\not=\mathcal{A}^{\alpha}_q$ for most non-democratic unconditional bases.     

Numerical approximation to the fractional derivative operator

In this paper we consider the numerical approximation of \(A^{\alpha }\) by contour integral. We are mainly interested to the case of \(A\) representing the discretization of the first derivative by means of a backward differentiation formula, and \( 0\!<\!\alpha \!<\!1\) . The computation of the contour integral yields a rational approximation to \(A^{\alpha }\) which can be used to define \(k\) -step formulas for the numerical integration of Fractional Differential Equations.     

A covering lemma for {K(\mathbb {R})}

The Dodd–Jensen Covering Lemma states that “if there is no inner model with a measurable cardinal, then for any uncountable set of ordinals X, there is a ${Y\in K}$ such that ${X\subseteq Y}$ and |X| = |Y|”. Assuming ZF+AD alone, we establish the following analog: If there is no inner model with an ${\mathbb {R}}$ –complete measurable cardinal, then the real core model ${K(\mathbb {R})}$ is a “very good approximation” to the universe of sets V; that is, ${K(\mathbb {R})}$ and V have exactly the same sets of reals and for any set of ordinals X with ${|{X}|\ge\Theta}$ , there is a ${Y\in K(\mathbb {R})}$ such that ${X\subseteq Y}$ and |X| = |Y|. Here ${\mathbb {R}}$ is the set of reals and ${\Theta}$ is the supremum of the ordinals which are the surjective image of ${\mathbb {R}}$ .     

Quadratic polynomials represented by norm forms

Let ${P(t) \in \mathbb{Q}[t]}$ be an irreducible quadratic polynomial and suppose that K is a quartic extension of ${\mathbb{Q}}$ containing the roots of P(t). Let ${{\bf N}_{K/\mathbb{Q}}({\rm x})}$ be a full norm form for the extension ${K/\mathbb{Q}}$ . We show that the variety $$\begin{array}{ll}P(t)={\bf N}_{K/\mathbb{Q}}({\rm x})\neq 0\end{array}$$ satisfies the Hasse principle and weak approximation. The proof uses analytic methods.     

C∞ functions in infinite dimension and linear partial differential difference equations with constant coefficients

This work is closed to [2] where a dense linear subspace \(\mathbb{E}\) (E) of the space ?(E) of the Silva C ^∞ functions on E is defined; the dual of \(\mathbb{E}\) (E) is described via the Fourier transform by a Paley-Wiener-Schwartz theorem which is formulated exactly in the same way as in the finite dimensional case. Here we prove existence and approximation result for solutions of linear partial differential difference equations in \(\mathbb{E}\) (E) with constant coefficients. We also obtain a Hahn-Banach type extension theorem for some C^∞ functions defined on a closed subspace of a DFN space, which is analogous to a Boland’s result in the holomorphic case [1].     

Homogenization of an Elliptic System as the Cells of Periodicity are Refined in One Direction

We homogenize a second-order elliptic system with anisotropic fractal structure characteristic of many real objects: the cells of periodicity are refined in one direction. This problem is considered in the rectangle with Dirichlet conditions given on two sides and periodicity conditions on two other sides. An explicit formula for the homogenized operator is established, and an asymptotic estimate of the remainder is obtained. The accuracy of approximation depends on the exponent $\kappa$ ∈ (0, 1/2] of smoothness of the right-hand side with respect to slow variables (the Sobolev-Slobodetskii space) and is estimated by $O(h^\kappa )$ for $\kappa$ ∈ (0, 1/2) and by O(h ^1/2(1 + |log h|)) for $\kappa$ = 1/2.     

New stochastic approximation algorithms with adaptive step sizes

This paper considers the stochastic approximation problem in which the gradient of the function is disturbed by noise. In other words, at each point x _k , instead of the exact gradient g _k , only noisy measurement ${\tilde g_k=g_k+\xi_k}$ is available, where ?? _k denotes the noise. To accelerate the classical Robbins?CMonro algorithm, Kesten (Ann Math Stat 29:41?C59, 1958) and Delyon and Juditsky (SIAM J Optim 3:868?C881, 1993) considered the use of the quantity s _k that stands for the number of changes of the sign of ${\tilde{g}_k^{T}\tilde{g}_{k-1}}$ . Assuming the presence of state independent noise, we discuss in this paper the properties of the quantity ${\frac{s_k}{k}}$ that stands for the change frequency of the sign of ${\tilde{g}_{k}^{T}\tilde{g}_{k-1}}$ and design new stochastic approximation algorithms based on the quantity ${\frac{s_k}k}$ . The almost sure convergence of the new algorithms are also established. The numerical results show that the algorithms are promising.     

Multilevel correction for collocation solutions of Volterra integral equations with proportional delays

In this paper, we propose a convergence acceleration method for collocation solutions of the linear second-kind Volterra integral equations with proportional delay qt $(0<q<1)$ . This convergence acceleration method called multilevel correction method is based on a kind of hybrid mesh, which can be viewed as a combination between the geometric meshes and the uniform meshes. It will be shown that, when the collocation solutions are continuous piecewise polynomials whose degrees are less than or equal to ${m} (m \leqslant 2)$ , the global accuracy of k level corrected approximation is $O(N^{-(2m(k+1)-\varepsilon)})$ , where N is the number of the nodes, and $\varepsilon$ is an arbitrary small positive number.     

Approximating minimum-cost edge-covers of crossing biset-families

Part of this paper appeared in the preliminary version [16]. An ordered pair ? = (S, S ₊) of subsets of a groundset V is called a biset if S ? S+; (V S ⁺;V S) is the co-biset of ?. Two bisets \(\hat X,\hat Y\) intersect if ^X X ∩ Y ≠ \(\not 0\) and cross if both X ∩ Y \(\not 0\) and X ⁺ ∪ Y ⁺ ≠= V. The intersection and the union of two bisets \(\hat X,\hat Y\) are defined by \(\hat X \cap \hat Y = (X \cap Y,X^ + \cap Y^ + )\) and \(\hat X \cup \hat Y = (X \cup Y,X^ + \cup Y^ + )\) . A biset-family \(\mathcal{F}\) is crossing (intersecting) if \(\hat X \cap \hat Y,\hat X \cup \hat Y \in \mathcal{F}\) for any \(\hat X,\hat Y \in \mathcal{F}\) that cross (intersect). A directed edge covers a biset ? if it goes from S to V S ⁺. We consider the problem of covering a crossing biset-family \(\mathcal{F}\) by a minimum-cost set of directed edges. While for intersecting \(\mathcal{F}\) , a standard primal-dual algorithm computes an optimal solution, the approximability of the case of crossing \(\mathcal{F}\) is not yet understood, as it includes several NP-hard problems, for which a poly-logarithmic approximation was discovered only recently or is not known. Let us say that a biset-family \(\mathcal{F}\) is k-regular if \(\hat X \cap \hat Y,\hat X \cup \hat Y \in \mathcal{F}\) for any \(\hat X,\hat Y \in \mathcal{F}\) with |V (X∪Y)≥k+1 that intersect. In this paper we obtain an O(log |V|)-approximation algorithm for arbitrary crossing \(\mathcal{F}\) if in addition both \(\mathcal{F}\) and the family of co-bisets of \(\mathcal{F}\) are k-regular, our ratios are: \(O\left( {\log \frac{{|V|}} {{|V| - k}}} \right) \) if |S ⁺ \ S| = k for all \(\hat S \in \mathcal{F}\) , and \(O\left( {\frac{{|V|}} {{|V| - k}}\log \frac{{|V|}} {{|V| - k}}} \right) \) if |S ⁺ \ S| = k for all \(\hat S \in \mathcal{F}\) . Using these generic algorithms, we derive for some network design problems the following approximation ratios: \(O\left( {\log k \cdot \log \tfrac{n} {{n - k}}} \right) \) for k-Connected Subgraph, and O(logk) \(\min \{ \tfrac{n} {{n - k}}\log \tfrac{n} {{n - k}},\log k\} \) for Subset k-Connected Subgraph when all edges with positive cost have their endnodes in the subset.     

The K-moment problem with densities

Given a compact basic semi-algebraic set ${\mathbf{K}} \subset {\mathbb{R}}^n$ , a rational fraction $f:{\mathbb{R}}^n\to{\mathbb{R}}$ , and a sequence of scalars y = (y _α), we investigate when $y_\alpha =\int_{\mathbf{K}} x^\alpha f\,d\mu$ holds for all $\alpha\in{\mathbb{N}}^n$ , i.e., when y is the moment sequence of some measure fdμ, supported on K. This yields a set of (convex) linear matrix inequalities (LMI). We also use semidefinite programming to develop a converging approximation scheme to evaluate the integral ∫ fdμ when the moments of μ are known and f is a given rational fraction. Numerical expreriments are also provided. We finally provide (again LMI) conditions on the moments of two measures $\nu,\mu$ with support contained in K, to have $d\nu=f d\mu$ for some rational fraction f.     

Optimal Set of the Modulus of Continuity in the Sharp Jackson Inequality in the Space $$L_2 $$

To a function $f \in L_2 [ - \pi ,\pi ]$ and a compact set $Q \subset [ - \pi ,\pi ]$ we assign the supremum $\omega (f,Q) = \sup _{t \in Q} ||f( \cdot + t) - f( \cdot )||_{L_2 [ - \pi ,\pi ]} $ , which is an analog of the modulus of continuity. We denote by $K(n,Q)$ the least constant in Jackson's inequality between the best approximation of the function f by trigonometric polynomials of degree $n - 1$ in the space $L_2 [ - \pi ,\pi ]$ and the modulus of continuity $\omega (f,Q)$ . It follows from results due to Chernykh that $K(n,Q) \geqslant 1/\sqrt 2 $ and $K(n,[0,\pi /\pi ]) = 1/\sqrt 2 $ . On the strength of a result of Yudin, we show that if the measure of the set Q is less than $\pi /n$ , then $K(n,Q) >1/\sqrt 2 $ .     

An extension of Mercer’s theory to L p

Let X be a topological space, either locally compact or first countable, endowed with a strictly positive measure ?? and ${\mathcal{K}:L^2(X,\nu)\to L^2(X,\nu)}$ an integral operator generated by a Mercer like kernel K. In this paper we extend Mercer??s theory for K and ${\mathcal{K}}$ under the assumption that the function ${x\in X\to K(x,x)}$ belongs to some L ^p/2(X, ??), p??? 1. In particular, we obtain series representations for K and some powers of ${\mathcal{K}}$ , with convergence in the p-mean, and show that the range of certain powers of ${\mathcal{K}}$ contains continuous functions only. These results are used to estimate the approximation numbers of a modified version of ${\mathcal{K}}$ acting on L ^p (X, ??).     

On generalizing transitivity, persistence, and sensitivity

A subgroup property $\alpha $ is transitive in a group $G$ if $U \alpha V$ and $V \alpha G$ imply that $U \alpha G$ whenever $U \le V \le G$ , and $\alpha $ is persistent in $G$ if $U \alpha G$ implies that $U \alpha V$ whenever $U \le V \le G$ . Even though a subgroup property $\alpha $ may be neither transitive nor persistent, a given subgroup $U$ may have the property that each $\alpha $ -subgroup of $U$ is an $\alpha $ -subgroup of $G$ , or that each $\alpha $ -subgroup of $G$ in $U$ is an $\alpha $ -subgroup of $U$ . We call these subgroup properties $\alpha $ -transitivity and $\alpha $ -persistence, respectively. We introduce and develop the notions of $\alpha $ -transitivity and $\alpha $ -persistence, and we establish how the former property is related to $\alpha $ -sensitivity. In order to demonstrate how these concepts can be used, we apply the results to the cases in which $\alpha $ is replaced with “normal” and the “cover-avoidance property.” We also suggest ways in which the theory can be developed further.     

Best L 1 Approximation of Truncated Functions,Whitney-Type and Borh–Favard-Type Inequalities

We present upper and lower estimates for the best constant C _n such that, if \({f \in W^{n+1}_1}\) [?1, 1], then $$E_n(f)_1 \leqq C_n||\varphi^{n+1}f^{(n+1)}||_1,$$ where \({\varphi(x) =\sqrt{1 - x^2}}\) . For the proof we first find out the polynomials of the best L ¹[?1, 1] approximation of some truncated functions.