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.     

The approximate solution of initial-value problems for general Volterra integro-differential equations

We study the application of certain spline collocation methods to Volterra integro-differential equations of orderr where ther-th order derivative of the unknown solution occurs also in the kernel of the integral term. The analysis focuses on the question of the optimal discrete convergence order (at the knots of the approximating spline function).     

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.     

Algorithm/algorithmus 42 an algorithm for cubic spline fitting with convexity constraints

In this paper an algorithm is presented for fitting a cubic spline satisfying certain local concavity and convexity constraints, to a given set of data points. When using theL ₂ norm, this problem results in a quadratic programming problem which is solved by means of the Theil-Van de Panne procedure. The algorithm makes use of the well-conditioned B-splines to represent the cubic splines. The knots are located automatically, as a function of a given upper limit for the sum of squared residuals. A Fortran IV implementation is given.     

A Novel Sparsity Reconstruction Method from Poisson Data for 3D Bioluminescence Tomography

In this paper, we consider 3D Bioluminescence tomography (BLT) source reconstruction from Poisson data in three dimensional space. With a priori information of sources sparsity and MAP estimation of Poisson distribution, we study the minimization of Kullback-Leihbler divergence with ℓ ¹ and ℓ ⁰ regularization. We show numerically that although several ℓ ¹ minimization algorithms are efficient for compressive sensing, they fail for BLT reconstruction due to the high coherence of the measurement matrix columns and high nonlinearity of Poisson fitting term. Instead, we propose a novel greedy algorithm for ℓ ⁰ regularization to reconstruct sparse solutions for BLT problem. Numerical experiments on synthetic data obtained by the finite element methods and Monte-Carlo methods show the accuracy and efficiency of the proposed method.     

The ripple minimization problems in sample data systems

The problem of minimizing the state value between the sampling times of a sampled data regulator is considered in this paper and is termed the ripple minimization problem. It is found that this problem is equivalent to the discrete problem of minimizing the state at the sampling times with a cost functional that includes in addition to the quadratic terms others which are bilinear in x and u. The results of the solution of the discrete optimal problem are used to solve the ripple minimization problem for both time-variant and time-invariant sampled data system. It is found that an additional condition on the rank of the controller matrices is necessary which is to some extent analogous to the condition necessary for preservation of controllability of sampled data system (Kalman et at., Bar-Ness 1975).     

A fast minimization method for blur and multiplicative noise removal

Multiplicative noise and blur removal problems have attracted much attention in recent years. In this paper, we propose an efficient minimization method to recover images from input blurred and multiplicative noisy images. In the proposed algorithm, we make use of the logarithm to transform blurring and multiplicative noise problems into additive image degradation problems, and then employ l ₁-norm to measure in the data-fitting term and the total variation to measure the regularization term. The alternating direction method of multipliers (ADMM) is used to solve the corresponding minimization problem. In order to guarantee the convergence of the ADMM algorithm, we approximate the associated nonconvex domain of the minimization problem by a convex domain. Experimental results are given to demonstrate that the proposed algorithm performs better than the other existing methods in terms of speed and peak signal noise ratio.     

Local and Nonlocal Discrete Regularization on Weighted Graphs for Image and Mesh Processing

We propose a discrete regularization framework on weighted graphs of arbitrary topology, which unifies local and nonlocal processing of images, meshes, and more generally discrete data. The approach considers the problem as a variational one, which consists in minimizing a weighted sum of two energy terms: a regularization one that uses the discrete p-Dirichlet form, and an approximation one. The proposed model is parametrized by the degree p of regularity, by the graph structure and by the weight function. The minimization solution leads to a family of simple linear and nonlinear processing methods. In particular, this family includes the exact expression or the discrete version of several neighborhood filters, such as the bilateral and the nonlocal means filter. In the context of images, local and nonlocal regularizations, based on the total variation models, are the continuous analog of the proposed model. Indirectly and naturally, it provides a discrete extension of these regularization methods for any discrete data or functions.     

A robust least squares based approach to min‐max model predictive control

