Lipschitz continuity of the best approximation operator in vector-valued Chebyshev approximation

When G is a finite dimensional Haar subspace of C(X,R^k), the vector-valued continuous functions (including complex-valued functions when k is 2) from a finite set X to Euclidean k-dimensional space, it is well-known that at any function f in C(X,R^k) the best approximation operator satisfies the strong unicity condition of order 2 and a Lipschitz (Hőlder) condition of order . This note shows that in fact the best approximation operator satisfies the usual Lipschitz condition of order 1.     

Lipschitz continuity and Gateaux differentiability of the best approximation operator in vector-valued Chebyshev approximation

When G is a finite-dimensional Haar subspace of C(X,R^k), the vector-valued functions (including complex-valued functions when k is 2) from a finite set X to Euclidean k-dimensional space, it is well-known that at any function f in C(X,R^k) the best approximation operator satisfies the strong unicity condition of order 2 and a Lipschitz (Hőlder) condition of order . This note shows that in fact the best approximation operator satisfies the usual Lipschitz condition of order 1 and has a Gateaux derivative on a dense set of functions in C(X,R^k).     

A non-linear structure preserving matrix method for the low rank approximation of the Sylvester resultant matrix

A non-linear structure preserving matrix method for the computation of a structured low rank approximation of the Sylvester resultant matrix S(f,g) of two inexact polynomials f=f(y) and g=g(y) is considered in this paper. It is shown that considerably improved results are obtained when f(y) and g(y) are processed prior to the computation of , and that these preprocessing operations introduce two parameters. These parameters can either be held constant during the computation of , which leads to a linear structure preserving matrix method, or they can be incremented during the computation of , which leads to a non-linear structure preserving matrix method. It is shown that the non-linear method yields a better structured low rank approximation of S(f,g) and that the assignment of f(y) and g(y) is important because may be a good structured low rank approximation of S(f,g), but may be a poor structured low rank approximation of S(g,f) because its numerical rank is not defined. Examples that illustrate the differences between the linear and non-linear structure preserving matrix methods, and the importance of the assignment of f(y) and g(y), are shown.     

Stability of the linear inequality method for rational Chebyshev approximation

The linear inequality method is an algorithm for discrete Chebyshev approximation by generalized rationals. Stability of the method with respect to uniform convergence is studied. Analytically, the method appears superior to all others in reliability.     

包含切比雪夫多项式的循环矩阵行列式的计算

行首加r尾r右循环矩阵和行尾加r首r左循环矩阵是两种特殊类型的矩阵,这篇论文中就是利用多项式因式分解的逆变换这一重要的技巧以及这类循环矩阵漂亮的结构和切比雪夫多项式的特殊的结构,分别讨论了第一类、第二类切比雪夫多项式的关于行首加r尾r右循环矩阵和行尾加r首r左循环矩阵的行列式,从而给出了行首加r尾r右循环矩阵和行尾加r首r左循环矩阵的行列式显式表达式.这些显式表达式与切比雪夫多项式以及参数r有关.这一问题的应用背景主要在循环编码,图像处理等信息理论方面.     

An improved non-linear method for the computation of a structured low rank approximation of the Sylvester resultant matrix

This paper reports on improvements to recent work on the computation of a structured low rank approximation of the Sylvester resultant matrix S(f,g)$S(f,g)$ of two inexact polynomials f=f(y)$f=f\left(y\right)$ and g=g(y)$g=g\left(y\right)$. Specifically, it has been shown in previous work that these polynomials must be processed before a structured low rank approximation of S(f,g)$S(f,g)$ is computed. The existing algorithm may still, however, yield a structured low rank approximation of S(f,g)$S(f,g)$, but not a structured low rank approximation of S(g,f)$S(g,f)$, which is unsatisfactory. Moreover, a structured low rank approximation of S(f,g)$S(f,g)$ must be equal to, apart from permutations of its columns, a structured low rank approximation of S(g,f)$S(g,f)$, but the existing algorithm does not guarantee the satisfaction of this condition. This paper addresses these issues by modifying the existing algorithm, such that these deficiencies are overcome. Examples that illustrate these improvements are shown.     

