Optimal Spline Approximation via ℓ0‐Minimization

Splines are part of the standard toolbox for the approximation of functions and curves in ?^d. Still, the problem of finding the spline that best approximates an input function or curve is ill‐posed, since in general this yields a “spline” with an infinite number of segments. The problem can be regularized by adding a penalty term for the number of spline segments. We show how this idea can be formulated as an ?₀‐regularized quadratic problem. This gives us a notion of optimal approximating splines that depend on one parameter, which weights the approximation error against the number of segments. We detail this concept for different types of splines including B‐splines and composite Bézier curves. Based on the latest development in the field of sparse approximation, we devise a solver for the resulting minimization problems and show applications to spline approximation of planar and space curves and to spline conversion of motion capture data.     

三次Cardinal样条函数的自由参数优化方案

为了合理地取定三次Cardinal样条函数所含的自由参数,讨论了插值问题中三次Cardinal样条函数所含自由参数的优化问题。首先分析了自由参数对三次Cardinal样条函数曲线形状的影响,然后给出了数据插值与函数逼近这2种情形下自由参数最优取值的计算方案,分别得到了具有极小二次平均振荡与极小逼近误差的三次Cardinal样条函数。当需要构造具有良好形状保持效果或逼近效果的三次Cardinal样条函数时,可通过所提出的方案选取自由参数的最优取值。     

Large scale portfolio optimization with piecewise linear transaction costs

We consider the fundamental problem of computing an optimal portfolio based on a quadratic mean-variance model for the objective function and a given polyhedral representation of the constraints. The main departure from the classical quadratic programming formulation is the inclusion in the objective function of piecewise linear, separable functions representing the transaction costs. We handle the non-smoothness in the objective function by using spline approximations. The problem is first solved approximately using a primal-dual interior-point method applied to the smoothed problem. Then, we crossover to an active set method applied to the original non-smooth problem to attain a high accuracy solution. Our numerical tests show that we can solve large scale problems efficiently and accurately.     

C2 interpolation of spatial data subject to arc-length constraints using Pythagorean–hodograph quintic splines

In order to reconstruct spatial curves from discrete electronic sensor data, two alternative C² Pythagorean–hodograph (PH) quintic spline formulations are proposed, interpolating given spatial data subject to prescribed constraints on the arc length of each spline segment. The first approach is concerned with the interpolation of a sequence of points, while the second addresses the interpolation of derivatives only (without spatial localization). The special structure of PH curves allows the arc-length conditions to be expressed as algebraic constraints on the curve coefficients. The C² PH quintic splines are thus defined through minimization of a quadratic function subject to quadratic constraints, and a close starting approximation to the desired solution is identified in order to facilitate efficient construction by iterative methods. The C² PH spline constructions are illustrated by several computed examples.     

连续等距区间上积分值的二次样条插值

目的 在现实中,某些插值问题结点处的函数值往往是未知的,而仅仅已知一些区间上的积分值。为此提出一种给定已知函数在连续等距区间上的积分值构造二次样条插值函数的方法。方法 首先,利用二次B样条基函数的线性组合去满足给定的积分值和两个端点插值条件,该插值问题等价于求解n+2个方程带宽为3的线性方程组。然后,运用算子理论给出二次样条插值函数的误差估计,继而得到二次样条函数逼近结点处的函数值时具有超收敛性。最后,通过等距区间上积分值的线性组合逼近两个端点的函数值方法实现了不带任何边界条件的积分型二次样条插值问题。结果 选取低频率函数,对积分型二次样条插值方法和改进方法分别进行数值测试,发现这两种方法逼近效果都是良好的。同样,选取高频率函数对积分型二次样条插值方法进行数值实验,得到数值收敛阶与理论值相一致。结论 实验结果表明,本文算法相比已有的方法更简单有效,对改进前后的二次样条插值函数在逼近结点处的函数值时的超收敛性得到了验证。该方法对连续等距区间上积分值的函数重构具有普适性。     

L ∞ error bound for the phase matching approximation (the one-step-at-a-time Hankel norm model reduction version)

