Search

We describe a subdivision algorithm for isolating the complex roots of a polynomial F ∈ C [ x ] . Given an oracle that provides approximations of each of the coefficients of F to any absolute error bound and given an arbitrary square B in the complex plane containing only simple roots of F , our algorithm returns disjoint isolating disks for the roots of F in B . Our complexity analysis bounds the absolute error to which the coefficients of F have to be provided, the total number of iterations, and the overall bit complexity. It further shows that the complexity of our algorithm is controlled by the geometry of the roots in a near neighborhood of the input square B , namely, the number of roots, their absolute values and pairwise distances. The number of subdivision steps is near-optimal. For the benchmark problem , namely, to isolate all the roots of a polynomial of degree n with integer coefficients of bit size less than τ , our algorithm needs O ˜ ( n 3 + n 2 τ ) bit operations, which is comparable to the record bound of Pan (2002) . It is the first time that such a bound has been achieved using subdivision methods, and independent of divide-and-conquer techniques such as Schönhage's splitting circle technique. Our algorithm uses the quadtree construction of Weyl (1924) with two key ingredients: using Pellet's Theorem (1881) combined with Graeffe iteration, we derive a “soft-test” to count the number of roots in a disk. Using Schröder's modified Newton operator combined with bisection, in a form inspired by the quadratic interval method from Abbot (2006), we achieve quadratic convergence towards root clusters. Relative to the divide-conquer algorithms, our algorithm is quite simple with the potential of being practical. This paper is self-contained: we provide pseudo-code for all subroutines used by our algorithm. [ABSTRACT FROM AUTHOR]

In this paper we introduce a general framework that exponentially improves the space, degree of independence, and time needed by min-wise-based algorithms. The authors, in SODA '11 [1] , introduced an exponential time improvement for min-wise-based algorithms. Here we develop an alternative approach that achieves both exponential time and exponential space improvement. The new approach relaxes the need for approximately min-wise hash functions, hence getting around the Ω ( log ⁡ 1 ϵ ) independence lower bound, by defining and constructing a d-k-min-wise independent family of hash functions; surprisingly, for most cases, only 8-wise independence is needed for the additional improvement. Furthermore, we discuss how this construction can be used to improve many min-wise-based algorithms. To our knowledge such definitions, for hash functions, were never previously studied or constructed. Finally, we show how to apply it for similarity and rarity estimation over data streams; other min-wise-based algorithms can be adjusted in the same way. [ABSTRACT FROM AUTHOR]

In this paper we establish an algorithmic framework between bin packing and strip packing, with which strip packing can be very well approximated by applying some bin packing algorithms. More precisely we obtain the following results: (1) Any off-line bin packing algorithm can be applied to strip packing maintaining almost the same asymptotic worst-case ratio. (2) A class of Harmonic-based algorithms for bin packing, such as Refined Harmonic, Modified Harmonic, Harmonic++, can be applied to online strip packing. In particular, we show that online strip packing admits an upper bound of 1.58889 + ϵ on the asymptotic competitive ratio, for any arbitrarily small ϵ > 0 . This significantly improves the previously best bound of 1.6910 and affirmatively answers an open question posed by Csirik and Woeginger (1997). Moreover, the time complexity mainly depends on a sorting procedure and the bin packing algorithms employed. [ABSTRACT FROM AUTHOR]

Abstract: Trigonometric non-Fourier moment problems arise as a result of various control problem study. In current paper, the extremal solution, i.e. the one with the least -norm is searched for. Proposed is an algorithm that allows to change an infinite system of equations into the linear one with only a finite number of equations. The mentioned algorithm is based on the fact, that in the case of a Fourier moment problem, the extremal solution is periodic and easy to construct. The extremal solution of a non-Fourier moment problem close to a Fourier one is approximated by a sequence of solutions with periodicity disturbed in a finite number of equations. It is proved that this sequence of approximations converges to the desired extremal solution. The paper is concluded with the particular example whose consideration leads to a moment problem elaborated in the first part of the article. [Copyright &y& Elsevier]

Abstract: This is a follow-up paper of “Liberating the dimension for function approximation”, where we studied approximation of infinitely variate functions by algorithms that use linear information consisting of finitely many linear functionals. In this paper, we study similar approximation problems, however, now the algorithms can only use standard information consisting of finitely many function values. We assume that the cost of one function value depends on the number of active variables. We focus on polynomial tractability, and occasionally also study weak tractability. We present non-constructive and constructive results. Non-constructive results are based on known relations between linear and standard information for finitely variate functions, whereas constructive results are based on Smolyak’s construction generalized to the case of infinitely variate functions. Surprisingly, for many cases, the results for standard information are roughly the same as for linear information. [Copyright &y& Elsevier]

