Randomly sample bounds from many multi-dimensional points Let $\mathbb{M}$ be an $m\times n$ matrix, with $m < n$.
My data consists of a large list of points $\mathbf{x}_i\in\mathbb{R}^n$, $i=1,...,N$, where each point satisfies $\mathbb{M}\cdot\mathbf{x}_i = 0$ and $\mathbf{A} < \mathbf{x} < \mathbf{B}$, where vector inequality denotes all component-wise inequality, and $\mathbf{A},\mathbf{B}$ are some vector bounds.
For each vector $\mathbf{b}\in\mathbb{R}^n$, let $\mu(\mathbf{b})$ denote the number of points $\mathbf{x}_i$ that satisfy $\mathbf{x}_i \leq \mathbf{b}$. Obviously $\mu(\mathbf{A}) = 0$ and $\mu(\mathbf{B}) = N$.
Naively taking a random vector $\mathbf{b}$ inside $\mathbf{A} < \mathbf{b} < \mathbf{B}$ will surely yield very low values of $\mu(\mathbf{b})$. Similarly, $\mu(\mathbf{x}_i) = 1$ for most points $\mathbf{x}_i$ I've tried.
So here's my problem. I need a way to randomly sample vectors $\mathbf{b}$ such that all values of $\mu$ are more or less equally represented.
 A: There is a simple way: by picking a coordinate index and sorting the $x_i$ based on their component in this index, we can easily find any specified number of the $x_i$ that are determined by an inequality of the form $x_i \le b$.

As a preliminary calculation, sort the $x_i$ on each coordinate $j$, writing $x_{[i]}^{j}$ for the $i^\text{th}$ smallest element of the data $(x_1^j, x_2^j, \ldots, x_N^j)$, $1\le j\le n$.  (Because the question uses subscripts to index vectors, I will use superscripts to index their coordinates.)  For convenience of notation, write $x_{[0]}^j = A^j$ and $x_{[N+1]}^j=B^j$ for all $j$, whence for each $j,$ $1\le j \le n,$
$$A^j = x_{[0]}^j \lt x_{[1]}^j \le \cdots \le x_{[i]}^j \le \cdots \le x_{[N]}^j \lt x_{[N+1]}^j = B^j.$$
Select $i \in \{0,1,\ldots,N\}$ uniformly at random and choose $j \in \{1,2,\ldots, n\}$ in any manner you like.  This determines a set $E_i^j$ of vectors $b$ with 
$$b^j \in [x_{[i]}^{j}, x_{[i+1]}^j) \text{ and } b^{j^\prime} \in [x_{[N]}^{j^\prime}, B^{j^{\prime}}) \text{ for } j^\prime \ne j.$$
Let $y$ be an arbitrary vector.  Since $y \le b$ if and only if $y^k \le b^k$ for all $1\le k \le n$, this--by the construction of $b$--means $y^j \lt x_{[i+1]}^j$ and $y^{j^\prime} \le x_{[N]}^{j^\prime}$.  Provided there are no ties for $x_{[i+1]}^j$, the former inequality has exactly $i$ solutions (by definition) and the assumptions about $B$ show that the latter set of inequalities is always satisfied.  Therefore $\mu(b) = i$. Select $b\in E_i^j$ in any manner you like.  Since $i$ has a uniform distribution, so does $\mu(b)$.

Two coordinates of $N=10$ vectors are shown as blue dots.  The rectangle delimited by $A$ and $B$ is shown as a pale unit square.  To include exactly $i=5$ vectors, pick either the fifth smallest of the first coordinates and the largest of all other coordinates (shown at the left for $j=1$) or the fifth smallest of the second coordinates and the largest of all other coordinates (shown at the right for $j=2$).  A value of $b$ is shown as a red dot and the region of points it selects is depicted as a darker shaded rectangle.  In this construction it does not matter whether all vectors are confined to a linear subspace, provided only that the coordinates vary over the subspace.
The only condition required for this to work was that there exist at least one coordinate $j$ for which there are no ties among the $(x_i^j)$.  This method will still produce an approximately uniform distribution of $\mu(b)$ provided there is at least one coordinate where the sizes of the tied groups are all very small compared to $N$.
