Authors:Annie Cuyt; Wen-shin Lee Pages: 987 - 1002 Abstract: The problem of multivariate exponential analysis or sparse interpolation has received a lot of attention, especially with respect to the number of samples required to solve it unambiguously. In this paper we show how to bring the number of samples down to the absolute minimum of (d + 1)n where d is the dimension of the problem and n is the number of exponential terms. To this end we present a fundamentally different approach for the multivariate problem statement. We combine a one-dimensional exponential analysis method such as ESPRIT, MUSIC, the matrix pencil or any Prony-like method, with some linear systems of equations because the multivariate exponents are inner products and thus linear expressions in the parameters. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9570-8 Issue No:Vol. 44, No. 4 (2018)

Authors:Hongjin He; Liusheng Hou; Hong-Kun Xu Pages: 1091 - 1115 Abstract: During the last decade, the state-of-the-art alternating direction method of multipliers (ADMM) has successfully been used to solve many two-block separable convex minimization problems arising from several applied areas such as signal/image processing and statistical and machine learning. It however remains an interesting problem of how to implement ADMM to three-block separable convex minimization problems as required by the situation where many objective functions in the above-mentioned areas are actually more conveniently decomposed to the sum of three convex functions, due also to the observation that the straightforward extension of ADMM from the two-block case to the three-block case is apparently not convergent. In this paper, we shall introduce a new algorithm that is called a partially isochronous splitting algorithm (PISA) in order to implement ADMM for the three-block separable model. The main idea of our algorithm is to incorporate only one proximal term into the last subproblem of the extended ADMM so that the resulting algorithm maximally inherits the promising properties of ADMM. A remarkable superiority over the extended ADMM is that we can simultaneously solve two of the subproblems, thereby taking advantages of the separable structure and parallel architectures. Theoretically, we will establish the global convergence of our algorithm under standard conditions, and also the O(1/t) rate of convergence in both ergodic and nonergodic senses, where t is the iteration counter. The computational competitiveness of our algorithm is shown by numerical experiments on an application to the well-tested robust principal component analysis model. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9574-4 Issue No:Vol. 44, No. 4 (2018)

Authors:Hongjin He; Liusheng Hou; Hong-Kun Xu Pages: 1117 - 1118 Abstract: The original publication of this article has an error. PubDate: 2018-08-01 DOI: 10.1007/s10444-018-9591-y Issue No:Vol. 44, No. 4 (2018)

Authors:Na Liu; Wei Jiang Pages: 1235 - 1248 Abstract: In this article, we proposed a new numerical method to obtain the approximation solution for the time-fractional Schrödinger equation based on reproducing kernel theory and collocation method. In order to overcome the weak singularity of typical solutions, we apply the integral operator to both sides of differential equation and yield a integral equation. We divided the solution of this kind equation into two parts: imaginary part and real part, and then derived the approximate solutions of the two parts in the form of series with easily computable terms in the reproducing kernel space. New bases of reproducing kernel spaces are constructed and the existence of approximate solution is proved. Numerical examples are given to show the accuracy and effectiveness of our approach. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9579-z Issue No:Vol. 44, No. 4 (2018)

Authors:Alan E. Lindsay; Bryan Quaife; Laura Wendelberger Pages: 1249 - 1273 Abstract: We consider the bi-Laplacian eigenvalue problem for the modes of vibration of a thin elastic plate with a discrete set of clamped points. A high-order boundary integral equation method is developed for efficient numerical determination of these modes in the presence of multiple localized defects for a wide range of two-dimensional geometries. The defects result in eigenfunctions with a weak singularity that is resolved by decomposing the solution as a superposition of Green’s functions plus a smooth regular part. This method is applied to a variety of regular and irregular domains and two key phenomena are observed. First, careful placement of clamping points can entirely eliminate particular eigenvalues and suggests a strategy for manipulating the vibrational characteristics of rigid bodies so that undesirable frequencies are removed. Second, clamping of the plate can result in partitioning of the domain so that vibrational modes are largely confined to certain spatial regions. This numerical method gives a precision tool for tuning the vibrational characteristics of thin elastic plates. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9580-6 Issue No:Vol. 44, No. 4 (2018)