Abstract: Recovering missing data from its partial samples is a fundamental problem in mathematics and it has wide range of applications in image and signal processing. While many such algorithms have been developed recently, there are very few papers available on their error estimations. This paper is to analyze the error of a frame based data recovery approach from random samples. In particular, we estimate the error between the underlying original data and the approximate solution that interpolates (or approximates with an error bound depending on the noise level) the given data that has the minimal norm of the canonical frame coefficients among all the possible solutions. [Copyright &y& Elsevier]

Abstract: This paper describes a statistically motivated framework for performing real-time dialogue state updates and policy learning in a spoken dialogue system. The framework is based on the partially observable Markov decision process (POMDP), which provides a well-founded, statistical model of spoken dialogue management. However, exact belief state updates in a POMDP model are computationally intractable so approximate methods must be used. This paper presents a tractable method based on the loopy belief propagation algorithm. Various simplifications are made, which improve the efficiency significantly compared to the original algorithm as well as compared to other POMDP-based dialogue state updating approaches. A second contribution of this paper is a method for learning in spoken dialogue systems which uses a component-based policy with the episodic Natural Actor Critic algorithm. The framework proposed in this paper was tested on both simulations and in a user trial. Both indicated that using Bayesian updates of the dialogue state significantly outperforms traditional definitions of the dialogue state. Policy learning worked effectively and the learned policy outperformed all others on simulations. In user trials the learned policy was also competitive, although its optimality was less conclusive. Overall, the Bayesian update of dialogue state framework was shown to be a feasible and effective approach to building real-world POMDP-based dialogue systems. [Copyright &y& Elsevier]

Abstract: In this paper, we focus on the edit distance between two given strings where block-edit operations are allowed and better fitting to the human natural edit behaviors. Previous results showed that this problem is NP-hard when block moves are allowed. Various approximations to this problem have been proposed in recent years. However, this problem can be solved by the polynomial-time optimization algorithms if some reasonable restrictions are applied. The restricted variations which we consider involve character insertions, character deletions, block copies and block deletions. In this paper, three problems are defined with different measuring functions, which are , and . Then we show that with some preprocessing, the minimum block edit distances of these three problems can be obtained by dynamic programming in , and time, respectively, where n and m are the lengths of the two input strings. [Copyright &y& Elsevier]

Abstract: The cyclic projections algorithm is an important method for determining a point in the intersection of a finite number of closed convex sets in a Hilbert space. That is, for determining a solution to the “convex feasibility” problem. This is the third paper in a series on a study of the rate of convergence for the cyclic projections algorithm. In the first of these papers, we showed that the rate could be described in terms of the “angles” between the convex sets involved. In the second, we showed that these angles often had a more tractable formulation in terms of the “norm” of the product of the (nonlinear) metric projections onto related convex sets. In this paper, we show that the rate of convergence of the cyclic projections algorithm is also intimately related to the “linear regularity property” of Bauschke and Borwein, the “normal property” of Jameson (as well as Bakan, Deutsch, and Li’s generalization of Jameson’s normal property), the “strong conical hull intersection property” of Deutsch, Li, and Ward, and the rate of convergence of iterated parallel projections. Such properties have already been shown to be important in various other contexts as well. [Copyright &y& Elsevier]

Abstract: In a previous paper, the author introduced a class of multivariate rational interpolants, which are called optimal Padé-type approximants (OPTA). The main goal of this paper is to extend classical results on convergence both in measure and in capacity of sequences of Padé approximants to the multivariate case using OPTA. To this end, we obtain some estimations of the size of multivariate polynomial lemniscates in terms of the Hausdorff content, which we also think are of some interest. [Copyright &y& Elsevier]

