Optimal Approximation on Sd

The asymptotic behavior of the n-widths of a wide range of sets of smooth functions on a d-dimensional sphere in L_q(S^d) is studied. Upper and lower bounds for the n-widths are established. Moreover, it is shown that these upper and lower bounds coincide for some important concrete examples.     

The Average Widths and Non-linear Widths of the Classes of Multivariate Functions with Bounded Moduli of Smoothness

The classes of the multivariate functions with bounded moduli on Rd and Td are given and their average σ-widths and non-linear n-widths are discussed. The weak asymptotic behaviors are established for the corresponding quantities.     

About Widths of Wiener Space in theLq-Norm

We calculate the average Kolmogorov and linearn-widths of the Wiener space in theL_q-norm. For the case 1 ≤q< ∞, then-widthsd_ndecrease asymptotically asn^-1/2.     

N-Widths and ε-Dimensions for High-Dimensional Approximations

In this paper, we study linear trigonometric hyperbolic cross approximations, Kolmogorov n-widths d _n (W,H ^γ ), and ε-dimensions n _ε (W,H ^γ ) of periodic d-variate function classes W with anisotropic smoothness, where d may be large. We are interested in finding the accurate dependence of d _n (W,H ^γ ) and n _ε (W,H ^γ ) as a function of two variables n, d and ε, d, respectively. Recall that n, the dimension of the approximating subspace, is the main parameter in the study of convergence rates with respect to n going to infinity. However, the parameter d may seriously affect this rate when d is large. We construct linear approximations of functions from W by trigonometric polynomials with frequencies from hyperbolic crosses and prove upper bounds for the error measured in isotropic Sobolev spaces H ^γ . Furthermore, in order to show the optimality of the proposed approximation, we prove upper and lower bounds of the corresponding n-widths d _n (W,H ^γ ) and ε-dimensions n _ε (W,H ^γ ). Some of the received results imply that the curse of dimensionality can be broken in some relevant situations.     

Estimates of n-widths of Sobolev's classes on compact globally symmetric spaces of rank one

Estimates of Kolmogorov's and linear n-widths of Sobolev's classes on compact globally symmetric spaces of rank 1 (i.e. on S^d, , , , P¹⁶(Cay)) are established. It is shown that these estimates have sharp orders in different important cases. New estimates for the (p,q)-norms of multiplier operators are given. We apply our results to get sharp orders of best polynomial approximation and n-widths.     

Orthogonal exponentials on the ball

We show that there does not exist an infinite sequence of vectors λ_n in ℝ^d, d > 1, such that the corresponding exponentials eⁱ〈λ_n,x〉, x ∈ ℝ^d, when considered on the unit ball B in ℝ^d, are pairwise orthogonal in L²(B) (B being endowed with Lebesgue measure). The weaker result that L²(B) does not have an infinite orthogonal base of exponentials has recently been established by A. Iosevich, N. Katz, and S. Pedersen in [2]. For d = 2 the present result was announced in the author's 1974 paper [1].     

Some open problems concerning the star-discrepancy

We discuss open problems on the minimal star-discrepancy of an n-point set in the d-dimensional unit cube [0,1]^d. We emphasize the aspect of dimension dependence and of simultaneous dependence on n and d.     

Widths and optimal sampling in spaces of analytic functions

Let Ω be a finitely-connected planar domain and μ be a positive measure with compact supportE in Ω. LetA _p be the unit ball of the Hardy spaceH ^p. The main result of this paper is that Kolmogorov, Gelfand, and linearn-widths ofA _p inL ^q are comparable in size to each other and to the sampling error ifq≤p. Moreover, ifp=q=2 andE is small enough, then all these quantities are equal.     

Entropy and Widths of Multiplier Operators on Two-Point Homogeneous Spaces