Authors:Denis Khleborodov Pages: 1275 - 1293 Abstract: This article presents two methods for developing algorithms of computing scalar multiplication in groups of points on an elliptic curve over finite fields. Two new effective algorithms have been presented: one of them is based on a binary Non-Adjacent Form of scalar representation and another one on a binary of scalar representation method. All algorithms were developed based on simple and composite operations with point and also based on affine and Jacobi coordinates systems taking into account the latest achievements in computing cost reduction. Theorems concerning their computational complexity are formulated and proved for these new algorithms. In the end of this article comparative analysis of both new algorithms among themselves and previously known algorithms are represented. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9581-5 Issue No:Vol. 44, No. 4 (2018)

Authors:F. Lara Pages: 1321 - 1323 Abstract: In this note, the notion of admissible sets contained in the strictly positive orthant introduced in Micchelli et al. (Adv. Comp. Math. 38(3), 455–489 2013) is analyzed. This notion was used to generalize theoretical results and optimization methods for structured sparsity. Unfortunately, we will prove that there is no generalization using admissible sets. PubDate: 2018-08-01 DOI: 10.1007/s10444-017-9583-3 Issue No:Vol. 44, No. 4 (2018)

Authors:Zhaonan Dong Abstract: We study the exponent of the exponential rate of convergence in terms of the number of degrees of freedom for various non-standard p-version finite element spaces employing reduced cardinality basis. More specifically, we show that serendipity finite element methods and discontinuous Galerkin finite element methods with total degree \(\mathcal {P}_{p}\) basis have a faster exponential convergence with respect to the number of degrees of freedom than their counterparts employing the tensor product \(\mathcal {Q}_{p}\) basis for quadrilateral/hexahedral elements, for piecewise analytic problems under p-refinement. The above results are proven by using a new p-optimal error bound for the L2-orthogonal projection onto the total degree \(\mathcal {P}_{p}\) basis, and for the H1-projection onto the serendipity finite element space over tensor product elements with dimension d ≥ 2. These new p-optimal error bounds lead to a larger exponent of the exponential rate of convergence with respect to the number of degrees of freedom. Moreover, these results show that part of the basis functions in \(\mathcal {Q}_{p}\) basis plays no roles in achieving the hp-optimal error bound in the Sobolev space. The sharpness of theoretical results is also verified by a series of numerical examples. PubDate: 2018-09-28 DOI: 10.1007/s10444-018-9637-1

Authors:Andrey Belonosov; Maxim Shishlenin; Dmitriy Klyuchinskiy Abstract: The ill-posed continuation problem for the one-dimensional parabolic equation with the data given on the part of the boundary is investigated. We prove the uniqueness theorem about the solution of the continuation problem. The finite-difference scheme inversion, the singular value decomposition, and gradient type method are numerically compared. The influence of a noisy data on the solution is presented. PubDate: 2018-09-26 DOI: 10.1007/s10444-018-9631-7

Authors:Can Huang; Li-Lian Wang Abstract: In this paper, we propose an accurate numerical means built upon a spectral-Galerkin method in spatial discretization and an enriched multi-step spectral-collocation approach in temporal direction, for the transverse magnetic mode of Maxwell equations in Cole-Cole dispersive media in two-dimensional setting. Our starting point is to derive a new model involving only one unknown field from the original model with three unknown fields: electric, magnetic fields, and the induced electric polarization (described by a global temporal convolution of the electric field). This results in a second-order integral-differential equation with a weakly singular integral kernel expressed by the Mittag-Lefler (ML) function. The most interesting but challenging issue resides in how to efficiently deal with the singularity in time induced by the ML function which is an infinite series of singular power functions with different nature. With this in mind, we introduce a spectral-Galerkin method using Fourier-like basis functions for spatial discretization, leading to a sequence of decoupled temporal integral-differential equations (IDE) with the same weakly singular kernel involving the ML function as the original two-dimensional problem. With a careful study of the regularity of IDE, we incorporate several leading singular terms into the numerical scheme and approximate much regular part of the solution. Then, we solve the IDE by a multi-step well-conditioned collocation scheme together with mapping technique to increase the accuracy and enhance the resolution. We show that such an enriched collocation method is convergent and accurate. PubDate: 2018-09-20 DOI: 10.1007/s10444-018-9636-2