This paper considers a modification of a PAC learning theory problem in which each instance of the training data is supplemented with side information. In this case, a transformation, given by a side-information map, of the training instance is also classified. However, the learning algorithm needs only to classify a new instance, not the instance and its value under the side information map. Side information can improve general learning rates, but not always. This paper shows that side information leads to the improvement of standard PAC learning theory rate bounds, under restrictions on the probable overlap between concepts and their images under the side information map. [Copyright &y& Elsevier]

Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of data reduction rules and combinatorial insights. We will expose in this paper a similar strategy for obtaining polynomial-time approximation algorithms. Our method features the use of approximation-preserving reductions, akin to the notion of parameterized reductions. We exemplify this method to obtain the currently best approximation algorithms for Harmless Set , Differential and Multiple Nonblocker , all of them can be considered in the context of securing networks or information propagation. [ABSTRACT FROM AUTHOR]

Computing the roots of a univariate polynomial is a fundamental and long-studied problem of computational algebra with applications in mathematics, engineering, computer science, and the natural sciences. For isolating as well as for approximating all complex roots, the best algorithm known is based on an almost optimal method for approximate polynomial factorization, introduced by Pan in 2002. Pan's factorization algorithm goes back to the splitting circle method from Schönhage in 1982. The main drawbacks of Pan's method are that it is quite involved 2 2 In Victor Pan's own words: “Our algorithms are quite involved, and their implementation would require a non-trivial work, incorporating numerous known implementation techniques and tricks”. In fact, we are not aware of any implementation of Pan's method. and that all roots have to be computed at the same time. For the important special case, where only the real roots have to be computed, much simpler methods are used in practice; however, they considerably lag behind Pan's method with respect to complexity. In this paper, we resolve this discrepancy by introducing a hybrid of the Descartes method and Newton iteration, denoted A New Dsc , which is simpler than Pan's method, but achieves a run-time comparable to it. Our algorithm computes isolating intervals for the real roots of any real square-free polynomial, given by an oracle that provides arbitrary good approximations of the polynomial's coefficients. A New Dsc can also be used to only isolate the roots in a given interval and to refine the isolating intervals to an arbitrary small size; it achieves near optimal complexity for the latter task. [ABSTRACT FROM AUTHOR]

In this paper, we present algorithms for the approximation of multivariate periodic functions by trigonometric polynomials. The approximation is based on sampling of multivariate functions on rank-1 lattices. To this end, we study the approximation of periodic functions of a certain smoothness. Our considerations include functions from periodic Sobolev spaces of generalized mixed smoothness. Recently an algorithm for the trigonometric interpolation on generalized sparse grids for this class of functions was investigated by Griebel and Hamaekers (2014). The main advantage of our method is that the algorithm is based mainly on a single one-dimensional fast Fourier transform, and that the arithmetic complexity of the algorithm depends only on the cardinality of the support of the trigonometric polynomial in the frequency domain. Therefore, we investigate trigonometric polynomials with frequencies supported on hyperbolic crosses and energy norm based hyperbolic crosses in more detail. Furthermore, we present an algorithm for sampling multivariate functions on perturbed rank-1 lattices and show the numerical stability of the suggested method. Numerical results are presented up to dimension d = 10 , which confirm the theoretical findings. [ABSTRACT FROM AUTHOR]

The Douglas-Rachford splitting algorithm is a classical optimization method that has found many applications. When specialized to two normal cone operators, it yields an algorithm for finding a point in the intersection of two convex sets. This method for solving feasibility problems has attracted a lot of attention due to its good performance even in nonconvex settings. In this paper, we consider the Douglas-Rachford algorithm for finding a point in the intersection of two subspaces. We prove that the method converges strongly to the projection of the starting point onto the intersection. Moreover, if the sum of the two subspaces is closed, then the convergence is linear with the rate being the cosine of the Friedrichs angle between the subspaces. Our results improve upon existing results in three ways: First, we identify the location of the limit and thus reveal the method as a best approximation algorithm; second, we quantify the rate of convergence, and third, we carry out our analysis in general (possibly infinite-dimensional) Hilbert space. We also provide various examples as well as a comparison with the classical method of alternating projections. [ABSTRACT FROM AUTHOR]

