Search

An efficient numerical algorithm is developed for solving nonlinear functional Volterra integral equations. The core idea is to define an appropriate operator, then combine the Krasnoselskij iterative scheme with collocation at discrete points and the Newton–Cotes quadrature rule. This results in an explicit scheme that does not require solving a nonlinear or linear algebraic system. For the convergence analysis, the discretization error is estimated and proved to converge via a recurrence relation. The discretization error is combined with the Krasnoselskij iteration error to estimate the total approximation error, hence establishing the convergence of the method. Then, numerical experiments are provided, first, to demonstrate the second order convergence of the proposed method, and secondly, to show the better performance of the scheme over the existing nonlinear-based approach. [ABSTRACT FROM AUTHOR]

We present an inexact proximal point algorithm using quasi distances to solve a minimization problem in the Euclidean space. This algorithm is motivated by the proximal methods introduced by Attouch et al., section 4, (Math Program Ser A, 137: 91–129, 2013) and Solodov and Svaiter (Set Valued Anal 7:323–345, 1999). In contrast, in this paper we consider quasi distances, arbitrary (non necessary smooth) objective functions, scalar errors in each objective regularized approximation and vectorial errors on the residual of the regularized critical point, that is, we have an error on the optimality condition of the proximal subproblem at the new point. We obtain, under a coercivity assumption of the objective function, that all accumulation points of the sequence generated by the algorithm are critical points (minimizer points in the convex case) of the minimization problem. As an application we consider a human location problem: How to travel around the world and prepare the trip of a lifetime. [ABSTRACT FROM AUTHOR]

Directed networks are broadly used to represent asymmetric relationships among units. Co-clustering aims to cluster the senders and receivers of directed networks simultaneously. In particular, the well-known spectral clustering algorithm could be modified as the spectral co-clustering to co-cluster directed networks. However, large-scale networks pose great computational challenges to it. In this paper, we leverage sketching techniques and derive two randomized spectral co-clustering algorithms, one random-projection-based and the other random-sampling-based, to accelerate the co-clustering of large-scale directed networks. We theoretically analyze the resulting algorithms under two generative models - the stochastic co-block model and the degree-corrected stochastic co-block model, and establish their approximation error rates and misclustering error rates, indicating better bounds than the state-of-the-art results of co-clustering literature. Numerically, we design and conduct simulations to support our theoretical results and test the efficiency of the algorithms on real networks with up to millions of nodes. A publicly available R package RandClust is developed for better usability and reproducibility of the proposed methods. [ABSTRACT FROM AUTHOR]

This article investigates the finite-time distributed approximate optimization problem of higher order multiagent systems, where the local cost functions are considered to be quadratic functions. This problem is solved via penalty-function-based method. First, by the penalty-function method, a global approximate cost function is constructed. Second, nonlinear distributed optimization algorithms are proposed for higher order multiagent systems by the tool of adding a power integrator technique. In the optimization algorithms design, the gradients of the approximate cost function are utilized. Under the proposed optimization algorithms, the agents approach the approximate optimal solution in finite time. Although there exist errors (they may be called approximation errors) between the approximate minimizers and the global accurate minimizer, the approximation errors can be regulated by penalty parameter and the relationship between the bound of the approximation errors and the penalty parameter is given explicitly. Furthermore, the proposed distributed approximate optimization algorithms are applied to the optimal rendezvous problem of wheeled multimobile robots, making the mobile robots achieve approximate optimization rendezvous in finite time. The effectiveness of the proposed distributed optimization algorithms and their applications to optimal rendezvous problem are validated by simulations. [ABSTRACT FROM AUTHOR]

We present new algorithms for $k$ k -means clustering on a data stream with a focus on providing fast responses to clustering queries. Compared to the state-of-the-art, our algorithms provide substantial improvements in the query time for cluster-center queries while retaining the desirable properties of provably small approximation error and low space usage. Our proposed clustering algorithms systematically reuse the “coresets” (summaries of data) computed for recent queries in answering the current clustering query, a novel technique which we refer to as coreset caching. We also present an algorithm called OnlineCC that integrates the coreset caching idea with a simple sequential streaming $k$ k -means algorithm. In practice, OnlineCC algorithm can provide constant query time. We present both theoretical analysis and detailed experiments demonstrating the correctness, accuracy, and efficiency of all our proposed clustering algorithms. [ABSTRACT FROM AUTHOR]

