Dvoretzky Type Theorems for Subgaussian Coordinate Projections

Given a class of functions F on a probability space \((\Omega ,\mu )\), we study the structure of a typical coordinate projection of the class, defined by \(\{(f(X_i))_{i=1}^N : f \in F\}\), where \(X_1,\ldots ,X_N\) are independent, selected according to \(\mu \). We show that when F is a subgaussian class, a typical coordinate projection satisfies a Dvoretzky type theorem.     

Stability Properties of Neighbourly Random Polytopes

We introduce a quantitative parameter measuring m-neighbourliness of symmetric convex polytopes in ℝ ^k . We discuss this parameter for random polytopes generated by subgaussian vectors and show its stability properties. Research of P. Mankiewicz was partially supported by KBN Grant no. 1 P03A 015 27. N. Tomczak-Jaegermann holds the Canada Research Chair in Geometric Analysis.     

An Inscribing Model for Random Polytopes

For convex bodies K with boundary in ℝ ^d , we explore random polytopes with vertices chosen along the boundary of K. In particular, we determine asymptotic properties of the volume of these random polytopes. We provide results concerning the variance and higher moments of this functional, as well as an analogous central limit theorem. The research of V.H. Vu was done under the support of A. Sloan Fellowship and an NSF Career Grant. The research of L. Wu is done while the author was at University of California San Diego.     

Random Projections of Smooth Manifolds

We propose a new approach for nonadaptive dimensionality reduction of manifold-modeled data, demonstrating that a small number of random linear projections can preserve key information about a manifold-modeled signal. We center our analysis on the effect of a random linear projection operator Φ:ℝ ^N →ℝ ^M , M<N, on a smooth well-conditioned K-dimensional submanifold ℳ⊂ℝ ^N . As our main theoretical contribution, we establish a sufficient number M of random projections to guarantee that, with high probability, all pairwise Euclidean and geodesic distances between points on ℳ are well preserved under the mapping Φ. Our results bear strong resemblance to the emerging theory of Compressed Sensing (CS), in which sparse signals can be recovered from small numbers of random linear measurements. As in CS, the random measurements we propose can be used to recover the original data in ℝ ^N . Moreover, like the fundamental bound in CS, our requisite M is linear in the “information level” K and logarithmic in the ambient dimension N; we also identify a logarithmic dependence on the volume and conditioning of the manifold. In addition to recovering faithful approximations to manifold-modeled signals, however, the random projections we propose can also be used to discern key properties about the manifold. We discuss connections and contrasts with existing techniques in manifold learning, a setting where dimensionality reducing mappings are typically nonlinear and constructed adaptively from a set of sampled training data. This research was supported by ONR grants N00014-06-1-0769 and N00014-06-1-0829; AFOSR grant FA9550-04-0148; DARPA grants N66001-06-1-2011 and N00014-06-1-0610; NSF grants CCF-0431150, CNS-0435425, CNS-0520280, and DMS-0603606; and the Texas Instruments Leadership University Program. Web: dsp.rice.edu/cs.     

Multivariate Normal Approximation for Functionals of Random Polytopes

Journal of Theoretical Probability - Consider the random polytope that is given by the convex hull of a Poisson point process on a smooth convex body in $$\mathbb {R}^d$$ . We prove central limit...     

Approximation of Projections of Random Vectors

Let X be a d-dimensional random vector and X _θ its projection onto the span of a set of orthonormal vectors {θ ₁,…,θ _k }. Conditions on the distribution of X are given such that if θ is chosen according to Haar measure on the Stiefel manifold, the bounded-Lipschitz distance from X _θ to a Gaussian distribution is concentrated at its expectation; furthermore, an explicit bound is given for the expected distance, in terms of d, k, and the distribution of X, allowing consideration not just of fixed k but of k growing with d. The results are applied in the setting of projection pursuit, showing that most k-dimensional projections of n data points in ℝ ^d are close to Gaussian, when n and d are large and k=clog (d) for a small constant c.     

Estimating Support Functions of Random Polytopes via Orlicz Norms

We study the expected value of support functions of random polytopes in a certain direction, where the random polytope is given by independent random vectors uniformly distributed in an isotropic convex body. All results are obtained using probabilistic estimates in terms of Orlicz norms that were not used in this connection before.     

Error Bounds for Consistent Reconstruction: Random Polytopes and Coverage Processes