Abstract: Recently, a fast alternating minimization algorithm for total variation image deblurring (FTVd) has been presented by Wang, Yang, Yin, and Zhang (2008) [32]. The method in a nutshell consists of a discrete Fourier transform-based alternating minimization algorithm with periodic boundary conditions and in which two fast Fourier transforms (FFTs) are required per iteration. In this paper, we propose an alternating minimization algorithm for the continuous version of the total variation image deblurring problem. We establish convergence of the proposed continuous alternating minimization algorithm. The continuous setting is very useful to have a unifying representation of the algorithm, independently of the discrete approximation of the deconvolution problem, in particular concerning the strategies for dealing with boundary artifacts. Indeed, an accurate restoration of blurred and noisy images requires a proper treatment of the boundary. A discrete version of our continuous alternating minimization algorithm is obtained following two different strategies: the imposition of appropriate boundary conditions and the enlargement of the domain. The first one is computationally useful in the case of a symmetric blur, while the second one can be efficiently applied for a nonsymmetric blur. Numerical tests show that our algorithm generates higher quality images in comparable running times with respect to the Fast Total Variation deconvolution algorithm. [Copyright &y& Elsevier]

Abstract: This article considers recovery of signals that are sparse or approximately sparse in terms of a (possibly) highly overcomplete and coherent tight frame from undersampled data corrupted with additive noise. We show that the properly constrained -analysis optimization problem, called analysis Dantzig selector, stably recovers a signal which is nearly sparse in terms of a tight frame provided that the measurement matrix satisfies a restricted isometry property adapted to the tight frame. As a special case, we consider the Gaussian noise. Further, under a sparsity scenario, with high probability, the recovery error from noisy data is within a log-like factor of the minimax risk over the class of vectors which are at most s sparse in terms of the tight frame. Similar results for the analysis LASSO are shown. The above two algorithms provide guarantees only for noise that is bounded or bounded with high probability (for example, Gaussian noise). However, when the underlying measurements are corrupted by sparse noise, these algorithms perform suboptimally. We propose new algorithms for reconstructing signals that are nearly sparse in terms of a tight frame in the presence of bounded noise combined with sparse noise, and present corresponding recovery guarantees. The analysis in this paper is based on the restricted isometry property adapted to a tight frame, which is a natural extension to the standard restricted isometry property. [Copyright &y& Elsevier]

Abstract: In this paper, we present an algebraic perspective of the de Rham transform of a binary subdivision scheme and propose an elegant strategy for constructing dual -ary approximating subdivision schemes of de Rham-type, starting from two primal schemes of arity and 2, respectively. On the one hand, this new strategy allows us to show that several existing dual corner-cutting subdivision schemes fit into a unified framework. On the other hand, the proposed strategy provides a straightforward algorithm for constructing new dual subdivision schemes having higher smoothness and higher polynomial reproduction capabilities with respect to the two given primal schemes. [Copyright &y& Elsevier]

Abstract: In this paper, an algorithm is given for determining the topology of an algebraic space curve and to compute a certified rational parametric approximation of the algebraic space curve. The algorithm works by extending to dimension one the local generic position method for solving zero-dimensional polynomial equation systems. Here, certified means that the approximation curve and the original curve have the same topology and their Hausdorff distance is smaller than a given precision. The main advantage of the algorithm, inherited from the local generic position method, is that the topology computation and approximation for a space curve are directly reduced to the same tasks for two plane curves. In particular, an error bound of the approximation space curve is deduced explicitly from the error bounds of the approximation plane curves. The complexity of the algorithm is also analyzed. Its effectivity is shown on some non-trivial examples. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate a non-iterative imaging algorithm based on the topological derivative in order to retrieve the shape of penetrable electromagnetic inclusions when their dielectric permittivity and/or magnetic permeability differ from those in the embedding (homogeneous) space. The main objective is the imaging of crack-like thin inclusions, but the algorithm can be applied to arbitrarily shaped inclusions. For this purpose, we apply multiple time-harmonic frequencies and normalize the topological derivative imaging function by its maximum value. In order to verify its validity, we apply it for the imaging of two-dimensional crack-like thin electromagnetic inhomogeneities completely hidden in a homogeneous material. Corresponding numerical simulations with noisy data are performed for showing the efficacy of the proposed algorithm. [Copyright &y& Elsevier]

Abstract: In this paper we propose a variation of the soft-thresholding algorithm for finding sparse approximate solutions of the equation , where as the sparsity of the iterate increases the penalty function changes. In this approach, sufficiently large entries in a sparse iterate are left untouched. The advantage of this approach is that a higher regularization constant can be used, leading to a significant reduction of the total number of iterations. Numerical experiments for sparse recovery problems, also with noisy data, are included. [Copyright &y& Elsevier]

