On orthogonal linear ℓ1 approximation

Summary The problem is considered of orthogonal ₁ fitting of discrete data. Local best approximations are characterized and the question of the robustness of these solutions is considered. An algorithm for the problem is presented, along with numerical results of its application to some data sets.     

Spline approximation of a non-linear Riemann–Hilbert problem†

In this article we use linear spline approximation of a non-linear Riemann–Hilbert problem on the unit disk. The boundary condition for the holomorphic function is reformulated as a non-linear singular integral equation A(u) = 0, where A : H ¹(Γ) → H ¹(Γ) is defined via a Nemytski operator. We approximate A by A ⁿ : H ¹(Γ) → H ¹(Γ) using spline collocation and show that this defines a Fredholm quasi-ruled mapping. Following the results of (A.I. ?nirel'man, The degree of quasi-ruled mapping and a nonlinear Hilbert problem, Math. USSR-Sbornik 18 (1972), pp. 373–396; M.A. Efendiev, On a property of the conjugate integral and a nonlinear Hilbert problem, Soviet Math. Dokl. 35 (1987), pp. 535–539; M.A. Efendiev, W.L. Wendland, Nonlinear Riemann–Hilbert problems for multiply connected domains, Nonlinear Anal. 27 (1996), pp. 37–58; Nonlinear Riemann–Hilbert problems without transversality. Math. Nachr. 183 (1997), pp. 73–89; Nonlinear Riemann–Hilbert problems for doubly connected domains and closed boundary data, Topol. Methods Nonlinear Anal. 17 (2001), pp. 111–124; Nonlinear Riemann–Hilbert problems with Lipschitz, continuous boundary data without transversality, Nonlinear Anal. 47 (2001), pp. 457–466; Nonlinear Riemann–Hilbert problems with Lipschitz-continuous boundary data: Doubly connected domains, Proc. Roy. Soc. London Ser. A 459 (2003), pp. 945–955.), we define a degree of mapping and show the existence of the spline solutions of the fully discrete equations A ⁿ (u) = 0, for n large enough. We conclude this article by discussing the solvability of the non-linear collocation method, where we shall need an additional uniform strong ellipticity condition for employing the spline approximation.     

Convergence of the reweighted ℓ 1 minimization algorithm for ℓ 2–ℓ p minimization

The iteratively reweighted ? ₁ minimization algorithm (IRL1) has been widely used for variable selection, signal reconstruction and image processing. In this paper, we show that any sequence generated by the IRL1 is bounded and any accumulation point is a stationary point of the ? ₂–? _p minimization problem with 0<p<1. Moreover, the stationary point is a global minimizer and the convergence rate is approximately linear under certain conditions. We derive posteriori error bounds which can be used to construct practical stopping rules for the algorithm.     

Rates of convergence for the approximation of dual shift-invariant systems in ℓ2(ℤ)

A shift-invariant system is a collection of functions {g_m,n} of the form g_m,n(k)=g_m(k–an). Such systems play an important role in time-frequency analysis and digital signal processing. A principal problem is to find a dual system _m,n(k)=_m(k–an) such that each functionf can be written asf= f, _m,ngm,n. The mathematical theory usually addresses this problem in infinite dimensions (typically in L² () or ²()), whereas numerical methods have to operate with a finite-dimensional model. Exploiting the link between the frame operator and Laurent operators with matrix-valued symbol, we apply the finite section method to show that the dual functions obtained by solving a finite-dimensional problem converge to the dual functions of the original infinite-dimensional problem in ²(). For compactly supported g_{m, n} (FIR filter banks) we prove an exponential rate of convergence and derive explicit expressions for the involved constants. Further we investigate under which conditions one can replace the discrete model of the finite section method by the periodic discrete model, which is used in many numerical procedures. Again we provide explicit estimates for the speed of convergence. Some remarks on tight frames complete the paper.Part of this work was done while the author was a visitor at the Department of Statistics at the Stanford University.The author has been partially supported by Erwin-Schrödinger scholarship J01388-MAT of the Austrian Science foundation FWF.     

An approximation for the nonlinear filtering problem,with error bound †

For the standard continuous-time nonlinear filtering problem an approximation approach is derived. The approximate filter is given by the solution to an appropriate discrete-time approximating filtering problem that can be explicitly solved by a finite-dimensional procedure. Furthermore an explicit upper bound for the approximation error is derived. The approximating problem is obtained by first approximating the signal and then using measure transformation to express the original observation process in terms of the approximating signal     

“Almost quasistationary” approximation for the problem of solidification front stability

“Almost quasistationary” approximation is suggested for the investigation of the problem of solidification front stability. It is appropriate for the initial stage of the process when sizes of particles are sufficiently small. The cases of “sphere like” and “cylinder-like” nuclei are considered. Capillary forces are taken into account.      

An existence criterion for the nonlinear $$ell _p$$ ℓ p -norm fitting problem

Central European Journal of Operations Research - In this paper, we give a necessary and sufficient criterion for the existence of the $$ell _p$$ -norm estimate for the nonlinear $$ell _p$$ -norm...     

WEB-spline based mesh-free finite element analysis for the approximation of the stationary Navier–Stokes problem

The objective in this paper is to discuss the existence and the uniqueness of a weighted extended B$B$-spline (WEB-spline) based discrete solution for the stationary incompressible Navier–Stokes equations. The WEB-spline discretization is newly developed methodology which satisfies the inf–sup condition or Ladyshenskaya–Babus?ka–Brezzi (LBB) condition. The main advantage of these new elements over standard finite elements is that they use regular grids instead of irregular partitions of the domain, thus eliminating the difficult and time-consuming pre-processing step. An error estimate for this WEB-spline based discrete solution is also obtained.     

On the finite element approximation for maxwell’s problem in polynomial domains of the plane

The time-harmonic Maxwell boundary value problem in polygonal domains of R² is considered. The behaviour of the solution in the neighbourhood of nonregular boundary points is given and asymptotic error estimates in L₂- and in curl-div-norm for a finite element approximation of the solution are derived     

Laguerre spectral approximation of Stokes’ first problem for third-grade fluid

A Laguerre–Galerkin method is proposed and analyzed for Quasilinear parabolic differential equation which arises from Stokes’ first problem for a third-grade fluid on a semi-infinite interval. By reformulating this equation with suitable functional transforms, it is shown that the Laguerre–Galerkin approximations are convergent on a semi-infinite interval with spectral accuracy. An efficient and accurate algorithm based on the Laguerre–Galerkin approximations to the transformed equations is developed and implemented. Effects of non-Newtonian parameters on the flow phenomena are analyzed and documented.     

On the global convergence of a generalized iterative procedure for the minisum location problem with ℓ p distances for p > 2

This paper presents a procedure to solve the classical location median problem where the distances are measured with ? _p -norms with p > 2. In order to do that we consider an approximated problem. The global convergence of the sequence generated by this iterative scheme is proved. Therefore, this paper closes the still open question of giving a modification of the Weiszfeld algorithm that converges to an optimal solution of the median problem with ? _p norms and ${p \in (2, \infty)}$ . The paper ends with a computational analysis of the different provided iterative schemes.     

Linear programming for the 0–1 quadratic knapsack problem

In this paper we consider the quadratic knapsack problem which consists in maximizing a positive quadratic pseudo-Boolean function subject to a linear capacity constraint. We propose a new method for computing an upper bound. This method is based on the solution of a continuous linear program constructed by adding to a classical linearization of the problem some constraints rebundant in 0–1 variables but nonredundant in continuous variables. The obtained upper bound is better than the bounds given by other known methods. We also propose an algorithm for computing a good feasible solution. This algorithm is an elaboration of the heuristic methods proposed by Chaillou, Hansen and Mahieu and by Gallo, Hammer and Simeone. The relative error between this feasible solution and the optimum solution is generally less than 1%. We show how these upper and lower bounds can be efficiently used to determine the values of some variables at the optimum. Finally we propose a branch-and-bound algorithm for solving the quadratic knapsack problem and report extensive computational tests.     

A Projection Proximal-Point Algorithm for ℓ1 Minimization

The problem of the minimization of least squares functionals with ?¹ penalties is considered in an infinite dimensional Hilbert space setting. Though there are several algorithms available in the finite dimensional setting there are only a few of them that come with a proper convergence analysis in the infinite dimensional setting.

In this work we provide an algorithm from a class that has not been considered for ?¹ minimization before, namely, a proximal-point method in combination with a projection step. We show that this idea gives a simple and easy-to-implement algorithm. We present experiments that indicate that the algorithm may perform better than other algorithms if we employ them without any special tricks. Hence, we may conclude that the projection proximal-point idea is a promising idea in the context of ?¹ minimization.     

Weak type inequalities for the ℓ 1-summability of higher dimensional Fourier transforms

Under some weak conditions on θ, it was verified in [21, 17] that the maximal operator of the ? ₁-θ-means of a tempered distribution is bounded from H _p (? ^d ) to L _p (? ^d ) for all d/(d + α) < p ≤ ∞, where 0 < α ≤ 1 depends only on θ. In this paper, we prove that the maximal operator is bounded from H _d/(d+α)(? ^d ) to the weak L _d/(d+α)(? ^d ) space. The analogous result is given for Fourier series, as well. Some special cases of the ? ₁-θ-summation are considered, such as the Weierstrass, Picard, Bessel, Fejér, de La Vallée-Poussin, Rogosinski and Riesz summations.     

Exact and approximation algorithms for the min–max k-traveling salesmen problem on a tree

Given k identical salesmen, where k ? 2 is a constant independent of the input size, the min–max k-traveling salesmen problem on a tree is to determine a set of k tours for the salesmen to serve all customers that are located on a tree-shaped network, so that each tour starts from and returns to the root of the tree with the maximum total edge weight of the tours minimized. The problem is known to be NP-hard even when k = 2. In this paper, we have developed a pseudo-polynomial time exact algorithm for this problem with any constant k ? 2, closing a question that has remained open for a decade. Along with this, we have further developed a (1 + ?)-approximation algorithm for any ? > 0.     

The limit spectral graph in semiclassical approximation for the Sturm–Liouville problem with complex polynomial potential

The limit behavior of the discrete spectrum of the Sturm–Liouville problem whose potential is a polynomial with complex coefficients on an interval, on a half-axis, and on the entire axis is studied. It is shown that, at large parameter values, the eigenvalues are concentrated along the so-called limit spectral graph; the curves forming this graph are classified. Asymptotics of eigenvalues along curves of various types in the graph are calculated.     

Generalized cross validation for ℓp-ℓq minimization

Numerical Algorithms - Discrete ill-posed inverse problems arise in various areas of science and engineering. The presence of noise in the data often makes it difficult to compute an accurate...