Parallel to what was done for the balanced model reduction version of the phase approximation problem (see Li and Jonckheere 1987), this paper provides an L ^∞ bound on the phase approximation error when one-step-at-a-time optimal Hankel norm model reduction is used to reduce the stable projection of the phase function matrix. The one-step-at-a-time Hankel norm procedure allows for an L ^∞ phase error bound twice as small as that of the balanced version.     

Penalized solutions to functional regression problems

Recent technological advances in continuous biological monitoring and personal exposure assessment have led to the collection of subject-specific functional data. A primary goal in such studies is to assess the relationship between the functional predictors and the functional responses. The historical functional linear model (HFLM) can be used to model such dependencies of the response on the history of the predictor values. An estimation procedure for the regression coefficients that uses a variety of regularization techniques is proposed. An approximation of the regression surface relating the predictor to the outcome by a finite-dimensional basis expansion is used, followed by penalization of the coefficients of the neighboring basis functions by restricting the size of the coefficient differences to be small. Penalties based on the absolute values of the basis function coefficient differences (corresponding to the LASSO) and the squares of these differences (corresponding to the penalized spline methodology) are studied. The fits are compared using an extension of the Akaike Information Criterion that combines the error variance estimate, degrees of freedom of the fit and the norm of the basis function coefficients. The performance of the proposed methods is evaluated via simulations. The LASSO penalty applied to the linearly transformed coefficients yields sparser representations of the estimated regression surface, while the quadratic penalty provides solutions with the smallest L₂-norm of the basis function coefficients. Finally, the new estimation procedure is applied to the analysis of the effects of occupational particulate matter (PM) exposure on heart rate variability (HRV) in a cohort of boilermaker workers. Results suggest that the strongest association between PM exposure and HRV in these workers occurs as a result of point exposures to the increased levels of PM corresponding to smoking breaks.     

Optimal entropy-constrained non-uniform scalar quantizer design for low bit-rate pixel domain DVC

In this paper, an optimal entropy-constrained non-uniform scalar quantizer is proposed for the pixel domain DVC. The uniform quantizer is efficient for the hybrid video coding since the residual signals conforming to a single-variance Laplacian distribution. However, the uniform quantizer is not optimal for pixel domain distributed video coding (DVC). This is because the uniform quantizer is not adaptive to the joint distribution of the source and the SI, especially for low level quantization. The signal distribution of pixel domain DVC conforms to the mixture model with multi-variance. The optimal non-uniform quantizer is designed according to the joint distribution, the error between the source and the SI can be decreased. As a result, the bit rate can be saved and the video quality won’t sacrifice too much. Accordingly, a better R-D trade-off can be achieved. First, the quantization level is fixed and the optimal RD trade-off is achieved by using a Lagrangian function J(Q). The rate and distortion components is designed based on P(Y|Q). The conditional probability density function of SI Y depend on quantization partitions Q, P(Y|Q), is approximated by a Guassian mixture model at encocder. Since the SI can not be accessed at encoder, an estimation of P(Y|Q) based on the distribution of the source is proposed. Next, J(Q) is optimized by an iterative Lloyd-Max algorithm with a novel quantization partition updating algorithm. To guarantee the convergence of J(Q), the monotonicity of the interval in which the endpoints of the quantizer lie must be satisfied. Then, a quantizer partition updating algorithm which considers the extreme points of the histogram of the source is proposed. Consequently, the entropy-constrained optimal non-uniform quantization partitions are derived and a better RD trade-off is achieved by applying them. Experiment results show that the proposed scheme can improve the performance by 0.5 dB averagely compared to the uniform scalar quantization.     

Collocation method for solving systems of Fredholm and Volterra integral equations

In this paper, a numerical method based on based quintic B-spline has been developed to solve systems of the linear and nonlinear Fredholm and Volterra integral equations. The solutions are collocated by quintic B-splines and then the integral equations are approximated by the four-points Gauss-Turán quadrature formula with respect to the weight function Legendre. The quintic spline leads to optimal approximation and O(h⁶) global error estimates obtained for numerical solution. The error analysis of proposed numerical method is studied theoretically. The results are compared with the results obtained by other methods which show that our method is accurate.     

Fairing an arc spline and designing with G 2 PH quintic spiral transitions