Abstract: The computation of approximate Gröbner bases is reported to be highly unstable in the literature. Selecting a suitable length of floats is helpful for stabilizing this computation. In this paper, we present a method to compute such a suitable length of floats. We concentrate on a family of polynomial systems sharing the same support and study the relation between the lengths of floats and the coefficients of relevant polynomials. Then we give a reference length of floats for all the polynomial systems in the family. One feature of our method is that it need not utilize numerical algorithms of Gröbner bases. Hence, our method can avoid the influence of the instabilities of the existing numerical algorithms and thus will be helpful for designing stable ones (e.g., stable Shirayanagiʼs algorithm). Experiments show that our method can work out reliable and reasonably large lengths of floats for most of the tested benchmarks. [Copyright &y& Elsevier]

Abstract: In this paper we present a technique for shape reconstruction based on the topological and shape gradients. The shape in consideration is a solution of an inverse conductivity problem. To solve such a problem numerically, we compute the topological gradient of a Kohn–Vogelius-type cost function when the domain under consideration is perturbed by the introduction of a small inclusion instead of a hole. The reconstruction is done by considering the shape as a superposition of very thin elliptic inclusions to get a first approximation. Then, we use a gradient-type algorithm to perform a good reconstruction. Various numerical experiments of single and multiple inclusions demonstrate the viability of the designed algorithm. [Copyright &y& Elsevier]

Abstract: Regularization schemes with an -regularizer often produce sparse representations for objects in approximation theory, image processing, statistics and learning theory. In this paper, we study a kernel-based learning algorithm for regression generated by regularization schemes associated with the -regularizer. We show that convergence rates of the learning algorithm can be independent of the dimension of the input space of the regression problem when the kernel is smooth enough. This confirms the effectiveness of the learning algorithm. Our error analysis is carried out by means of an approximation theory approach using a local polynomial reproduction formula and the norming set condition. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate -average sampling numbers of a periodic Sobolev space with a Gaussian measure in the metric for and , and obtain their asymptotic orders. Moreover, we show that in the average case setting, the operators , which are the Lagrange interpolating operators, are asymptotically optimal in the metric for all . It is interesting to note that in the worst case setting, are not asymptotically optimal algorithms in the metric for or . [Copyright &y& Elsevier]

Abstract: In this paper modified variants of the sparse Fourier transform algorithms from Iwen (2010) [32] are presented which improve on the approximation error bounds of the original algorithms. In addition, simple methods for extending the improved sparse Fourier transforms to higher dimensional settings are developed. As a consequence, approximate Fourier transforms are obtained which will identify a near-optimal k-term Fourier series for any given input function, , in time (neglecting logarithmic factors). Faster randomized Fourier algorithm variants with runtime complexities that scale linearly in the sparsity parameter k are also presented. [Copyright &y& Elsevier]

Abstract: In this paper the two-dimensional -fraction with independent variables which is the generalization of the continued -fraction is considered. The correspondence between the formal double power series and the above mentioned fraction is studied. As a result the algorithm for the expansion of the formal double power series into the corresponding two-dimensional -fraction with independent variables has been constructed and the conditions for the existence of such an algorithm have been established. The expansion of some functions into the corresponding two-dimensional -fraction with independent variables is constructed and the efficiency of the obtained expansion by using approximants is shown. [Copyright &y& Elsevier]

Abstract: Let be a separable polynomial over a local field. The Montes algorithm computes certain approximations to the different irreducible factors of , with strong arithmetic properties. In this paper, we develop an algorithm to improve any one of these approximations, till a prescribed precision is attained. The most natural application of this “single-factor lifting” routine is to combine it with the Montes algorithm to provide a fast polynomial factorization algorithm. Moreover, the single-factor lifting algorithm may be applied as well to accelerate the computational resolution of several global arithmetic problems in which the improvement of an approximation to a single local irreducible factor of a polynomial is required. [Copyright &y& Elsevier]

Abstract: The error function erf is a special function. It is widely used in statistical computations for instance, where it is also known as the standard normal cumulative probability. The complementary error function is defined as . In this paper, the computation of and in arbitrary precision is detailed: our algorithms take as input a target precision and deliver approximate values of or with a relative error guaranteed to be bounded by . We study three different algorithms for evaluating erf and erfc. These algorithms are completely detailed. In particular, the determination of the order of truncation, the analysis of roundoff errors and the way of choosing the working precision are presented. The scheme used for implementing erf and erfc and the proofs are expressed in a general setting, so they can directly be reused for the implementation of other functions. We have implemented the three algorithms and studied experimentally what is the best algorithm to use in function of the point x and the target precision . [Copyright &y& Elsevier]