In this article we continue the development of methods of estimating n-widths and entropy of multiplier operators begun in 1992 by A. Kushpel (Fourier Series and Their Applications, pp. 49–53, 1992; Ukr. Math. J. 45(1):59–65, 1993). Our main aim is to give an unified treatment for a wide range of multiplier operators Λ on symmetric manifolds. Namely, we investigate entropy numbers and n-widths of decaying multiplier sequences of real numbers \(\varLambda=\{\lambda_{k}\}_{k=1}^{\infty}\), |λ ₁|≥|λ ₂|≥?, \(\varLambda:L_{p}(\mathbb{M}^{d}) \rightarrow L_{q}(\mathbb{M}^{d})\) on two-point homogeneous spaces \(\mathbb{M}^{d}\): \(\mathbb{S}^{d}\), ? ^d (?), ? ^d (?), ? ^d (?), ?¹⁶(Cay). In the first part of this article, general upper and lower bounds are established for entropy and n-widths of multiplier operators. In the second part, different applications of these results are presented. In particular, we show that these estimates are order sharp in various important situations. For example, sharp order estimates are found for function sets with finite and infinite smoothness. We show that in the case of finite smoothness (i.e., |λ _k |?k ^?γ (lnk)^?ζ, γ/d>1, ζ≥0, k→∞), we have \(e_{n}(\varLambda U_{p}(\mathbb{S}^{d}), L_{q}(\mathbb{S}^{d})) \ll d_{n}(\varLambda U_{p}(\mathbb{S}^{d}), L_{q}(\mathbb{S}^{d}))\), n→∞, but in the case of infinite smoothness (i.e., \(|\lambda_{k}| \asymp e^{-\gamma k^{r}}\), γ>0, 0<r≤1, k→∞), we have \(e_{n}(\varLambda U_{p}(\mathbb{S}^{d}), L_{q}(\mathbb{S}^{d})) \gg d_{n}(\varLambda U_{p}(\mathbb{S}^{d}), L_{q}(\mathbb{S}^{d}))\), n→∞ for different p and q, where \(U_{p}(\mathbb{S}^{d})\) denotes the closed unit ball of \(L_{p}(\mathbb{S}^{d})\).     

The Fine Structure of the n-Widths of H-Spaces in Lq(−1, 1)

The n-widths of the unit ball A_p of the Hardy space H^p in L_q( −1, 1) are determined asymptotically. It is shown that for 1 ≤ q < p ≤∞ there exist constants k₁ and k₂ such that [formula]≤ d_n(A_p, L_q(−1, 1)),dⁿ(A_p, L_q(−1, 1)), δ_n(A_p, L_q(−1, 1))[formula]where d_n, dⁿ, and δ_n denote the Kolmogorov, Gel′fand and linear n-widths, respectively. This result is an improvement of estimates previously obtained by Burchard and Höllig and by the author.     

n-Widths,Faber Expansion,and Computation of Analytic Functions

LetBH^∞(Ω) be the space of analytic functionsfin the region Ω for which |f(z)| ≤ 1,z∈ Ω, and letKbe a compact subset of Ω. How can we compute the values of any functionf∈BH^∞(Ω) at an arbitrary pointz∈K? One of the approaches to this problem applies the results concerning then-widths and ϵ-entrophy of classBH^∞(Ω) in the metricC(K). In the case whenKhas a simply connected complement inC and Ω is a canonical neighbourhood ofK, the classical tools for approximation off∈BH^∞(Ω) inC(K) give the Faber series. This work is concerned with the following: the exact values of Kolmogorov and othern-widths of Hardy spacesH^p, then-widths and ϵ-entrophy of classBH^∞(Ω), the optimality of Faber approximations, and computing values of analytic functions with the help of Faber series.     

Asymptotics of the n-widths of a Wiener spiral in complex Hilbert space

We describe isometric embeddings of the Wiener spiral in complex Hilbert space and obtain the asymptotics of the Kolmogorov n-widths of specific embeddings. We note the difference with the asymptotics of the n-widths of the Wiener spiral in real Hilbert space.     

Onn-widths of bounded periodic holomorphic functions

The even-dimensional Kolmogorov widthsd _2n , Gel'fand widthsd ²ⁿ , and linear widths _2n ofà inL _q andC are determined exactly. We show that all threen-widths are equal and give a characterization of the widths in terms of Blaschke products.Published in Ukrainskii Matematicheskii Zhurnal, Vol. 47, No. 9, pp. 1170–1175, September, 1995.     

The measure problem for rectangular ranges in d-space

Klee recently posed the question: find an efficient algorithm for computing the measure of a set of n intervals on the line, and the analog for n hyperrectangles (ranges) in d-space. The one-dimensional case is easily solved in O(n log n) and Bentley has proved an O(n^d?1log n) algorithm for dimension d ≥ 2. We present an algorithm for Klee's measure problem that has a worst-case running time of only O(n^d?1) for d?3. While Bentley's algorithm is based on segment trees and requires only linear storage for any dimension, the new method is based on quad-trees and requires quadratic storage for d > 2.     

Continuous Algorithms in n-Term Approximation and Non-Linear Widths

