Rates of convex approximation in non-hilbert spaces

This paper deals with sparse approximations by means of convex combinations of elements from a predetermined “basis” subsetS of a function space. Specifically, the focus is on therate at which the lowest achievable error can be reduced as larger subsets ofS are allowed when constructing an approximant. The new results extend those given for Hilbert spaces by Jones and Barron, including, in particular, a computationally attractive incremental approximation scheme. Bounds are derived for broad classes of Banach spaces; in particular, forL _p spaces with 1<p<∞, theO (n ^−1/2) bounds of Barron and Jones are recovered whenp=2. One motivation for the questions studied here arises from the area of “artificial neural networks,” where the problem can be stated in terms of the growth in the number of “neurons” (the elements ofS) needed in order to achieve a desired error rate. The focus on non-Hilbert spaces is due to the desire to understand approximation in the more “robust” (resistant to exemplar noise)L _p, 1 ≤p<2, norms. The techniques used borrow from results regarding moduli of smoothness in functional analysis as well as from the theory of stochastic processes on function spaces.     

Analysis of 1 GeV proton scattering on D and 4He in a non-eikonal approach

A recently formulated theory for multiple hadron scattering is applied to 1.7 GeV/c scattering on D and ⁴He .Agreement is obtained for pD up to θ_CM ～ 90° and for p⁴He over the entire range measured (θ_CM ? 65°).     

A Polynomial-Time Algorithm to Approximate the Mixed Volume within a Simply Exponential Factor

Let K=(K ₁,…,K _n ) be an n-tuple of convex compact subsets in the Euclidean space R ⁿ , and let V(⋅) be the Euclidean volume in R ⁿ . The Minkowski polynomial V _K is defined as V _K (λ ₁,…,λ _n )=V(λ ₁ K ₁+⋅⋅⋅+λ _n K _n ) and the mixed volume V(K ₁,…,K _n ) as

Probing the gravitational redshift with an Earth-orbiting satellite

We present an approach to testing the gravitational redshift effect using the RadioAstron satellite. The experiment is based on a modification of the Gravity Probe A scheme of nonrelativistic Doppler compensation and benefits from the highly eccentric orbit and ultra-stable atomic hydrogen maser frequency standard of the RadioAstron satellite. Using the presented techniques we expect to reach an accuracy of the gravitational redshift test of order ${10}^{?5}$, a magnitude better than that of Gravity Probe A. Data processing is ongoing, our preliminary results agree with the validity of the Einstein Equivalence Principle.     

The Van der Waerden conjecture for mixed discriminants

We prove that the mixed discriminant of doubly stochastic n-tuples of semidefinite hermitian n×n matrices is bounded below by and that this bound is uniquely attained at the n-tuple . This result settles a conjecture posed by R. Bapat in 1989. We consider various generalizations and applications of this result.     

A Deterministic Algorithm for Approximating the Mixed Discriminant and Mixed Volume, and a Combinatorial Corollary

Abstract. We present a deterministic polynomial-time algorithm that computes the mixed discriminant of an n -tuple of positive semidefinite matrices to within an exponential multiplicative factor. To this end we extend the notion of doubly stochastic matrix scaling to a larger class of n -tuples of positive semidefinite matrices, and provide a polynomial-time algorithm for this scaling. As a corollary, we obtain a deterministic polynomial algorithm that computes the mixed volume of n convex bodies in R ⁿ to within an error which depends only on the dimension. This answers a question of Dyer, Gritzmann and Hufnagel. A ``side benefit' is a generalization of Rado's theorem on the existence of a linearly independent transversal.     

Vandermonde Matrices, NP-Completeness, and Transversal Subspaces

Let K be an infinite field. We give polynomial time constructions of families of r-dimensional subspaces of K ⁿ with the following transversality property: any linear subspace of K ⁿ of dimension n–r is transversal to at least one element of the family. We also give a new NP-completeness proof for the following problem: given two integers n and m with n \leq m and a n × m matrix A with entries in Z, decide whether there exists an n × n subdeterminant of A which is equal to zero.     

Positivity and strict contractivity of functions of operators

Carathéodory class functionsf(z) are described having the property that the self-adjoint part off(A) is positive definite for every contractionA whose spectral radius is less than 1. Analogous results are obtained for bounded analytic functions in the unit disc, and for the Nevanlinna class. Applications to Markov chains are indicated.Partially supported by the US Air Force Grant AFOSR-94-0293.Partially supported by the NSF Grant DMS-9500924.