Abstract: This paper introduces a fast algorithm for computing multilinear integrals which are defined through Fourier multipliers. The algorithm is based on generating a hierarchical decomposition of the summation domain into squares, constructing a low-rank approximation for the multiplier function within each square, and applying an FFT based fast convolution algorithm for the computation associated with each square. The resulting algorithm is accurate and has a linear complexity, up to logarithmic factors, with respect to the number of the unknowns in the input functions. Numerical results are presented to demonstrate the properties of this algorithm. [Copyright &y& Elsevier]

Abstract: This paper addresses the problem of scheduling non-preemptive moldable tasks to minimize the stretch of the tasks in an online non-clairvoyant setting. To the best of the authors’ knowledge, this problem has never been studied before. To tackle this problem, first the sequential subproblem is studied through the lens of the approximation theory. An algorithm, called DASEDF, is proposed and, through simulations, it is shown to outperform the first-come, first-served scheme. Furthermore, it is observed that machine availability is the key to getting good stretch values. Then, the moldable task scheduling problem is considered, and, by leveraging the results from the sequential case, another algorithm, DBOS, is proposed to optimize the stretch while scheduling moldable tasks. This work is motivated by a task scheduling problem in the context of parallel short sequence mapping which has important applications in biology and genetics. The proposed DBOS algorithm is evaluated both on synthetic data sets that represent short sequence mapping requests and on data sets generated using log files of real production clusters. The results show that the DBOS algorithm significantly outperforms the two state-of-the-art task scheduling algorithms on stretch optimization. [Copyright &y& Elsevier]

Abstract: Symbolic numeric algorithms for polynomials are very important, especially for practical computations since we have to operate with empirical polynomials having numerical errors on their coefficients. Recently, for those polynomials, a number of algorithms have been introduced, such as approximate univariate GCD and approximate multivariate factorization for example. However, for polynomials over integers having coefficients rounded from empirical data, changing their coefficients over reals does not remain them in the polynomial ring over integers; hence we need several approximate operations over integers. In this paper, we discuss computing a polynomial GCD of univariate or multivariate polynomials over integers approximately. Here, “approximately” means that we compute a polynomial GCD over integers by changing their coefficients slightly over integers so that the input polynomials still remain over integers. [Copyright &y& Elsevier]

Abstract: The aim of the paper is the construction and the analysis of nonlinear and non-separable multiscale representations for multivariate functions defined using a non-diagonal dilation matrix . We show that a function in or Besov spaces can be characterized by means of its multiscale representation. We also study the stability of these representations, a key issue to design adaptive algorithms. [Copyright &y& Elsevier]

Abstract: This paper shows that the FPTAS for the min–max disjoint paths problem on directed acyclic graphs by Yu et al. (2010) can be improved by a rounding and searching technique. [Copyright &y& Elsevier]

Abstract: In this paper, we present iteration schemes to weakly and strongly approximate common fixed points of a finite family of a class of strict pseudocontractions. [Copyright &y& Elsevier]

Abstract: In this paper we describe a method that can be used for Minimum Bayes Risk (MBR) decoding for speech recognition. Our algorithm can take as input either a single lattice, or multiple lattices for system combination. It has similar functionality to the widely used Consensus method, but has a clearer theoretical basis and appears to give better results both for MBR decoding and system combination. Many different approximations have been described to solve the MBR decoding problem, which is very difficult from an optimization point of view. Our proposed method solves the problem through a novel forward–backward recursion on the lattice, not requiring time markings. We prove that our algorithm iteratively improves a bound on the Bayes risk. [Copyright &y& Elsevier]

Abstract: This paper concerns systems with small coherence parameter. Simple greedy-type algorithms perform well on these systems, which are also useful in the construction of compressed sensing matrices. We discuss the following problems for both and . How large can a dictionary be, if we prescribe the coherence parameter? How small could the resulting coherence parameter be, if we impose a size on the dictionary? How could we construct such a system? Several fundamental results from different areas of mathematics shed light on these important problems with far-reaching implications in approximation theory. [Copyright &y& Elsevier]