In the present paper we investigate optimal continuous algorithms in n-term approximation based on various non-linear n-widths, and n-term approximation by the dictionary V formed from the integer translates of the mixed dyadic scales of the tensor product multivariate de la Vallée Poussin kernel, for the unit ball of Sobolev and Besov spaces of functions with common mixed smoothness. The asymptotic orders of these quantities are given. For each space the asymptotic orders of non-linear n-widths and n-term approximation coincide. Moreover, these asymptotic orders are achieved by a continuous algorithm of n-term approximation by V, which is explicitly constructed.     

On the homogeneous algebraic graphs of large girth and their applications

Families of finite graphs of large girth were introduced in classical extremal graph theory. One important theoretical result here is the upper bound on the maximal size of the graph with girth ?2d established in Even Circuit Theorem by P. Erdös. We consider some results on such algebraic graphs over any field. The upper bound on the dimension of variety of edges for algebraic graphs of girth ?2d is established. Getting the lower bound, we use the family of bipartite graphs D(n,K) with n?2 over a field K, whose partition sets are two copies of the vector space Kⁿ. We consider the problem of constructing homogeneous algebraic graphs with a prescribed girth and formulate some problems motivated by classical extremal graph theory. Finally, we present a very short survey on applications of finite homogeneous algebraic graphs to coding theory and cryptography.     

Widths and distributions of values of the approximation functional on the sobolev spaces with measure

We obtain asymptotic values for the integraln-widths of Sobolev classesW ₂ ^r equipped with Gaussian measure in theL _q -norm.     

Über die Wurzelschranke für das Minimalgewicht von codes

Let d be the minimum distance of an (n, k) code $\text{C}$, invariant under an abelian group acting transitively on the basis of the ambient space over a field F with char F × n. Assume that $\text{C}$ contains the repetition code, that dim($\text{C}$ ∏ $\text{C}$^⊥) = k ? 1 and that the supports of the minimal weight vectors of $\text{C}$ form a 2-design. Then d² ? d + 1 ? n with equality if and only if the design is a projective plane of order d ? 1. The case d² ? d + 1 = n can often be excluded with Hall's multiplier theorem on projective planes, a theorem which follows easily from the tools developed in this paper Moreover, if d² ? d + 1 > n and F = GF(2) then (d ? 1)² ? n. Examples are the generalized quadratic residue codes.     

On Monte Carlo methods for Bayesian multivariate regression models with heavy-tailed errors

We consider Bayesian analysis of data from multivariate linear regression models whose errors have a distribution that is a scale mixture of normals. Such models are used to analyze data on financial returns, which are notoriously heavy-tailed. Let π denote the intractable posterior density that results when this regression model is combined with the standard non-informative prior on the unknown regression coefficients and scale matrix of the errors. Roughly speaking, the posterior is proper if and only if n≥d+k, where n is the sample size, d is the dimension of the response, and k is number of covariates. We provide a method of making exact draws from π in the special case where n=d+k, and we study Markov chain Monte Carlo (MCMC) algorithms that can be used to explore π when n>d+k. In particular, we show how the Haar PX-DA technology studied in Hobert and Marchev (2008) [11] can be used to improve upon Liu’s (1996) [7] data augmentation (DA) algorithm. Indeed, the new algorithm that we introduce is theoretically superior to the DA algorithm, yet equivalent to DA in terms of computational complexity. Moreover, we analyze the convergence rates of these MCMC algorithms in the important special case where the regression errors have a Student’s t distribution. We prove that, under conditions on n, d, k, and the degrees of freedom of the t distribution, both algorithms converge at a geometric rate. These convergence rate results are important from a practical standpoint because geometric ergodicity guarantees the existence of central limit theorems which are essential for the calculation of valid asymptotic standard errors for MCMC based estimates.     

Defect indices of powers of a contraction

Let A be a contraction on a Hilbert space H. The defect index d_A of A is, by definition, the dimension of the closure of the range of I-A^∗A. We prove that (1) d_Aⁿ?nd_A for all n?0, (2) if, in addition, Aⁿ converges to 0 in the strong operator topology and d_A=1, then d_Aⁿ=n for all finite n,0?n?dimH, and (3) d_A=d_A^∗ implies d_Aⁿ=d_A^n∗ for all n?0. The norm-one index k_A of A is defined as sup{n?0:‖Aⁿ‖=1}. When dimH=m<∞, a lower bound for k_A was obtained before: k_A?(m/d_A)-1. We show that the equality holds if and only if either A is unitary or the eigenvalues of A are all in the open unit disc, d_A divides m and d_Aⁿ=nd_A for all n, 1?n?m/d_A. We also consider the defect index of f(A) for a finite Blaschke product f and show that d_f(A)=d_Aⁿ, where n is the number of zeros of f.