This paper describes a method to smooth an arc spline. Arc splines are G ¹ continuous segments made of circular arcs and straight lines. We have proposed a smooth version of the arc spline by replacing its parts with C-, S-, and J-shaped spiral transitions, stitched with G ² continuity, by using a single segment of Pythagorean hodograph quintic function. Use of a single polynomial function rather than two has the benefit that designers have fewer entities to deal with. Spiral transitions are important in manufacturing industries because of their use in the cutting paths for numerically controlled cutting machinery, highway or railway designing, non-holonomic robot path planning and spur gear designing.     

多层积分值三次样条拟插值

目的 在实际问题中,某些插值问题结点处的函数值往往是未知的,而仅仅知道一些连续等距区间上的积分值。为此提出了一种基于未知函数在连续等距区间上的积分值和多层样条拟插值技术来解决函数重构。该方法称之为多层积分值三次样条拟插值方法。方法 首先,利用积分值的线性组合来逼近结点处的函数值;然后,利用传统的三次B-样条拟插值和相应的误差函数来实现多层三次样条拟插值;最后,给出两层积分值三次样条拟插值算子的多项式再生性和误差估计。结果 选取无穷次可微函数对多层积分值三次样条拟插值方法和已有的积分值三次样条拟插值方法进行对比分析。数值实验印证了本文方法在逼近误差和数值收敛阶均稍占优。结论本文多层三次样条拟插值函数能够在整体上很好的逼近原始函数,一阶和二阶导函数。本文方法较之于已有的积分值三次样条拟插值方法具有更好的逼近误差和数值收敛阶。该方法对连续等距区间上积分值的函数重构具有普适性。     

Fully discrete mixed finite element approximations for non-Darcy flows in porous media

A numerical approximation procedure is proposed to solve equations describing non-Darcy flow of a single-phase fluid in a porous medium in two or three spacial dimensions, including the generalized Forchheimer equation. Fully discrete mixed finite element methods are considered and analyzed for the approximation. Existence and uniqueness of the approximation are discussed and optimal order error estimates in L² are derived for the three relevant functions.     

Approximation by a smooth interpolation spline

The properties of a smooth continuous spline approximation are considered. The existence conditions are established and an algorithm is proposed to determine the parameters of such a spline with segments as the sum of a polynomial and an exponent. The errors of approximating a function and its derivative by such a spline with polynomial segments and segments in the form of the sum of a polynomial and an exponent are estimated.     

L2–Optimal Fopdt Models of High–Order Transfer Functions

Necessary conditions for the L² optimality of a first order plus dead time (FOPDT) model of a high‐order plant are derived using classic analytic function theory. They are expressed as a set of three nonlinear equations that partly resemble the interpolation conditions valid for rational approximation. From these conditions a simple procedure to find the optimal FOPDT model is obtained. Examples taken from the relevant literature are worked out to show the performance of the method in comparison with alternative techniques.     

A linear-time algorithm for linearL1 approximation of points

In this paper we present a linear-time algorithm for approximating a set ofn points by a linear function, or a line, that minimizes theL ₁ norm. The algorithmic complexity of this problem appears not to have been investigated, although anO(n ³) naive algorithm can be easily obtained based on some simple characteristics of an optimumL ₁ solution. Our linear-time algorithm is optimal within a constant factor and enables us to use linearL ₁ approximation of many points in practice. The complexity ofL ₁ linear approximation of a piecewise linear function is also touched upon.     

Finite-time H∞ control of periodic piecewise linear systems

In this paper, the finite-time stability, stabilisation, L₂-gain and H_∞ control problems for a class of continuous-time periodic piecewise linear systems are addressed. By employing a time-varying control scheme in which the time interval of each subsystem constitutes a number of basic time segments, the finite-time controllers can be developed with periodically time-varying control gains. Based on a piecewise time-varying Lyapunov-like function, a sufficient condition of finite-time stability and the relevant time-varying controller are proposed. Considering the finite-time boundedness of the closed-loop periodic system, the L₂-gain criterion with continuous time-varying Lyapunov-like matrix function is studied. A finite-time H_∞ controller is proposed based on the L₂-gain analysis. Finally, numerical simulations are presented to illustrate the effectiveness of the proposed criteria.     

Speeding up simplification of polygonal curves using nested approximations