On rank variation of block matrices generated by Nevanlinna matrix functions

Within the framework of the multiple Nevanlinna–Pick matrix interpolation and its related matrix moment problem, we study the rank of block moment matrices of various kinds, generalized block Pick matrices and generalized block Loewner matrices, as well as their Potapov modifications, generated by Nevanlinna matrix functions, and derive statements either on rank (or inertia) invariance in different senses or on rank variation of such types of block matrices (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Bezoutian矩阵的一致逼近形式

借助闭区间上的连续函数可以用Bernstein 多项式一致逼近这一事实,将多项式对所生成的经典Bezoutian 矩阵和Bernstein Bezoutian 矩阵推广到C [0,1]上函数对所对应的情形,给出了 Bezoutian 矩阵一致逼近形式的定义,并且得到如下结论：给出了经典 Bezoutian 矩阵的 Barnett 型分解公式和三角分解公式的一致逼近形式;提供了经典Bezoutian 矩阵和Bernstein Bezoutian 矩阵的一致逼近形式的两类算法;得到了上述两种矩阵的一致逼近形式中元素间的两个恒等关系式。最后,利用数值实例对恒等关系式进行验证,结果表明两类算法是有效的。     

The similarity between the best approximation and the best copositive approximation

In this paper the author studies the copositive approximation in C(?) by elements of finite dimensional Chebyshev subspaces in the general case when ? is any totally ordered compact space. He studies the similarity between me behavior of the ordinary best approximation and the behavior pf the copositive best approximation. At the end of this paper, the author isolates many cases at which the two behaviors are the same.     

The inverse eigenvalue problem of generalized reflexive matrices and its approximation

This paper studies inverse eigenvalue problems of generalized reflexive matrices and their optimal approximations. Necessary and sufficient conditions for the solvability of the problems are derived, the solutions and their optimal approximations are provided.     

Recursive generation of the Galerkin–Chebyshev matrix for convolution kernels

The Galerkin–Chebyshev matrix is the coefficient matrix for the Galerkin method (or the degenerate kernel approximation method) using Chebyshev polynomials. Each entry of the matrix is defined by a double integral. For convolution kernels K(x-y) on finite intervals, this paper obtains a general recursion relation connecting the matrix entries. This relation provides a fast generation of the Galerkin–Chebyshev matrix by reducing the construction of a matrix of order N from N ²+O(N) double integral evaluations to 3N+O(1) evaluations. For the special cases (a) K(x-y)=|x-y|^α-1(-ln|x-y|) ^p and (b) K(x-y)=K _ν(σ|x-y|) (modified Bessel functions), the number of double integral evaluations to generate a Galerkin–Chebyshev matrix of arbitrary order can be further reduced to 2p+2 double integral evaluations in case (a) and to 8 double integral evaluations in case (b). This revised version was published online in June 2006 with corrections to the Cover Date.     

Finite-codimensional Chebyshev subspaces in the complex spaceC(Q)

We consider finite-condimensional Chebyshev subspaces in the complex spaceC(Q), whereQ is a compact Hausdorff space, and prove analogs of some theorems established earlier for the real case by Garkavi and Brown (in particular, we characterize such subspaces). It is shown that if the real spaceC(Q) contains finite-codimensional Chebyshev subspaces, then the same is true of the complex spaceC(Q) (with the sameQ). Translated fromMatermaticheskie Zametki, Vol. 62, No. 2, pp. 178–191, August, 1997. Translated by V. E. Nazaikinskii     

On the rank of certain matrices

This note is an appendix to the paper “Osculating spaces and diophantine equations (with an Appendix by Pietro Corvaja and Umberto Zannier)” by M. Bolognesi and G. Pirola.     

Local reconstruction of low‐rank matrices and subspaces

We study the problem of reconstructing a low‐rank matrix, where the input is an n × m matrix M over a field and the goal is to reconstruct a (near‐optimal) matrix that is low‐rank and close to M under some distance function Δ. Furthermore, the reconstruction must be local, i.e., provides access to any desired entry of by reading only a few entries of the input M (ideally, independent of the matrix dimensions n and m). Our formulation of this problem is inspired by the local reconstruction framework of Saks and Seshadhri (SICOMP, 2010). Our main result is a local reconstruction algorithm for the case where Δ is the normalized Hamming distance (between matrices). Given M that is ‐close to a matrix of rank (together with d and ), this algorithm computes with high probability a rank‐d matrix that is ‐close to M. This is a local algorithm that proceeds in two phases. The preprocessing phase reads only random entries of M, and stores a small data structure. The query phase deterministically outputs a desired entry by reading only the data structure and 2d additional entries of M. We also consider local reconstruction in an easier setting, where the algorithm can read an entire matrix column in a single operation. When Δ is the normalized Hamming distance between vectors, we derive an algorithm that runs in polynomial time by applying our main result for matrix reconstruction. For comparison, when Δ is the truncated Euclidean distance and , we analyze sampling algorithms by using statistical learning tools. A preliminary version of this paper appears appears in ECCC, see: http://eccc.hpi-web.de/report/2015/128/ © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 607–630, 2017     

Estimates of the trace of the inverse of a symmetric matrix using the modified Chebyshev algorithm

In this paper we study how to compute an estimate of the trace of the inverse of a symmetric matrix by using Gauss quadrature and the modified Chebyshev algorithm. As auxiliary polynomials we use the shifted Chebyshev polynomials. Since this can be too costly in computer storage for large matrices we also propose to compute the modified moments with a stochastic approach due to Hutchinson (Commun Stat Simul 18:1059–1076, 1989). In memory of Gene H. Golub.     

Linear restriction problem of Hermitian reflexive matrices and its approximation

In this paper, we consider a linear restriction problem of Hermitian reflexive matrices and its approximation. By using the properties and structure of Hermitian reflexive matrices and the special properties of reflexive vectors and anti-reflexive vectors, we convert the linear restriction problem to an equivalence problem trickily, which is a special feature of this paper and is a different method from other articles. Then we solve this problem completely and also obtain its optimal approximate solution. Moreover, an algorithm provided for it and the numerical examples show that the algorithm is feasible.     

Best uniform approximation to a class of rational functions

We explicitly determine the best uniform polynomial approximation to a class of rational functions of the form 1/²(x−c)+K(a,b,c,n)/(x−c) on [a,b] represented by their Chebyshev expansion, where a, b, and c are real numbers, n−1 denotes the degree of the best approximating polynomial, and K is a constant determined by a, b, c, and n. Our result is based on the explicit determination of a phase angle η in the representation of the approximation error by a trigonometric function. Moreover, we formulate an ansatz which offers a heuristic strategies to determine the best approximating polynomial to a function represented by its Chebyshev expansion. Combined with the phase angle method, this ansatz can be used to find the best uniform approximation to some more functions.     

基于Chebyshev多项式零点的Lagrange插值多项式逼近的注记

本文通过一个例子说明了文献[3]中定理6.9的不完善之处,并建立了:若f∈C^r_[-1,1],则     

Approximation of discrete functions and Chebyshev polynomials orthogonal on the uniform grid

Let _N+2m ={−m, −m+1, …, −1, 0, 1, …,N−1,N, …,N−1+m}. The present paper is devoted to the approximation of discrete functions of the formf : _N+2m → ℝ by algebraic polynomials on the grid Ω _N ={0, 1, …,N−1}. On the basis of two systems of Chebyshev polynomials orthogonal on the sets Ω _N+m and Ω _N , respectively, we construct a linear operatorY _{n+2m, N} =Y _{n+2m, N} (f), acting in the space of discrete functions as an algebraic polynomial of degree at mostn+2m for which the following estimate holds (x ε Ω _N ):