This article deals with the model predictive control (MPC) of linear, time‐invariant discrete‐time polytopic (LTIDP) systems. The 2‐fold aim is to simplify the treatment of complex issues like stability and feasibility analysis of MPC in the presence of parametric uncertainty as well as to reduce the complexity of the relative optimization procedure. The new approach is based on a two degrees of freedom (2DOF) control scheme, where the output r(k) of the feedforward input estimator (IE) is used as input forcing the closed‐loop system ∑_f. ∑_f is the feedback connection of an LTIDP plant ∑_p with an LTI feedback controller ∑_g. Both cases of plants with measurable and unmeasurable state are considered. The task of ∑_g is to guarantee the quadratic stability of ∑_f, as well as the fulfillment of hard constraints on some physical variables for any input r(k) satisfying an “a priori” determined admissibility condition. The input r(k) is computed by the feedforward IE through the on‐line minimization of a worst‐case finite‐horizon quadratic cost functional and is applied to ∑_f according to the usual receding horizon strategy. The on‐line constrained optimization problem is here simplified, reducing the number of the involved constraints and decision variables. This is obtained modeling r(k) as a B‐spline function, which is known to admit a parsimonious parametric representation. This allows us to reformulate the minimization of the worst‐case cost functional as a box‐constrained robust least squares estimation problem, which can be efficiently solved using second‐order cone programming.     

Trivariate Biharmonic B‐Splines

In this paper, we formulate a novel trivariate biharmonic B‐spline defined over bounded volumetric domain. The properties of bi‐Laplacian have been well investigated, but the straightforward generalization from bivariate case to trivariate one gives rise to unsatisfactory discretization, due to the dramatically uneven distribution of neighbouring knots in 3D. To ameliorate, our original idea is to extend the bivariate biharmonic B‐spline to the trivariate one with novel formulations based on quadratic programming, approximating the properties of localization and partition of unity. And we design a novel discrete biharmonic operator which is optimized more robustly for a specific set of functions for unevenly sampled knots compared with previous methods. Our experiments demonstrate that our 3D discrete biharmonic operators are robust for unevenly distributed knots and illustrate that our algorithm is superior to previous algorithms.     

End conditions for interpolatory sextic splines†

In this paper a sextic spline is defined for interpolation at equally spaced knots along with the end conditions required to complete the definition of the spline. These conditions are in terms of given functional values at the knots and lead to uniform convergence of O(h ⁷) throughout the interval of interpolation. The main objective of defining the end conditions for the sextic spline is to use the sextic spline not only for interpolation purposes, but also for the solution of the fifth-order boundary value problem, with the change consistent with the boundary value problem.     

G2 Tensor Product Splines over Extraordinary Vertices

We present a second order smooth filling of an n‐valent Catmull‐Clark spline ring with n biseptic patches. While an underdetermined biseptic solution to this problem has appeared previously, we make several advances in this paper. Most notably, we cast the problem as a constrained minimization and introduce a novel quadratic energy functional whose absolute minimum of zero is achieved for bicubic polynomials. This means that for the regular 4‐valent case, we reproduce the bicubic B‐splines. In other cases, the resulting surfaces are aesthetically well behaved. We extend our constrained minimization framework to handle the case of input mesh with boundary.     

Knot calculation for spline fitting via sparse optimization

Curve fitting with splines is a fundamental problem in computer-aided design and engineering. However, how to choose the number of knots and how to place the knots in spline fitting remain a difficult issue. This paper presents a framework for computing knots (including the number and positions) in curve fitting based on a sparse optimization model. The framework consists of two steps: first, from a dense initial knot vector, a set of active knots is selected at which certain order derivative of the spline is discontinuous by solving a sparse optimization problem; second, we further remove redundant knots and adjust the positions of active knots to obtain the final knot vector. Our experiments show that the approximation spline curve obtained by our approach has less number of knots compared to existing methods. Particularly, when the data points are sampled dense enough from a spline, our algorithm can recover the ground truth knot vector and reproduce the spline.     

Suboptimal Robot Joint Interpolation Within User-Specified Knot Tolerances

