Adaptive Stochastic Collocation on Sparse Grids

We consider Partial Differential Equations (PDEs) with random parameters, solved by adaptive stochastic collocation. Our research studies common error indicators compared to adjoint based error estimates extended to the stochastic framework. We show that such estimates are able to detect the true error very accurately and suggest to replace the expensive adjoint problem by a reduced model. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A Class of Periodic Function Spaces and Interpolation on Sparse Grids

We present a unified approach to error estimates of periodic interpolation on equidistant, full, and sparse grids for functions from a scale of function spaces which includes L ₂-Sobolev spaces, the Wiener algebra and the Korobov spaces.     

Sampling and Cubature on Sparse Grids Based on a B-spline Quasi-Interpolation

Let \(X_n = \{x^j\}_{j=1}^n\) be a set of n points in the d-cube \({\mathbb {I}}^d:=[0,1]^d\), and \(\Phi _n = \{\varphi _j\}_{j =1}^n\) a family of n functions on \({\mathbb {I}}^d\). We consider the approximate recovery of functions f on \({{\mathbb {I}}}^d\) from the sampled values \(f(x^1), \ldots , f(x^n)\), by the linear sampling algorithm \( L_n(X_n,\Phi _n,f) := \sum _{j=1}^n f(x^j)\varphi _j. \) The error of sampling recovery is measured in the norm of the space \(L_q({\mathbb {I}}^d)\)-norm or the energy quasi-norm of the isotropic Sobolev space \(W^\gamma _q({\mathbb {I}}^d)\) for \(1 < q < \infty \) and \(\gamma > 0\). Functions f to be recovered are from the unit ball in Besov-type spaces of an anisotropic smoothness, in particular, spaces \(B^{\alpha ,\beta }_{p,\theta }\) of a “hybrid” of mixed smoothness \(\alpha > 0\) and isotropic smoothness \(\beta \in {\mathbb {R}}\), and spaces \(B^a_{p,\theta }\) of a nonuniform mixed smoothness \(a \in {\mathbb {R}}^d_+\). We constructed asymptotically optimal linear sampling algorithms \(L_n(X_n^*,\Phi _n^*,\cdot )\) on special sparse grids \(X_n^*\) and a family \(\Phi _n^*\) of linear combinations of integer or half integer translated dilations of tensor products of B-splines. We computed the asymptotic order of the error of the optimal recovery. This construction is based on B-spline quasi-interpolation representations of functions in \(B^{\alpha ,\beta }_{p,\theta }\) and \(B^a_{p,\theta }\). As consequences, we obtained the asymptotic order of optimal cubature formulas for numerical integration of functions from the unit ball of these Besov-type spaces.     

Efficient Ritz-Galerkin Discretization of PDEs with Variable Coefficients in arbitrary Dimensions using Sparse Grids