Abstract: In this paper we describe how an idea centered on the concept of self-saturation allows several improvements in the computation of Gröbner bases via Buchberger’s Algorithm. In a nutshell, the idea is to extend the advantages of computing with homogeneous polynomials or vectors to the general case. When the input data are not homogeneous, we use as a main tool the procedure of a self-saturating Buchberger’s Algorithm. Another strictly related topic is treated later when a mathematical foundation is given to the sugar trick which is nowadays widely used in most of the implementations of Buchberger’s Algorithm. A special emphasis is also given to the case of a single grading, and subsequently some timings and indicators showing the practical merits of our approach. [Copyright &y& Elsevier]

Abstract: A classical measure of similarity between strings is the length of the longest common subsequence (LCS) between the two given strings. The search for efficient algorithms for finding the LCS has been going on for more than three decades. To date, all known algorithms may take quadratic time (shaved by logarithmic factors) to find large LCS. In this paper, the problem of approximating LCS is studied, while focusing on the hard inputs for this problem, namely, approximating LCS of near-linear size in strings over a relatively large alphabet (of size at least for some constant , where is the length of the string). We show that, any given string over a relatively large alphabet can be embedded into a locally non-repetitive string. This embedding has a negligible additive distortion for strings that are not too dissimilar in terms of the edit distance. We also show that LCS can be efficiently approximated in locally-non-repetitive strings. Our new method (the embedding together with the approximation algorithm) gives a strictly sub-quadratic time algorithm (i.e., of complexity for some constant ) which can find common subsequences of linear (and near linear) size that cannot be detected efficiently by the existing tools. [Copyright &y& Elsevier]

Abstract: In DeVore et al. (2011) we considered smooth functions on which depend on a much smaller number of variables or continuous functions which can be approximated by such functions. We were interested in approximating those functions when we can calculate point values at points of our choice. The number of points we needed for non-adaptive algorithms was higher than that in the adaptive case. In this paper we improve on DeVore et al. (2011) and show that in the non-adaptive case one can use the same number of points (up to a multiplicative constant depending on ) that we need in the adaptive case. [Copyright &y& Elsevier]

Abstract: This paper deals with absolute convergence of real-valued rational series, i.e. mappings computed by weighted automata. An algorithm is provided, that takes a weighted automaton as input and halts if and only if the corresponding series is absolutely convergent: hence, absolute convergence of rational series is semi-decidable. A spectral radius-like parameter is introduced, which satisfies the following property: a rational series is absolutely convergent iff . We show that if is rational, then can be approximated by convergent upper estimates. Then, it is shown that the sum can be estimated to any accuracy rate. This result can be extended to any sum of the form , for any integer . [Copyright &y& Elsevier]

Abstract: Much work has been devoted, during the past 20years, to using complexity to protect elections from manipulation and control. Many “complexity shield” results have been obtained—results showing that the attacker’s task can be made NP-hard. Recently there has been much focus on whether such worst-case hardness protections can be bypassed by frequently correct heuristics or by approximations. This paper takes a very different approach: We argue that when electorates follow the canonical political science model of societal preferences the complexity shield never existed in the first place. In particular, we show that for electorates having single-peaked preferences, many existing NP-hardness results on manipulation and control evaporate. [ABSTRACT FROM AUTHOR]

Abstract: Partial transition systems support abstract model checking of complex temporal properties by combining both over- and under-approximating abstractions into a single model. Over the years, three families of such modeling formalisms have emerged, represented by (1) Kripke Modal Transition Systems (KMTSs), with restrictions on necessary and possible behaviors; (2) Mixed Transition Systems (MixTSs), with relaxation on these restrictions; and (3) Generalized Kripke MTSs (GKMTSs), with hyper-transitions, respectively. In this paper, we investigate these formalisms based on two fundamental ways of using partial transition systems (PTSs) – as objects for abstracting concrete systems (and thus, a PTS is semantically consistent if it abstracts at least one concrete system) and as models for checking temporal properties (and thus, a PTS is logically consistent if it gives consistent interpretation to all temporal logic formulas). We study the connection between semantic and logical consistency of PTSs, compare the three families w.r.t. their expressive power (i.e., what can be modeled, what abstractions can be captured using them), and discuss the analysis power of these formalisms, i.e., the cost and precision of model checking. Specifically, we identify a class of PTSs for which semantic and logical consistency coincide and define a necessary and sufficient structural condition to guarantee consistency. We also show that all three families of PTSs have the same expressive power (but do differ in succinctness). However, GKMTSs are more precise (i.e., can establish more properties) for model checking than the other two families. The direct use of GKMTSs in practice has been hampered by the difficulty of encoding them symbolically. We address this problem by developing a new semantics for temporal logic of PTSs that makes the MixTS family as precise for model checking as the GKMTS family. The outcome is a symbolic model checking algorithm that combines the efficient encoding of MixTSs with the model checking precision of GKMTSs. Our preliminary experiments indicate that the new algorithm is a good match for predicate-abstraction-based model checkers. [Copyright &y& Elsevier]