The $K$ K -means algorithm is one of the most popular clustering methods. However, it is a well-known fact that its performance, in terms of quality of the obtained solution and computational load, highly depends upon its initialization phase. For this reason, different initialization techniques have been developed throughout the years to enable its fast convergence to competitive solutions. In this sense, it is common practice to re-start the $K$ K -means algorithm several times via one of these techniques and keep the solution with the lowest error. Unfortunately, such a choice is still likely to be a poor approximation of the optimal set of centroids. In this article, we introduce a cheap Split-Merge step that can be used to re-start the $K$ K -means algorithm after reaching a fixed point. Under some settings, one can show that this approach reduces the error of the given fixed point without requiring any further iteration of the $K$ K -means algorithm. Moreover, experimental results show that this strategy is able to generate approximations with an associated error that is hard to reach for different multi-start methods, such as multi-start Forgy $K$ K -means, $K$ K -means++ and Hartigan $K$ K -means, while also computing a lower amount of distances than the previous algorithms. [ABSTRACT FROM AUTHOR]

The Binary Iterative Hard Thresholding (BIHT) algorithm is a popular reconstruction method for one-bit compressed sensing due to its simplicity and fast empirical convergence. Despite considerable research on this algorithm, a theoretical understanding of the corresponding approximation error and convergence rate still remains an open problem. This paper shows that the normalized version of BIHT (NBIHT) achieves an approximation error rate optimal up to logarithmic factors. More precisely, using $m$ one-bit measurements of an $s$ -sparse vector $x$ , we prove that the approximation error of NBIHT is of order $O \left ({\frac{1 }{ m }}\right)$ up to logarithmic factors, which matches the information-theoretic lower bound $\Omega \left ({\frac{1 }{ m }}\right)$ proved by Jacques, Laska, Boufounos, and Baraniuk in 2013. To our knowledge, this is the first theoretical analysis of a BIHT-type algorithm that explains the optimal rate of error decay empirically observed in the literature. This also makes NBIHT the first provable computationally-efficient one-bit compressed sensing algorithm that breaks the inverse square-root error decay rate $O \left ({\frac{1 }{ m^{1/2} }}\right)\vphantom {{\left ({\frac{1 }{ m^{1/2} }}\right)}^{'}}$. [ABSTRACT FROM AUTHOR]

The quantum Monte Carlo algorithm can provide significant speedup compared to its classical counterpart. So far, most reported works have utilized Grover's state preparation algorithm. However, this algorithm relies on costly controlled Y rotations to apply the correct amplitudes onto the superposition states. Recently, a comparison-based state preparation method was proposed to reduce computational complexity by avoiding rotation operations. One critical aspect of this method is the generation of the comparison threshold associated with the amplitude of the quantum superposition states. The direct computation of the comparison threshold is often very costly. An alternative is to estimate the threshold with a Taylor approximation. However, Taylor approximations do not work well with heavy-tailed distribution functions such as the Cauchy distribution, which is widely used in applications such as financial modeling. Therefore, a new state preparation method needs to be developed. In this study, an efficient comparison-based state preparation method is proposed for the heavy-tailed Cauchy distribution. Instead of a single Taylor approximation for the entire function domain, this study uses quantum piecewise arithmetic to increase accuracy and reduce computational cost. The proposed piecewise function is in the simplest form to estimate the comparison threshold associated with the amplitudes. Numerical analysis shows that the number of required subdomains increases linearly as the maximum tolerated approximation error decreases exponentially. 197 subdomains are required to keep the error below 1 8192 of the maximum amplitude. Quantum parallelism ensures that the computational complexity of estimating the amplitudes is independent from the number of subdomains. [ABSTRACT FROM AUTHOR]

Several phenomena encountered in nature are characterized by very localized events occurring randomly at given times. Random pulses are an appropriate modelling tool for such events. Usually, the impulses are hidden in the noise due to unwanted convolution. In some cases, the problem is more complex because of the short time lag between the pulses. Considering these problems, the resulting signal is unclear and can lead to an erroneous analysis. Hence the need for deconvolution to restore the pulsed signal in order to obtain a more accurate diagnosis. The main objective of this study is to propose a new algorithm called orthogonal least absolute value. The particularity of this algorithm lies in its selection criterion. The algorithm iteratively selects the atom minimizing the absolute value of the approximation error. This allows the proposed algorithm to outperform classical greedy algorithms when the peaks are very close to each other. Numerical and experimental simulations are performed to study the proposed algorithm and compare its behavior to other greedy algorithms in deconvolution framework. Simulations results prove the performance of the proposed algorithm, especially when the impulses are very close to each other. [ABSTRACT FROM AUTHOR]

• Reviews the existing surface remeshing techniques evolved during the last decade that attempt to solve surface remeshing as an optimization problem and achieve the balance between the typical goals of surface remeshing. • Analyzes the performance parameters of existing surface remeshing techniques. • Identifies the drawbacks in the existing techniques. • Suggests a few improvements in the techniques to enhance the results. Direct triangular surface remeshing algorithms work directly on the surface meshes without involving any complex parameterization techniques. The typical goal of surface remeshing is to find a mesh that is a faithful approximation of the input mesh that maintains the geometric fidelity between input and output meshes, achieve a lower bound on the minimal angles to enhance high element quality while maintaining vertex regularity and sharp feature preservation of the input mesh. The goal of each surface remeshing algorithm varies as per the requirement of the end application and thus achieving a balance between all common goals is a challenging task in remeshing. In this paper, a survey of numerous direct surface remeshing algorithms that have been developed over the past decade is presented. A framework of direct surface remeshing is defined and various phases of the framework are discussed in detail to give new insights into both existing methods and issues. A detailed analysis of how significant challenges have already been overcome and promising perspectives of various methods are presented. [ABSTRACT FROM AUTHOR]

We present goal-oriented a posteriori error estimates for the automatic variationally stable finite element (AVS-FE) method (Calo et al., 2020) for scalar-valued convection–diffusion problems. The AVS-FE method is a Petrov–Galerkin method in which the test space is broken, whereas the trial space consists of classical FE basis functions, e.g., C 0 or Raviart–Thomas functions. We employ the concept of optimal test functions of the discontinuous Petrov–Galerkin (DPG) method by Demkowicz and Gopalakrishnan (Demkowicz and Gopalakrishnan, 2010; Carstensen et al., 2014; Demkowicz and Gopalakrishnan, 2011a; Demkowicz and Gopalakrishnan, 2011b; Demkowicz and Gopalakrishnan, 2012), leading to unconditionally stable FE approximations. Remarkably, by using C 0 or Raviart–Thomas trial spaces, the optimal discontinuous test functions can be computed in a completely decoupled element-by-element fashion. To establish the error estimators we present two approaches: (i) following the classical approach of Becker and Rannacher (Becker and Rannacher, 2001), i.e., the dual solution is sought in the (broken) test space, and (ii) introducing an alternative approach in which we seek C 0 , or Raviart–Thomas, AVS-FE approximations of the dual solution by using the underlying strong form of the dual boundary value problem (BVP). Various numerical verifications for 2D convection-dominated diffusion BVPs show that the estimates of the approximation error by the new alternative method are highly accurate, while the classical approach leads to error estimates of poor quality. Lastly, we present an algorithm for h -adaptive processes based on control of the numerical approximation error via the new alternative approach. Numerical verifications show that the estimator maintains high accuracy as the error converges to zero. [ABSTRACT FROM AUTHOR]

We propose and analyze a generalized splitting method to sample approximately from a distribution conditional on the occurrence of a rare event. This has important applications in a variety of contexts in operations research, engineering, and computational statistics. The method uses independent trials starting from a single particle. We exploit this independence to obtain asymptotic and nonasymptotic bounds on the total variation error of the sampler. Our main finding is that the approximation error depends crucially on the relative variability of the number of points produced by the splitting algorithm in one run and that this relative variability can be readily estimated via simulation. We illustrate the relevance of the proposed method on an application in which one needs to sample (approximately) from an intractable posterior density in Bayesian inference. [ABSTRACT FROM AUTHOR]

This article develops a brand new technique to perform safety monitoring using images for a type of complex industrial processes. The new safety monitoring technique is developed with the aid of a modified nonnegative matrix factorization (NMF) algorithm that is called multiple-centroid strictly convex nonnegative matrix factorization (MCSCNMF). Specifically, MCSCNMF is designed deliberately in an all-new manner such that it can learn more accurate centroids for each group of samples than the existing NMF-like algorithms. Moreover, MCSCNMF takes advantage of multiple centroids instead of single centroid to describe the complicated distribution of each type of samples. Both properties give MCSCNMF a powerful clustering performance and make it beneficial for developing high-performance safety monitoring techniques than the existing NMF-like algorithms. We compare different types of monitoring methods in terms of false negative, false positive, and average approximation error in an experiment on a steel coil painting process. Comparison results demonstrate that the MCSCNMF-based monitoring technique can obtain the best experimental results compared with other monitoring methods all the time. [ABSTRACT FROM AUTHOR]

We consider a linear elliptic partial differential equation (PDE) with a generic uniformly bounded parametric coefficient. The solution to this PDE problem is approximated in the framework of stochastic Galerkin finite element methods. We perform a posteriori error analysis of Galerkin approximations and derive a reliable and efficient estimate for the energy error in these approximations. Practical versions of this error estimate are discussed and tested numerically for a model problem with non-affine parametric representation of the coefficient. Furthermore, we use the error reduction indicators derived from spatial and parametric error estimators to guide an adaptive solution algorithm for the given parametric PDE problem. The performance of the adaptive algorithm is tested numerically for model problems with two different non-affine parametric representations of the coefficient. [ABSTRACT FROM AUTHOR]

Two popular approaches to dimensionality reduction are principal component analysis, which projects onto a small number of well-chosen but non-interpretable directions, and feature selection, which selects a small number of the original features. Feature selection can be abstracted as selecting the subset of columns of a matrix X 2 RNd which minimize the approximation error, i.e., the norm of the residual after projecting X onto the space spanned by the selected columns. Such a combinatorial optimization is usually impractical, and there has been interest in polynomial-cost, random subset selection algorithms that favour small values of this approximation error. We propose sampling from a projection determinantal point process, a repulsive distribution over column indices that favours diversity among the selected columns. We bound the ratio of the expected approximation error over the optimal error of PCA. These bounds improve over the state-of-the-art bounds of volume sampling when some realistic structural assumptions are satisfied for X. Numerical experiments suggest that our bounds are tight, and that our algorithms have comparable performance with the double phase algorithm, often considered the practical state-of-the-art. [ABSTRACT FROM AUTHOR]

The horseshoe prior is frequently employed in Bayesian analysis of high-dimensional models, and has been shown to achieve minimax optimal risk properties when the truth is sparse. While optimization-based algorithms for the extremely popular Lasso and elastic net procedures can scale to dimension in the hundreds of thousands, algorithms for the horseshoe that use Markov chain Monte Carlo (MCMC) for computation are limited to problems an order of magnitude smaller. This is due to high computational cost per step and growth of the variance of time-averaging estimators as a function of dimension. We propose two new MCMC algorithms for computation in these models that have significantly improved performance compared to existing alternatives. One of the algorithms also approximates an expensive matrix product to give orders of magnitude speedup in high-dimensional applications. We prove guarantees for the accuracy of the approximate algorithm, and show that gradually decreasing the approximation error as the chain extends results in an exact algorithm. The scalability of the algorithm is illustrated in simulations with problem size as large as N=5,000 observations and p=50,000 predictors, and an application to a genome-wide association study with N=2,267 and p=98,385. The empirical results also show that the new algorithm yields estimates with lower mean squared error, intervals with better coverage, and elucidates features of the posterior that were often missed by previous algorithms in high dimensions, including bimodality of posterior marginals indicating uncertainty about which covariates belong in the model. [ABSTRACT FROM AUTHOR]

High-accuracy on-line contouring error estimation plays a significant role in contouring accuracy control of multi-axis CNC machining. This paper focuses on developing a high-accuracy on-line estimation algorithm of five-axis contouring errors based on three-point arc approximation (TPAA). The nearest reference tool tip position related to the actual one is searched at first, then the tool tip position contouring error is estimated by the distance between the actual position and the arc formed by the nearest reference tool tip position and its two adjacent reference positions. Similar to the tool tip position, the TPAA algorithm is also conducted to estimate the tool orientation contouring error in the unit spherical coordinate system, where equal proportional factors of the tool tip position and the tool orientation arc-lengths are adopted to ensure the synchronization of the tool tip position contouring error and the tool orientation contouring error. The proposed contouring error estimation algorithm is adapted to different trajectory types and has higher estimation accuracy than linear segment approximation (LSA) algorithm for trajectory segments with high curvature. Various experiments with different testing tool paths are performed on an in-house developed five-axis experiment platform to verify the effectiveness of the proposed algorithm, and the results show that the proposed TPAA algorithm can estimate contouring errors with higher accuracy than existing algorithms based on the curvature arc iterative (CAI) algorithm and the LSA algorithm. [ABSTRACT FROM AUTHOR]

For the problem of distance evaluation from a point X 0 to an ellipse in R 2 and to an ellipsoid in R 3 given by algebraic equation G ( X ) = 0 , we investigate the properties of the distance equation , i.e. an algebraic equation whose zeros coincide with the critical values of the squared distance function. We detail the structure of this equation and an algorithm for finding the point in the quadric nearest to X 0 . We also find analytical formulas for distance approximations using the expansion of the zero of distance equation into power series ∑ j = 1 ∞ ℓ j G j ( X 0 ) . Exact values for the approximation error bounds are obtained via construction of an analogue of the distance equations for the curve-to-curve distance problem. [ABSTRACT FROM AUTHOR]

Particle filters are broadly used to approximate posterior distributions of hidden states in state-space models by means of sets of weighted particles. While the convergence of the filter is guaranteed when the number of particles tends to infinity, the quality of the approximation is usually unknown but strongly dependent on the number of particles. In this paper, we propose a novel method for assessing the convergence of particle filters in an online manner, as well as a simple scheme for the online adaptation of the number of particles based on the convergence assessment. The method is based on a sequential comparison between the actual observations and their predictive probability distributions approximated by the filter. We provide a rigorous theoretical analysis of the proposed methodology and, as an example of its practical use, we present simulations of a simple algorithm for the dynamic and online adaptation of the number of particles during the operation of a particle filter on a stochastic version of the Lorenz 63 system. [ABSTRACT FROM PUBLISHER]

Designing and implementing systems as an interconnection of smaller subsystems is a common practice for modularity and standardization of components and design algorithms. Although not typically cast in this framework, many of these approaches can be viewed within the mathematical context of functional composition. This paper re-interprets and generalizes within the functional composition framework one such approach known as filter sharpening, i.e., interconnecting filter modules which have significant approximation error in order to obtain improved filter characteristics. More specifically, filter sharpening is approached by determining the composing polynomial to minimize the infinity-norm of the approximation error, utilizing the First Algorithm of Remez. This is applied both to sharpening for FIR, even-symmetric filters and for the more general case of subfilters that have complex-valued frequency responses including causal IIR filters and for continuous-time filters. Within the framework of functional composition, this paper also explores the use of functional decomposition to approximate a desired system as a composition of simpler functions based on a two-norm on the approximation error. Among the potential advantages of this decomposition is the ability for modular implementation in which the inner component of the functional decomposition represents the subfilters and the outer the interconnection. [ABSTRACT FROM AUTHOR]

Linear phase is an important characteristic of digital filters in many signal processing applications. In this paper, two iterative reweighted minimax phase error algorithms are proposed to design nearly linear-phase infinite impulse response (IIR) digital filters with prescribed or simultaneously minimized magnitude errors and preset transition-band gain. In each iteration of the algorithms, a weighted minimax phase error problem with a fixed weight function is firstly solved using a modified Gauss-Newton method with a variable step length, and the weight function of the phase error is then updated using the square root of a modified envelope of the group-delay error of the filter. With the proposed methods, both very small phase error and group-delay error have been obtained while meeting the requirements on the passband and stopband magnitude errors and the transition-band gain. Design examples demonstrate the effectiveness of the proposed methods and the excellent performance of the designed filters. [ABSTRACT FROM PUBLISHER]

Several convex formulation methods have been proposed previously for statistical estimation with structured sparsity as the prior. These methods often require a carefully tuned regularization parameter, often a cumbersome or heuristic exercise. Furthermore, the estimate that these methods produce might not belong to the desired sparsity model, albeit accurately approximating the true parameter. Therefore, greedy-type algorithms could often be more desirable in estimating structured-sparse parameters. So far, these greedy methods have mostly focused on linear statistical models. In this paper, we study the projected gradient descent with a non-convex structured-sparse parameter model as the constraint set. Should the cost function have a stable model-restricted Hessian, the algorithm produces an approximation for the desired minimizer. As an example, we elaborate on application of the main results to estimation in generalized linear models. [ABSTRACT FROM AUTHOR]

In Part I of the study of the tensor deflation for CANDECOMP/PARAFAC, we have shown that the rank-1 tensor deflation is applicable under some conditions. Part II of the study presents several initialization algorithms suitable for the algorithm proposed in Part I. In addition, Part II contains an algorithm for the case when one or more factor matrices in the estimated model is constrained to be orthogonal. Finally, Part II provides an error analysis of the tensor deflation algorithm, which shows that there is a marginal loss of accuracy of the deflation algorithm compared to the ordinary CP decomposition. [ABSTRACT FROM PUBLISHER]

When the precise model of a controlled system is difficult to obtain, a model-free control method is suitable for control system design. The design goal of this paper is to propose a more efficient control method to deal with control systems with unknown system dynamic models and to achieve favorable chattering-free trajectory tracking performance. The cerebellar model articulation controller (CMAC) is an efficient neural network that can be applied for model-free control systems. This study proposes an adaptive dynamic sliding-mode fuzzy CMAC (ADSFC) system, which is comprised of a fuzzy CMAC and a fuzzy compensator. A fuzzy CMAC using an asymmetric Gaussian membership function is the main controller and the fuzzy compensator can compensate the approximation error introduced by a fuzzy CMAC. Moreover, a proportional–integral-type adaptation learning algorithm is developed to speed up the parameter learning. Finally, the proposed ADSFC system is applied to control a voice coil motor (VCM). Finally, the experimental results demonstrate the effectiveness of the proposed ADSFC scheme. [ABSTRACT FROM PUBLISHER]

Abstract: We present the first algorithm for approximating weighted geodesic distances on 2-manifolds in . Our algorithm works on a weighted ε-sample S of the underlying manifold and computes approximate geodesic distances between all pairs of points in S. The approximation error is multiplicative and depends on the density of the sample. The algorithm has a running time of and an optimal space requirement of ; the approximation error is bounded by . As a result of independent and possibly practical interest, we develop the first technique to efficiently approximate the sampling density ε of S; this algorithm naturally carries over to the unweighted case. [Copyright &y& Elsevier]

We present a method for real-time computation of clothoid coordinates that guarantees bounded approximation error over a wide range of clothoid parameters provided that the clothoid’s orientation change and length are bounded. It is shown that coordinates of clothoid with any parameters can be computed from those of a single clothoid (with fixed parameters), using appropriate geometrical transformations. A comprehensive analysis is given on how to determine a required set of clothoids and, based on this, how to sample a clothoid in a lookup table in order to achieve required approximation precision. The algorithm is computationally very efficient and therefore suitable for real-time path planning, as well as for other applications that benefit from fast clothoid computation. [ABSTRACT FROM PUBLISHER]

Sensor data streams often represent signals/trajectories which are twice differentiable (e.g., to give a continuous velocity and acceleration), and this property must be reflected in their segmentation. An adaptive streaming algorithm for this problem is presented. It is based on the greedy look-ahead strategy and is built on the concept of a cubic splinelet. A characteristic feature of the proposed algorithm is the real-time simultaneous segmentation, smoothing, and compression of data streams. The segmentation quality is measured in terms of the signal approximation accuracy and the corresponding compression ratio. The numerical results show the relatively high compression ratios (from 135 to 208, i.e., compressed stream sizes up to 208 times smaller) combined with the approximation errors comparable to those obtained from the state-of-the-art global reference algorithm. The proposed algorithm can be applied to various domains, including online compression and/or smoothing of data streams coming from sensors, real-time IoT analytics, and embedded time-series databases. [ABSTRACT FROM AUTHOR]

Coreset is usually a small weighted subset of an input set of items, that provably approximates their loss function for a given set of queries (models, classifiers, hypothesis). That is, the maximum (worst-case) error over all queries is bounded. To obtain smaller coresets, we suggest a natural relaxation: coresets whose average error over the given set of queries is bounded. We provide both deterministic and randomized (generic) algorithms for computing such a coreset for any finite set of queries. Unlike most corresponding coresets for the worst-case error, the size of the coreset in this work is independent of both the input size and its Vapnik–Chervonenkis (VC) dimension. The main technique is to reduce the average-case coreset into the vector summarization problem, where the goal is to compute a weighted subset of the n input vectors which approximates their sum. We then suggest the first algorithm for computing this weighted subset in time that is linear in the input size, for n ≫ 1 / ε , where ε is the approximation error, improving, e.g., both [ICML'17] and applications for principal component analysis (PCA) [NIPS'16]. Experimental results show significant and consistent improvement also in practice. Open source code is provided. [ABSTRACT FROM AUTHOR]

Alignment and parallelism are frequently found between objects in high-resolution remote sensing images and can be used to interpret and describe the observed scenes. In this paper, we propose new representations of parallelism and alignment as fuzzy spatial relations, which capture the imprecision in the semantics of both relations. We propose two novel definitions of alignment between objects: local and global. In local alignment, each object of the group is aligned with its neighbors, while in global alignment, every object of the group is aligned to all other members. Both definitions consider each object as a whole and are based on relative position measures. They are robust with respect to segmentation errors. Furthermore, we propose an efficient graph-based method to determine which are the locally and the globally aligned groups of objects from a set of segmented objects. In addition, we propose a fuzzy definition for the parallel relation, which is also based on relative position measures and is adequate to represent the parallelism between a globally aligned group of objects and another object or group of objects. Illustrative examples on optical satellite images show the description power of these two relations and their combination for image interpretation. [ABSTRACT FROM AUTHOR]

Abstract: Fast and accurate phase equilibrium calculations have been a hot research topic during the past decades due to the increased computational effort they impose in process simulation. Reduction methods have attracted significant interest as a means to accelerate calculations by decreasing the problem''s dimensionality. However, when many binary interaction parameters (BIPs) exhibit non-zero values, reduction methods offer limited advantage and the introduction of approximation error is inevitable. In this work a new method is presented for replacing the conventional spectral decomposition basis vectors by new ones so that the approximation error of the energy parameter is minimized instead of that of BIP matrix. The new reduced variables set leads to improved flash calculations accuracy, thus allowing them to be performed at a given accuracy level using fewer reduced variables compared to the conventional approach. Moreover, it is shown that the formulation of the proposed matrix decomposition method is a generalization of the spectral analysis one. The extension of the proposed method to temperature-dependent BIPs is also discussed. A set of examples demonstrates the efficiency of the proposed method. The method can be readily applied to all existing phase behavior algorithms within the reduced variables framework as it intervenes solely on the treatment of the BIP matrix. [Copyright &y& Elsevier]

We consider the minimum error entropy (MEE) criterion and an empirical risk minimization learning algorithm when an approximation of Rényi's entropy (of order 2) by Parzen windowing is minimized. This learning algorithm involves a Parzen windowing scaling parameter. We present a learning theory approach for this MEE algorithm in a regression setting when the scaling parameter is large. Consistency and explicit convergence rates are provided in terms of the approximation ability and capacity of the involved hypothesis space. Novel analysis is carried out for the generalization error associated with Rényi's entropy and a Parzen windowing function, to overcome technical difficulties arising from the essential differences between the classical least squares problems and the MEE setting. An involved symmetrized least squares error is introduced and analyzed, which is related to some ranking algorithms. [ABSTRACT FROM AUTHOR]

Mixed-scaling-rotation (MSR) coordinate rotation digital computer (CORDIC) is an attractive approach to synthesizing complex rotators. This paper presents the fixed-point error analysis and parameter selections of MSR-CORDIC with applications to the fast Fourier transform (FFT). First, the fixed-point mean squared error of the MSR-CORDIC is analyzed by considering both the angle approximation error and signal round-off error incurred in the finite precision arithmetic. The signal to quantization noise ratio (SQNR) of the output of the FFT synthesized using MSR-CORDIC is thereafter estimated. Based on these analyses, two different parameter selection algorithms of MSR-CORDIC are proposed for general and dedicated MSR-CORDIC structures. The proposed algorithms minimize the number of adders and word-length when the SQNR of the FFT output is constrained. Design examples show that the FFT designed by the proposed method exhibits a lower hardware complexity than existing methods. [ABSTRACT FROM PUBLISHER]

In practical finite-impulse-response (FIR) digital filter applications, it is often necessary to represent the filter coefficients with a finite number of bits. The finite wordlength restriction increases the filter deviation. This increase can be reduced substantially if the optimal finite wordlength coefficients are used. The time needed to compute these coefficients is greatly reduced with the help of a lower bound on the deviation increase. Derivation of an improved lower bound that uses the well-known LLL algorithm is presented in this correspondence. [ABSTRACT FROM PUBLISHER]

The purpose of this article is to present a general viscosity iteration process {xn} which defined by xn + 1 = (I - anA)Txn + ßn?f(xn) + (an - ßn)xn and to study the convergence of {xn}, where T is a nonexpansive mapping and A is a strongly positive linear operator, if {an}, {ßn} satisfy appropriate conditions, then iteration sequence {xn} converges strongly to the unique solution x* ∈ f(T) of variational inequality ((A-?f)x*,x-x*) = 0,forallx ∈ f(T). Meanwhile, a approximate iteration algorithm is presented which is used to calculate the fixed point of nonexpansive mapping and solution of variational inequality, the error estimate is also given. The results presented in this paper extend, generalize, and improve the results of Xu, G. Marino and Xu and some others. [ABSTRACT FROM AUTHOR]

Abstract: For purposes of actual evaluation, mathematical functions are commonly replaced by approximation polynomials . Examples include floating-point implementations of elementary functions, quadrature or more theoretical proof work involving transcendental functions. Replacing by induces a relative error . In order to ensure the validity of the use of instead of , the maximum error, i.e. the supremum norm must be safely bounded above over an interval , whose width is typically of order . Numerical algorithms for supremum norms are efficient, but they cannot offer the required safety. Previous validated approaches often require tedious manual intervention. If they are automated, they have several drawbacks, such as the lack of quality guarantees. In this article, a novel, automated supremum norm algorithm on univariate approximation errors is proposed, achieving an a priori quality on the result. It focuses on the validation step and paves the way for formally certified supremum norms. Key elements are the use of intermediate approximation polynomials with bounded approximation error and a non-negativity test based on a sum-of-squares expression of polynomials. The new algorithm was implemented in the Sollya tool. The article includes experimental results on real-life examples. [Copyright &y& Elsevier]

Abstract: We propose an early stopping algorithm for learning gradients. The motivation is to choose “useful” or “relevant” variables by a ranking method according to norms of partial derivatives in some function spaces. In the algorithm, we used an early stopping technique, instead of the classical Tikhonov regularization, to avoid over-fitting. After stating dimension-dependent learning rates valid for any dimension of the input space, we present a novel error bound when the dimension is large. Our novelty is the independence of power index of the learning rates on the dimension of the input space. [Copyright &y& Elsevier]

Abstract: Many learning algorithms use hypothesis spaces which are trained from samples, but little theoretical work has been devoted to the study of these algorithms. In this paper we show that mathematical analysis for these algorithms is essentially different from that for algorithms with hypothesis spaces independent of the sample or depending only on the sample size. The difficulty lies in the lack of a proper characterization of approximation error. To overcome this difficulty, we propose an idea of using a larger function class (not necessarily linear space) containing the union of all possible hypothesis spaces (varying with the sample) to measure the approximation ability of the algorithm. We show how this idea provides error analysis for two particular classes of learning algorithms in kernel methods: learning the kernel via regularization and coefficient based regularization. We demonstrate the power of this approach by its wide applicability. [Copyright &y& Elsevier]

In the past decade, inertial measurement sensors have found their way into many wearable devices where they are used in a broad range of applications, including fitness tracking, step counting, navigation, activity recognition, or motion capturing. One of their key features that is widely used in motion capturing applications is their capability of estimating the orientation of the device and, thus, the orientation of the limb it is attached to. However, tracking a human's motion at reasonable sampling rates comes with the drawback that a substantial amount of data needs to be transmitted between devices or to an end point where all device data is fused into the overall body pose. The communication typically happens wirelessly, which severely drains battery capacity and limits the use time. In this paper, we introduce fastSW, a novel piecewise linear approximation technique that efficiently reduces the amount of data required to be transmitted between devices. It takes advantage of the fact that, during motion, not all limbs are being moved at the same time or at the same speed, and only those devices need to transmit data that actually are being moved or that exceed a certain approximation error threshold. Our technique is efficient in computation time and memory utilization on embedded platforms, with a maximum of 210 instructions on an ARM Cortex-M4 microcontroller. Furthermore, in contrast to similar techniques, our algorithm does not affect the device orientation estimates to deviate from a unit quaternion. In our experiments on a publicly available dataset, our technique is able to compress the data to 10 % of its original size, while achieving an average angular deviation of approximately 2° and a maximum angular deviation below 9°. [ABSTRACT FROM AUTHOR]

Error bounds and complexity bounds in numerical analysis and information-based complexity are often proved for functions that are defined on very simple domains, such as a cube, a torus, or a sphere. We study optimal error bounds for the approximation or integration of functions defined on D d ⊂ R d and only assume that D d is a bounded Lipschitz domain. Some results are even more general. We study three different concepts to measure the complexity: order of convergence, asymptotic constant, and explicit uniform bounds, i.e., bounds that hold for all n (number of pieces of information) and all (normalized) domains. It is known for many problems that the order of convergence of optimal algorithms does not depend on the domain D d ⊂ R d . We present examples for which the following statements are true: 1. Also the asymptotic constant does not depend on the shape of D d or the imposed boundary values, it only depends on the volume of the domain. 2. There are explicit and uniform lower (or upper, respectively) bounds for the error that are only slightly smaller (or larger, respectively) than the asymptotic error bound. [ABSTRACT FROM AUTHOR]

We investigate dimension-dependent estimates of the approximation error for linear algorithms of sampling recovery on Smolyak grids parametrized by m ∈ N , of periodic d -variate functions from the space with Hölder–Zygmund mixed smoothness α > 0. We consider two subsets of the unit ball in this space. The first one is the subset of functions with homogeneous condition, and the second one is the subset of functions depending on ν active variables (1 ≤ ν ≤ d). For these classes, we prove some upper bounds and lower bounds (for α ≤ 2) of the error of the optimal sampling recovery on Smolyak grids, explicit in d , ν , m when d and m may be large. [ABSTRACT FROM AUTHOR]

In this paper, we consider the application of the matching pursuit algorithm (MPA) for spectral analysis of non-stationary signals. First, we estimate the approximation error and the performance time for various MPA modifications and parameters using central processor unit and graphics processing unit (GPU) to identify possible ways to improve the algorithm. Next, we propose the modifications of discrete wavelet transform (DWT) and package wavelet decomposition (PWD) for further use in MPA. We explicitly show that the optimal decomposition level, defined as a level with minimum entropy, in DWT and PWD provides the minimum approximation error and the smallest execution time when applied in MPA as a rough estimate in the case of using wavelets as basis functions (atoms). We provide an example of entropy-based estimation for optimal decomposition level in spectral analysis of seismic signals. The proposed modification of the algorithm significantly reduces its computational costs. Results of spectral analysis obtained with MPA can be used for various signal processing applications, including denoising, clustering, classification, and parameter estimation. [ABSTRACT FROM AUTHOR]

Among various approximation formulas for the gamma function, Smith showed that Γ(x+12)∼S(x)=2π(xe)x(2xtanh12x)x/2,x→∞, which is a little-known but accurate and simple one. In this note, we prove that the function x↦lnΓ(x+1/2)−lnS(x) is strictly increasing and concave on (0,∞), which shows that Smith’s approximation is just an upper one. [ABSTRACT FROM AUTHOR]