Sparse grids can be used to discretize elliptic differential equations of second order on a d-dimensional cube. Using the Ritz-Galerkin discretization, one obtains a linear equation system with 𝒪 (N (log N)^d−1) unknowns. The corresponding discretization error is 𝒪 (N⁻¹ (log N)^d−1) in the H¹-norm. A major difficulty in using this sparse grid discretization is the complexity of the related stiffness matrix. To reduce the complexity of the sparse grid discretization matrix, we apply prewavelets and a discretization with semi-orthogonality. Furthermore, a recursive algorithm is used, which performs a matrix vector multiplication with the stiffness matrix by 𝒪 (N (log N)^d−1) operations. Simulation results up to level 10 are presented for a 6-dimensional Helmholtz problem with variable coefficients. (© 2017 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

稀疏表示及其在人脸识别中的应用

稀疏表示是近年来新兴的一种数据表示方法,是对人类大脑皮层编码机制的模拟。稀疏表示以其良好的鲁棒性、抗干扰能力、可解释性和判别性等优势,广泛应用于模式识别领域。基于稀疏表示的分类器在人脸识别领域取得了令人惊喜的成就,它将训练样本看成字典,寻求测试样本在字典下的最稀疏的表示,即用尽可能少的训练样本的线性组合来重构测试样本。但是经典的基于稀疏表示的分类器没有考虑训练样本的类别信息,以致被选中的训练样本来自许多类,不利于分类,因此基于组稀疏的分类器被提出。组稀疏方法考虑了训练样本的类别相似性,其目的是用尽可能少类别的训练样本来表示测试样本,然而这类方法的缺点是同类的训练样本或者同时被选中或者同时被丢弃。在实际中,人脸受到光照、表情、姿势甚至遮挡等因素的影响,样本之间关系比较复杂,因此最后介绍局部加权组结构稀疏表示方法。该方法尽量用来自于与测试样本相似的类的训练样本和来自测试样本邻域的训练样本来表示测试样本,以减轻不相关类的干扰,并使得表示更稀疏和更具判别性。     

Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications

We develop a Las Vegas-randomized algorithm which performs interpolation of sparse multivariate polynomials over finite fields. Our algorithm can be viewed as the first successful adaptation of the sparse polynomial interpolation algorithm for the complex field developed by M. Ben-Or and P. Tiwari (1988, in “Proceedings of the 20th ACM Symposium on the Theory of Computing,” pp. 301–309, Assoc. Comput. Mach., New York) to the case of finite fields. It improves upon a previous result by D. Y. Grigoriev, M. Karpinski, and M. F. Singer (1990, SIAM J. Comput.19, 1059–1063) and is by far the most time efficient algorithm (time and processor efficient parallel algorithm) for the problem when the finite field is large. As applications, we obtain Monte Carlo-randomized parallel algorithms for sparse multivariate polynomial factorization and GCD over finite fields. The efficiency of these algorithms improves upon that of the previously known algorithms for the respective problems.     

High-Dimensional Adaptive Sparse Polynomial Interpolation and Applications to Parametric PDEs

We consider the problem of Lagrange polynomial interpolation in high or countably infinite dimension, motivated by the fast computation of solutions to partial differential equations (PDEs) depending on a possibly large number of parameters which result from the application of generalised polynomial chaos discretisations to random and stochastic PDEs. In such applications there is a substantial advantage in considering polynomial spaces that are sparse and anisotropic with respect to the different parametric variables. In an adaptive context, the polynomial space is enriched at different stages of the computation. In this paper, we study an interpolation technique in which the sample set is incremented as the polynomial dimension increases, leading therefore to a minimal amount of PDE solving. This construction is based on the standard principle of tensorisation of a one-dimensional interpolation scheme and sparsification. We derive bounds on the Lebesgue constants for this interpolation process in terms of their univariate counterpart. For a class of model elliptic parametric PDE’s, we have shown in Chkifa et al. (Modél. Math. Anal. Numér. 47(1):253–280, 2013) that certain polynomial approximations based on Taylor expansions converge in terms of the polynomial dimension with an algebraic rate that is robust with respect to the parametric dimension. We show that this rate is preserved when using our interpolation algorithm. We also propose a greedy algorithm for the adaptive selection of the polynomial spaces based on our interpolation scheme, and illustrate its performance both on scalar valued functions and on parametric elliptic PDE’s.     

Computing Jacobi Symbols modulo Sparse Integers and Polynomials and Some Applications

We describe a polynomial time algorithm to compute Jacobi symbols of exponentially large integers of special form, including so-called sparse integers which are exponentially large integers with only polynomially many nonzero binary digits. In a number of papers sequences of Jacobi symbols have been proposed as generators of cryptographically secure pseudorandom bits. Our algorithm allows us to use much larger moduli in such constructions. We also use our algorithm to design a probabilistic polynomial time test which decides if a given integer of the aforementioned type is a perfect square (assuming the Extended Riemann Hypothesis). We also obtain analogues of these results for polynomials over finite fields. Moreover, in this case the perfect square testing algorithm is unconditional. These results can be compared with many known NP-hardness results for some natural problems on sparse integers and polynomials.     

Generalized Normal Derivatives and Their Applications in DDMs with Nonmatching Grids and DG Methods

A class of normal-like derivatives for functions with low regularity defined on Lipschitz domains are introduced and studied.It is shown that the new normal-like derivatives,which are called the generalized normal derivatives,preserve the major prop- erties of the existing standard normal derivatives.The generalized normal derivatives are then applied to analyze the convergence of domain decomposition methods (DDMs) with nonmatching grids and discontinuous Galerkin (DG) methods for second-order el- liptic problems.The approximate solutions generated by these methods still possess the optimal energy-norm error estimates,even if the exact solutions to the underlying elliptic problems admit very low regularities.     

近似Bayes计算前沿研究进展及应用

在大数据和人工智能时代,建立能够有效处理复杂数据的模型和算法,以从数据中获取有用的信息和知识是应用数学、统计学和计算机科学面临的共同难题.为复杂数据建立生成模型并依据这些模型进行分析和推断是解决上述难题的一种有效手段.从一种宏观的视角来看,无论是应用数学中常用的微分方程和动力系统,或是统计学中表现为概率分布的统计模型,还是机器学习领域兴起的生成对抗网络和变分自编码器,都可以看作是一种广义的生成模型.随着所处理的数据规模越来越大,结构越来越复杂,在实际问题中所需要的生成模型也变得也越来越复杂,对这些生成模型的数学结构进行精确地解析刻画变得越来越困难.如何对没有精确解析形式（或其解析形式的精确计算非常困难）的生成模型进行有效的分析和推断,逐渐成为一个十分重要的问题.起源于Bayes统计推断,近似Bayes计算是一种可以免于计算似然函数的统计推断技术,近年来在复杂统计模型和生成模型的分析和推断中发挥了重要作用.该文从经典的近似Bayes计算方法出发,对近似Bayes计算方法的前沿研究进展进行了系统的综述,并对近似Bayes计算方法在复杂数据处理中的应用前景及其和前沿人工智能方法的深刻联系进行了分析和讨论.     

Recent Developments In Harmonic Approximation,With Applications

A theorem of J.L. Walsh (1929) says that if E is a compact subset of Rⁿ with connected complement and if u is harmonic on a neighbourhood of E, then u can be uniformly approximated on E by functions harmonic on the whole of Rⁿ. In Part I of this article we survey some generalizations of Walsh’s theorem from the period 1980–94. In Part II we discuss applications of Walsh’s theorem and its generalizations to four diverse topics: universal harmonic functions, the Radon transform, the maximum principle, and the Dirichlet problem.     

Some Recent Progress and Applications in Graph Minor Theory

In the core of the seminal Graph Minor Theory of Robertson and Seymour lies a powerful theorem capturing the ``rough' structure of graphs excluding a fixed minor. This result was used to prove Wagner's Conjecture that finite graphs are well-quasi-ordered under the graph minor relation. Recently, a number of beautiful results that use this structural result have appeared. Some of these along with some other recent advances on graph minors are surveyed. Research partly supported by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research, Grant number 16740044, by Sumitomo Foundation, by C & C Foundation and by Inoue Research Award for Young Scientists Supported in part by the Research Grant P1–0297 and by the CRC program On leave from: IMFM & FMF, Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia     

正交设计的最新发展和应用-回归分析在正交设计的应用

正交设计有许多新发展,本系列讲座介绍其中的一些便于应用的结果,共有四部份：回归分析在正交设计中的应用,均匀正交设计,正交设计的Ｄ－最优性,以及正交设计的投影性质。本讲强调回归分析用于正交设计的建模、估计、减少参数数目方面的应用     

Negative Index Materials and Their Applications: Recent Mathematics Progress

Negative index materials are artificial structures whose refractive index has negative value over some frequency range.These materials were first investigated theoretically by Veselago in 1946 and were confirmed experimentally by Shelby,Smith,and Schultz in 2001.Mathematically,the study of negative index materials faces two difficulties.Firstly,the equations describing the phenomenon have sign changing coefficients,hence the ellipticity and the compactness are lost in general.Secondly,the localized resonance,i.e.,the field explodes in some regions and remains bounded in some others as the loss goes to 0,might appear.In this survey,the author discusses recent mathematics progress in understanding properties of negative index materials and their applications.The topics are reflecting complementary media,superlensing and cloaking by using complementary media,cloaking a source via anomalous localized resonance,the limiting absorption principle and the well-posedness of the Helmholtz equation with sign changing coefficients.     

Grids in random graphs

Threshold probabilities for the existence in a random graph on n vertices of a graph isomorphic to a given graph of order Cn and average degree at least three are investigated. In particular it is proved that the random graph G(n, p) on n vertices with edge probability contains a square grid on En/2 vertices. © 1994 John Wiley & Sons, Inc.     

Nonlinear Level Set Learning for Function Approximation on Sparse Data with Applications to Parametric Differential Equations

A dimension reduction method based on the “Nonlinear Level set Learning” (NLL) approach is presented for the pointwise prediction of functions which have been sparsely sampled. Leveraging geometric information provided by the Implicit Function Theorem, the proposed algorithm effectively reduces the input dimension to the theoretical lower bound with minor accuracy loss, providing a one-dimensional representation of the function which can be used for regression and sensitivity analysis. Experiments and applications are presented which compare this modified NLL with the original NLL and the Active Subspaces (AS) method. While accommodating sparse input data, the proposed algorithm is shown to train quickly and provide a much more accurate and informative reduction than either AS or the original NLL on two example functions with high-dimensional domains, as well as two state-dependent quantities depending on the solutions to parametric differential equations.     

Sparse Regression by Projection and Sparse Discriminant Analysis

Recent years have seen active developments of various penalized regression methods, such as LASSO and elastic net, to analyze high-dimensional data. In these approaches, the direction and length of the regression coefficients are determined simultaneously. Due to the introduction of penalties, the length of the estimates can be far from being optimal for accurate predictions. We introduce a new framework, regression by projection, and its sparse version to analyze high-dimensional data. The unique nature of this framework is that the directions of the regression coefficients are inferred first, and the lengths and the tuning parameters are determined by a cross-validation procedure to achieve the largest prediction accuracy. We provide a theoretical result for simultaneous model selection consistency and parameter estimation consistency of our method in high dimension. This new framework is then generalized such that it can be applied to principal components analysis, partial least squares, and canonical correlation analysis. We also adapt this framework for discriminant analysis. Compared with the existing methods, where there is relatively little control of the dependency among the sparse components, our method can control the relationships among the components. We present efficient algorithms and related theory for solving the sparse regression by projection problem. Based on extensive simulations and real data analysis, we demonstrate that our method achieves good predictive performance and variable selection in the regression setting, and the ability to control relationships between the sparse components leads to more accurate classification. In supplementary materials available online, the details of the algorithms and theoretical proofs, and R codes for all simulation studies are provided.     

Sparse matrices

One gives a survey of methods and programs for solving large sparse spectral problems based on the Lanczos algorithm. Practically all the important works on this topic are reflected in this survey. One also considers applications of the variants of the Lanczos method to the solution of symmetric indefinite systems of linear equations and to a series of other problems of linear algebra.Translated from Itogi Nauki i Tekhniki, Seriya Matematicheskii Analiz, Vol. 20, pp. 179–260, 1982.