Small Ball Probabilities for Linear Images of High-Dimensional Distributions

By Mark Rudelson, Roman Vershynin. 2014

111 citations recorded by the source corpus.

Author(s): Rudelson, Mark; Vershynin, Roman | Abstract: We study concentration properties of random vectors of the form $AX$, where $X = (X_1, ..., X_n)$ has independent coordinates and $A$ is a given matrix. We show that the distribution of $AX$ is well spread in space whenever the distributions of $X_i$ are well spread on the line. Specifically, assume that the probability that $X_i$ falls in any given interval of length $T$ is at most $p$. Then the probability that $AX$ falls in any given ball of radius $T \|A\|_{HS}$ is at most $(Cp)^{0.9 r(A)}$, where $r(A)$ denotes the stable rank of $A$ and $C$ is an absolute constant.

Subfields: Applied Mathematics, Computational Theory and Mathematics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/d6b0eaba2af17ba0f546c5a195844a2bd406d5f8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Theory and Mathematics

In Statistics and Probability

Citations in the corpus

No-gaps delocalization for general random matrices (2015, background): “This can be done by a standard covering argument, where a lower bound is first proved for a fixed vector, then extended to a δ-net of the sphere by a union bound, and finally to the whole sphere by approximation.”
Robust machine learning by median-of-means: Theory and practice (2017, methodology): “L1 P i ;i2Iare equivalent over F f. Note also that Assumption3is equivalent to the small ball property (cf. [46,67]) which has been recently used in Learning theory and signal processing. We refer to [47,55,66,68,69,79] for examples of distributions satisfying the small ball assumption. Proposition ”
The smallest singular value of random rectangular matrices with no moment assumptions on entries (2014, result): “y elements: on a modiﬁcation of a standard ε-net argument for matrices (Proposition 3) and on estimates of the distance between a random vector and a ﬁxed linear subspace that follow from a result of [12] (Theorem 4 and Corollary 6 of our paper). Our method is similar in many aspects to the approach”