Authors:Thomas Fink Abstract: We consider an extension of the continuous shearlet transform which additionally uses higher order shears. This extension, called the Taylorlet transform, allows for a detection of the position, the orientation, the curvature, and other higher order geometric information of singularities. Employing the novel vanishing moment conditions of higher order, \({\int }_{\mathbb {R}} g(\pm t^{k})t^{m} dt= 0\) for \(k,m\in \mathbb {N}\) , k ≥ 1, on the analyzing function \(g\in \mathcal {S}(\mathbb {R})\) , we can show that the Taylorlet transform exhibits different decay rates for decreasing scales depending on the choice of the higher order shearing variables. This enables a faster detection of the geometric information of singularities in terms of the decay rate with respect to the dilation parameter. Furthermore, we present a construction that yields analyzing functions which fulfill vanishing moment conditions of different orders simultaneously. PubDate: 2018-09-18 DOI: 10.1007/s10444-018-9635-3

Authors:Burak Aksoylu; Fatih Celiker; Orsan Kilicer Abstract: In the original publication, Figure 4 image should be Figure 5, Figure 5 image was a repetition of Figure 6 and the correct image of Figure 4 was not shown. The original article was updated by correcting the images of figures 4, 5, and 6. PubDate: 2018-09-14 DOI: 10.1007/s10444-018-9632-6

Authors:Jesús M. Carnicer; Carmen Godés Abstract: The geometric characterization, introduced by Chung and Yao, identifies node sets for total degree interpolation such that the Lagrange fundamental polynomials are products of linear factors. Sets satisfying the geometric characterization are usually called GC sets. Gasca and Maeztu conjectured that planar GC sets of degree n contain n + 1 collinear points. It has been shown that the conjecture holds for degrees not greater than 5 but it is still unsolved for general degree. One promising approach consists of studying the syzygies of the ideal of polynomials vanishing at the nodes. In order to describe syzygy matrices of GC sets, we analyze the extension of a GC set of degree n to a GC set of degree n + 1, by adding a n + 2 nodes on a line. PubDate: 2018-09-13 DOI: 10.1007/s10444-018-9630-8

Authors:Marek Rydel Abstract: This paper presents a new approach to modeling of linear time-invariant discrete-time non-commensurate fractional-order single-input single-output state space systems by means of the Balanced Truncation and Frequency Weighted model order reduction methods based on the cross Gramian. These reduction methods are applied to the specific rational (integer-order) FIR-based approximation to the fractional-order system, which enables to introduce simple, analytical formulae for determination of the cross Gramian of the system. This leads to significant decrease of computational burden in the reduction algorithm. As a result, a rational and relatively low-order state space approximator for the fractional-order system is obtained. A simulation experiment illustrates an efficiency of the introduced methodology in terms of high approximation accuracy and low time complexity of the proposed method. PubDate: 2018-09-08 DOI: 10.1007/s10444-018-9633-5

Authors:Chuanjun Chen; Kang Li; Yanping Chen; Yunqing Huang Abstract: In this paper, we present a second-order accurate Crank-Nicolson scheme for the two-grid finite element methods of the nonlinear Sobolev equations. This method involves solving a small nonlinear system on a coarse mesh with mesh size H and a linear system on a fine mesh with mesh size h, which can still maintain the asymptotically optimal accuracy compared with the standard finite element method. However, the two-grid scheme can reduce workload and save a lot of CPU time. The optimal error estimates in H1-norm show that the two-grid methods can achieve optimal convergence order when the mesh sizes satisfy h = O(H2). These estimates are shown to be uniform in time. Numerical results are provided to verify the theoretical estimates. PubDate: 2018-08-31 DOI: 10.1007/s10444-018-9628-2