Approximation of a desired robot path can be accomplished by interpolating a curve through a sequence of joint-space knots. A smooth interpolated trajectory can be realized by using trigonometric splines. But, sometimes the joint trajectory is not required to exactly pass through the given knots. The knots may rather be centers of tolerances near which the trajectory is required to pass. In this article, we optimize trigonometric splines through a given set of knots subject to user-specified knot tolerances. The contribution of this article is the straightforward way in which intermediate constraints (i.e., knot angles) are incorporated into the parameter optimization problem. Another contribution is the exploitation of the decoupled nature of trigonometric splines to reduce the computational expense of the problem. The additional freedom of varying the knot angles results in a lower objective function and a higher computational expense compared to the case in which the knot angles are constrained to exact values. The specific objective functions considered are minimum jerk and minimum torque. In the minimum jerk case, the optimization problem reduces to a quadratic programming problem. Simulation results for a two-link manipulator are presented to support the results of this article.     

Correlation between the gradients of the quadratic functional and its clipped prototype

Applicability of clipping of quadratic functional E = −0.5x ⁺ Tx + Bx in the minimization problem is considered (here x is the configurational vector and B ∈ R ^N is real valued vector). The probability that the gradient of this functional and the gradient of clipped functional ɛ = −0.5x ⁺ τx + bx are collinear is shown to be very high (the matrix τ is obtained by clipping of original matrix T: τ_ij = sgnT _ij ). It allows the conclusion that minimization of functional ɛ implies minimization of functional E. We can therefore replace the laborious process of minimizing functional E by the minimization of its clipped prototype ɛ. Use of the clipped functional allows sixteen-times reduction of the computation time and computer memory usage.     

Surface reconstruction using bivariate simplex splines on Delaunay configurations

Recently, a new bivariate simplex spline scheme based on Delaunay configuration has been introduced into the geometric computing community, and it defines a complete spline space that retains many attractive theoretic and computational properties. In this paper, we develop a novel shape modeling framework to reconstruct a closed surface of arbitrary topology based on this new spline scheme. Our framework takes a triangulated set of points, and by solving a linear least-square problem and iteratively refining parameter domains with newly added knots, we can finally obtain a continuous spline surface satisfying the requirement of a user-specified error tolerance. Unlike existing surface reconstruction methods based on triangular B-splines (or DMS splines), in which auxiliary knots must be explicitly added in advance to form a knot sequence for construction of each basis function, our new algorithm completely avoids this less-intuitive and labor-intensive knot generating procedure. We demonstrate the efficacy and effectiveness of our algorithm on real-world, scattered datasets for shape representation and computing.     

A class of general quartic spline curves with shape parameters

With a support on four consecutive subintervals, a class of general quartic splines are presented for a non-uniform knot vector. The splines have C² continuity at simple knots and include the cubic non-uniform B-spline as a special case. Based on the given splines, piecewise quartic spline curves with three local shape parameters are given. The given spline curves can be C²∩G³ continuous by fixing some values of the curve?s parameters. Without solving a linear system, the spline curves can also be used to interpolate sets of points with C² continuity. The effects of varying the three shape parameters on the shape of the quartic spline curves are determined and illustrated.     

A Faster Algorithm for Computing the Principal Sequence of Partitions of a Graph

We consider the following problem: given an undirected weighted graph G=(V,E,c) with nonnegative weights, minimize function c(δ(Π))−λ|Π| for all values of parameter λ. Here Π is a partition of the set of nodes, the first term is the cost of edges whose endpoints belong to different components of the partition, and |Π| is the number of components. The current best known algorithm for this problem has complexity O(|V|²) maximum flow computations. We improve it to |V| parametric maximum flow computations. We observe that the complexity can be improved further for families of graphs which admit a good separator, e.g. for planar graphs.     

Shape-preserving knot removal

Starting with a shape-preserving C¹ quadratic spline, we show how knots can be removed to produce a new spline which is within a specified tolerance of the original one, and which has the same shape properties. We give specific algorithms and some numerical examples, and also show how the method can be used to compute approximate best free-knot splines. Finally, we discuss how to handle noisy data, and develop an analogous knot removal algorithm for a monotonicity preserving surface method.     

Quasi-nodal splines

Most spline interpolation operators such as the nodal spline operator introduced by de Villiers and Rohwer in 1987 interpolate data at spline knots. In this paper, we are going to present a method of how to construct a local spline interpolation operator that interpolates at sites that are different from the spline knots. These considerations result in the quasi-nodal spline interpolation operator of degree n that reproduces all polynomials of degree not exceeding n.