Consistent reconstruction is a method for producing an estimate \(\widetilde{x} \in {\mathbb {R}}^d\) of a signal \(x\in {\mathbb {R}}^d\) if one is given a collection of \(N\) noisy linear measurements \(q_n = \langle x, \varphi _n \rangle + \epsilon _n\), \(1 \le n \le N\), that have been corrupted by i.i.d. uniform noise \(\{\epsilon _n\}_{n=1}^N\). We prove mean-squared error bounds for consistent reconstruction when the measurement vectors \(\{\varphi _n\}_{n=1}^N\subset {\mathbb {R}}^d\) are drawn independently at random from a suitable distribution on the unit-sphere \({\mathbb {S}}^{d-1}\). Our main results prove that the mean-squared error (MSE) for consistent reconstruction is of the optimal order \({\mathbb {E}}\Vert x - \widetilde{x}\Vert ^2 \le K\delta ^2/N^2\) under general conditions on the measurement vectors. We also prove refined MSE bounds when the measurement vectors are i.i.d. uniformly distributed on the unit-sphere \({\mathbb {S}}^{d-1}\) and, in particular, show that in this case, the constant \(K\) is dominated by \(d^3\), the cube of the ambient dimension. The proofs involve an analysis of random polytopes using coverage processes on the sphere.     

Efficient Computation of the Hausdorff Distance Between Polytopes by Exterior Random Covering

In this paper, a simple yet efficient randomized algorithm (Exterior Random Covering) for finding the maximum distance from a point set to an arbitrary compact set in R^d is presented. This algorithm can be used for accelerating the computation of the Hausdorff distance between complex polytopes.     

On the Isotropic Constant of Random Polytopes with Vertices on an $$\ell _p$$-Sphere

The symmetric convex hull of random points that are independent and distributed according to the cone probability measure on the \(\ell _p\)-unit sphere of \({{\mathbb {R}}}^n\) for some \(1\le p < \infty \) is considered. We prove that these random polytopes have uniformly absolutely bounded isotropic constants with overwhelming probability. This generalizes the result for the Euclidean sphere \((p=2)\) obtained by Alonso-Gutiérrez. The proof requires several different tools including a probabilistic representation of the cone measure due to Schechtman and Zinn and moment estimates for sums of independent random variables with log-concave tails originating in a paper of Gluskin and Kwapień.     

Expected Distances between Two Uniformly Distributed Random Points in Rectangles and Rectangular Parallelpipeds

In this paper, the expected distance between two uniformly distributed random points in a rectangle or in a rectangular parallelepiped is computed under three different metrics: the Manhattan metric, the Euclidean metric, and the Chebychev metric.     

Reconstruction and Subgaussian Operators in Asymptotic Geometric Analysis

We present a randomized method to approximate any vector from a set . The data one is given is the set T, vectors of and k scalar products , where are i.i.d. isotropic subgaussian random vectors in , and . We show that with high probability, any for which is close to the data vector will be a good approximation of , and that the degree of approximation is determined by a natural geometric parameter associated with the set T. We also investigate a random method to identify exactly any vector which has a relatively short support using linear subgaussian measurements as above. It turns out that our analysis, when applied to {−1, 1}-valued vectors with i.i.d. symmetric entries, yields new information on the geometry of faces of a random {−1, 1}-polytope; we show that a k- dimensional random {−1, 1}-polytope with n vertices is m-neighborly for The proofs are based on new estimates on the behavior of the empirical process when F is a subset of the L ₂ sphere. The estimates are given in terms of the γ ₂ functional with respect to the ψ ₂ metric on F, and hold both in exponential probability and in expectation. Received: November 2005, Revision: May 2006, Accepted: June 2006     

Uniform Uncertainty Principle for Bernoulli and Subgaussian Ensembles

The paper considers random matrices with independent subgaussian columns and provides a new elementary proof of the Uniform Uncertainty Principle for such matrices. The Principle was introduced by Candes, Romberg and Tao in 2004; for subgaussian random matrices it was carlier proved by the present authors, as a consequence of a general result based on a generic chaining method of Talagrand. The present proof combines a simple measure concentration and a covering argument, which are standard tools of high-dimensional convexity.      

Bayesian Inference of a Parametric Random Spheroid from its Orthogonal Projections

Methodology and Computing in Applied Probability - The paper focuses on a new method for the inference of a parametric random spheroid from the observations of its 2D orthogonal projections. Such a...     

RAPTT: An Exact Two-Sample Test in High Dimensions Using Random Projections

In high dimensions, the classical Hotelling’s T² test tends to have low power or becomes undefined due to singularity of the sample covariance matrix. In this article, this problem is overcome by projecting the data matrix onto lower dimensional subspaces through multiplication by random matrices. We propose RAPTT (RAndom Projection T²-Test), an exact test for equality of means of two normal populations based on projected lower dimensional data. RAPTT does not require any constraints on the dimension of the data or the sample size. A simulation study indicates that in high dimensions the power of this test is often greater than that of competing tests. The advantages of RAPTT are illustrated on a high-dimensional gene expression dataset involving the discrimination of tumor and normal colon tissues.     

Cutting Polytopes and Flag f-Vectors

We show how the flag f -vector of a polytope changes when cutting off any face, generalizing work of Lee for simple polytopes. The result is in terms of explicit linear operators on cd-polynomials. Also, we obtain the change in the flag f -vector when contracting any face of the polytope. Received July 13, 1998, and in revised form April 14, 1999.