We develop a top-down multiresolution algorithm (TDMR) to solve iteratively the problem of polygonal curve approximation. This algorithm provides nested polygonal approximations of an input curve. We show theoretically and experimentally that, if the simplification algorithm A{\mathcal{A}} used between any two successive levels of resolution satisfies some conditions, the multiresolution algorithm will have a complexity lower than the complexity of A{\mathcal{A}} applied directly on the input curve to provide the crudest polygonal approximation. In particular, we show that if A{\mathcal{A}} has a O(N ²/K) complexity (the complexity of a reduced search dynamic programming solution approach), where N and K are, respectively, the number of segments in the input curve and the number of segments in the crudest approximation, the complexity of MR is in O(N). We experimentally compare the outcomes of TDMR with those of the optimal full search dynamic programming solution and of classical merge and split approaches. The experimental evaluations confirm the theoretical derivations and show that the proposed approach evaluated on 2D coastal maps either leads to a lower complexity or provides polygonal approximations closer to the initial curves.     

Adaptive recurrent neural network control using a structure adaptation algorithm

This paper proposes an adaptive recurrent neural network control (ARNNC) system with structure adaptation algorithm for the uncertain nonlinear systems. The developed ARNNC system is composed of a neural controller and a robust controller. The neural controller which uses a self-structuring recurrent neural network (SRNN) is the principal controller, and the robust controller is designed to achieve L ² tracking performance with desired attenuation level. The SRNN approximator is used to online estimate an ideal tracking controller with the online structuring and parameter learning algorithms. The structure learning possesses the ability of both adding and pruning hidden neurons, and the parameter learning adjusts the interconnection weights of neural network to achieve favorable approximation performance. And, by the L ² control design technique, the worst effect of approximation error on the tracking error can be attenuated to be less or equal to a specified level. Finally, the proposed ARNNC system with structure adaptation algorithm is applied to control two nonlinear dynamic systems. Simulation results prove that the proposed ARNNC system with structure adaptation algorithm can achieve favorable tracking performance even unknown the control system dynamics function.     

Quadratic optimal neural fuzzy control for synchronization of uncertain chaotic systems

This paper presents a novel quadratic optimal neural fuzzy control for synchronization of uncertain chaotic systems via H^∞ approach. In the proposed algorithm, a self-constructing neural fuzzy network (SCNFN) is developed with both structure and parameter learning phases, so that the number of fuzzy rules and network parameters can be adaptively determined. Based on the SCNFN, an uncertainty observer is first introduced to watch compound system uncertainties. Subsequently, an optimal NFN-based controller is designed to overcome the effects of unstructured uncertainty and approximation error by integrating the NFN identifier, linear optimal control and H^∞ approach as a whole. The adaptive tuning laws of network parameters are derived in the sense of quadratic stability technique and Lyapunov synthesis approach to ensure the network convergence and H^∞ synchronization performance. The merits of the proposed control scheme are not only that the conservative estimation of NFN approximation error bound is avoided but also that a suitable-sized neural structure is found to sufficiently approximate the system uncertainties. Simulation results are provided to verify the effectiveness and robustness of the proposed control method.     

Curve fitting and fairing using conic splines

We present an efficient geometric algorithm for conic spline curve fitting and fairing through conic arc scaling. Given a set of planar points, we first construct a tangent continuous conic spline by interpolating the points with a quadratic Bézier spline curve or fitting the data with a smooth arc spline. The arc spline can be represented as a piecewise quadratic rational Bézier spline curve. For parts of the G¹ conic spline without an inflection, we can obtain a curvature continuous conic spline by adjusting the tangent direction at the joint point and scaling the weights for every two adjacent rational Bézier curves. The unwanted curvature extrema within conic segments or at some joint points can be removed efficiently by scaling the weights of the conic segments or moving the joint points along the normal direction of the curve at the point. In the end, a fair conic spline curve is obtained that is G² continuous at convex or concave parts and G¹ continuous at inflection points. The main advantages of the method lies in two aspects, one advantage is that we can construct a curvature continuous conic spline by a local algorithm, the other one is that the curvature plot of the conic spline can be controlled efficiently. The method can be used in the field where fair shape is desired by interpolating or approximating a given point set. Numerical examples from simulated and real data are presented to show the efficiency of the new method.