Abstract: A recurring task in image processing, approximation theory, and the numerical solution of partial differential equations is to reconstruct a piecewise-smooth real-valued function , where , from its truncated Fourier transform (its truncated spectrum). An essential step is edge detection for which a variety of one-dimensional schemes have been developed over the last few decades. Most higher-dimensional edge detection algorithms consist of applying one-dimensional detectors in each component direction in order to recover the locations in where is singular (the singular support). In this paper, we present a multidimensional algorithm which identifies the wavefront of a function from spectral data. The wavefront of f is the set of points which encode both the location of the singular points of a function and the orientation of the singularities. (Here denotes the unit sphere in N dimensions.) More precisely, is the direction of the normal line to the curve or surface of discontinuity at x. Note that the singular support is simply the projection of the wavefront onto its x-component. In one dimension, the wavefront is a subset of , and it coincides with the singular support. In higher dimensions, geometry comes into play and they are distinct. We discuss the advantages of wavefront reconstruction and indicate how it can be used for segmentation in magnetic resonance imaging (MRI). [ABSTRACT FROM AUTHOR]

Abstract: Many scientific applications can be structured as parallel task graphs (PTGs), that is, graphs of data-parallel tasks. Adding data parallelism to a task-parallel application provides opportunities for higher performance and scalability, but poses additional scheduling challenges. In this paper, we study the off-line scheduling of multiple PTGs on a single, homogeneous cluster. The objective is to optimize performance without compromising fairness among the PTGs. We consider the range of previously proposed scheduling algorithms applicable to this problem, from both the applied and the theoretical literature, and we propose minor improvements when possible. Our main contribution is an extensive evaluation of these algorithms in simulation, using both synthetic and real-world application configurations, using two different metrics for performance and one metric for fairness. We identify a handful of algorithms that provide good trade-offs when considering all these metrics. The best algorithm overall is one that structures the schedule as a sequence of phases of increasing duration based on a makespan guarantee produced by an approximation algorithm. [Copyright &y& Elsevier]

Abstract: This work is concerned with several properties of solutions of stochastic differential equations arising from hybrid switching diffusions. The word “hybrid” highlights the coexistence of continuous dynamics and discrete events. The underlying process has two components. One component describes the continuous dynamics, whereas the other is a switching process representing discrete events. One of the main features is the switching component depending on the continuous dynamics. In this paper, weak continuity is proved first. Then continuous and smooth dependence on initial data are demonstrated. In addition, it is shown that certain functions of the solutions verify a system of Kolmogorov''s backward differential equations. Moreover, rates of convergence of numerical approximation algorithms are dealt with. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate nonlinear -term approximation with regard to orthogonal dictionaries. We consider this problem in the periodic multivariate case for generalized Besov classes under the condition where is a univariate function. We prove that the well-known dictionary which consists of trigonometric polynomials (shifts of the Dirichlet kernels) is nearly optimal among orthogonal dictionaries. Moreover, it is established that for these classes near-best -term approximation, with regard to , can be achieved by simple greedy-type algorithms. [Copyright &y& Elsevier]

Abstract: Scheduling of large-scale, distributed topology-aware applications requires that not only the properties of the requested machines be considered, but also the properties of the machines’ interconnections. This requirement severely complicates the scheduling process, as even a matching between a single multi-processor task and available machines in a single time slot becomes an NP-complete problem with no polynomial approximation. In this paper we propose a complete scheduling framework for multi-cluster, heterogeneous environments that provides, in practice, an efficient solution for the scheduling of topology-aware applications. The proposed framework is very flexible as it is composed of pluggable components and can be easily configured to support a variety of scheduling policies. We also describe three novel scheduling and coallocation algorithms that were developed and plugged into the framework. The proposed scheduling framework was integrated into the QosCosGrid 1 [1] http://www.qoscosgrid.eu. system, where it is used as the main decision-making module. [ABSTRACT FROM AUTHOR]