Authors:Chao Zeng; Chunlin Wu Abstract: Nonconvex nonsmooth regularizations have exhibited the ability of restoring images with neat edges in many applications, which has been provided a mathematical explanation by analyzing the discontinuity of the local minimizers of the variational models. Since in many applications the pixel intensity values in digital images are restricted in a certain given range, box constraints are adopted to improve the restorations. A similar property of nonconvex nonsmooth regularization for box-constrained models has been proved in the literature. While many theoretical results are available for anisotropic models, we investigate the isotropic case. We establish similar theoretical results for isotropic nonconvex nonsmooth models with box constraints. Numerical experiments are presented to validate our theoretical results. PubDate: 2018-08-21 DOI: 10.1007/s10444-018-9629-1

Authors:Ya-Ru Fan; Alessandro Buccini; Marco Donatelli; Ting-Zhu Huang Abstract: Compressive sensing (CS) aims at reconstructing high dimensional data from a small number of samples or measurements. In this paper, we propose the minimization of a non-convex functional for the solution of the CS problem. The considered functional incorporates information on the self-similarity of the image by measuring the rank of some appropriately constructed matrices of fairly small dimensions. However, since the rank minimization is a NP hard problem, we consider, as a surrogate function for the rank, a non-convex, but smooth function. We provide a theoretical analysis of the proposed functional and develop an iterative algorithm to compute one of its stationary points. We prove the convergence of such algorithm and show, with some selected numerical experiments, that the proposed approach achieves good performances, even when compared with the state of the art. PubDate: 2018-08-09 DOI: 10.1007/s10444-018-9627-3

Authors:Sina Bittens; Ruochuan Zhang; Mark A. Iwen Abstract: In this paper, a deterministic sparse Fourier transform algorithm is presented which breaks the quadratic-in-sparsity runtime bottleneck for a large class of periodic functions exhibiting structured frequency support. These functions include, e.g., the often considered set of block frequency sparse functions of the form $$f(x) = \sum\limits^{n}_{j = 1} \sum\limits^{B-1}_{k = 0} c_{\omega_{j} + k} e^{i(\omega_{j} + k)x},~~\{ \omega_{1}, \dots, \omega_{n} \} \subset \left( -\left\lceil \frac{N}{2}\right\rceil, \left\lfloor \frac{N}{2}\right\rfloor\right]\cap\mathbb{Z}$$ as a simple subclass. Theoretical error bounds in combination with numerical experiments demonstrate that the newly proposed algorithms are both fast and robust to noise. In particular, they outperform standard sparse Fourier transforms in the rapid recovery of block frequency sparse functions of the type above. PubDate: 2018-08-09 DOI: 10.1007/s10444-018-9626-4

Authors:Roland Herzog; John W. Pearson; Martin Stoll Abstract: Optimal transport problems pose many challenges when considering their numerical treatment. We investigate the solution of a PDE-constrained optimisation problem subject to a particular transport equation arising from the modelling of image metamorphosis. We present the nonlinear optimisation problem, and discuss the discretisation and treatment of the nonlinearity via a Gauss–Newton scheme. We then derive preconditioners that can be used to solve the linear systems at the heart of the (Gauss–)Newton method. PubDate: 2018-08-07 DOI: 10.1007/s10444-018-9625-5

Authors:Burak Aksoylu; Fatih Celiker; Orsan Kilicer Abstract: We present novel nonlocal governing operators in 2D/3D for wave propagation and diffusion. The operators are inspired by peridynamics. They agree with the original peridynamics operator in the bulk of the domain and simultaneously enforce local boundary conditions (BC). The main ingredients are periodic, antiperiodic, and mixed extensions of separable kernel functions together with even and odd parts of bivariate functions on rectangular/box domains. The operators are bounded and self-adjoint. We present all possible 36 different types of BC in 2D which include pure and mixed combinations of Neumann, Dirichlet, periodic, and antiperiodic BC. Our construction is systematic and easy to follow. We provide numerical experiments that verify our theoretical findings. We also compare the solutions of the classical wave and heat equations to their nonlocal counterparts. PubDate: 2018-08-02 DOI: 10.1007/s10444-018-9624-6