Center-Outward Ranks from Optimal Transport

Why Multivariate Ranks Need a Reference Geometry

In one dimension, ordering observations gives a natural notion of rank. In several dimensions, there is no unique way to say which of two points is “larger”: one may be farther from the center in one direction but closer in another. Center-outward ranks address this by choosing a reference geometry and transporting the data distribution to it. The resulting rank records distance from the reference center, while the sign records direction.

The reference distribution used here is uniform on the unit ball. Optimal transport supplies a principled map from a multivariate distribution to that ball. This construction is different from simply sorting points by their distance from an estimated center: it uses the full distribution to assign positions throughout the reference ball.

Definition: Let \(X\) have an absolutely continuous distribution \(F\) on \(\mathbb{R}^d\) and satisfy \(E[\|X\|^2]<\infty\). Let \(U_d\) denote the uniform distribution on the unit ball \(B_d=\{u\in\mathbb{R}^d:\|u\|\leq 1\}\). The center-outward distribution function \(F_{\pm}\) is the quadratic optimal transport map from \(F\) to \(U_d\): it pushes \(F\) to \(U_d\) and minimizes \(E[\|X-T(X)\|^2]\) over transport maps \(T\) with \(T(X)\sim U_d\). Under these conditions, Brenier’s theorem gives a map unique \(F\)-almost everywhere, equal almost everywhere to the gradient of a convex function. The center-outward rank is \(R_{\pm}(x)=\|F_{\pm}(x)\|\), and the center-outward sign is \(S_{\pm}(x)=F_{\pm}(x)/\|F_{\pm}(x)\|\) when \(F_{\pm}(x)\ne 0\). Set the sign to \(0\) at the center.

Absolute continuity matters: it is the condition that gives the quadratic optimal transport map in the stated gradient-of-a-convex-function form. A distribution that is merely atomless but concentrated on a lower-dimensional set need not satisfy that condition. The finite second moment ensures that the quadratic transport cost is finite. Since the target ball is bounded, it already has a finite second moment.

The rank is a number between zero and one. The sign is a direction on the unit sphere, except at the center. Neither component alone generally gives the full transformed observation: together they recover \(F_{\pm}(x)\) away from the center through \(F_{\pm}(x)=R_{\pm}(x)S_{\pm}(x)\).

Radial Transports: Two Worked Derivations

For a spherically symmetric distribution, a radial map can often be obtained directly. If \(R=\|X\|\), then a point uniformly distributed on the unit ball has radius \(Q\) satisfying \(P(Q\leq q)=q^d\) for \(0\leq q\leq1\). Thus the radial transformation \(R\mapsto P(R_{\text{source}}\leq R)^{1/d}\) gives the desired target radius. It remains important to check optimality, not only the pushforward distribution.

Worked Example: Mapping a Two-Dimensional Radial Exponential Distribution

Let \(X=R(\cos\Theta,\sin\Theta)\), where \(R\) has the exponential distribution with rate \(1\), and \(\Theta\) is independent and uniform on \([0,2\pi)\). Then \(P(R\leq r)=1-e^{-r}\) for \(r\geq0\). Define

T(x)=\sqrt{1-e^{-\|x\|}}\frac{x}{\|x\|},\qquad x\ne 0,

and set \(T(0)=0\). Its output radius is \(Q=\sqrt{1-e^{-R}}\). For \(0\leq q<1\),

P(Q\leq q) =P\bigl(R\leq-\log(1-q^2)\bigr) =1-e^{-[-\log(1-q^2)]} =q^2.

The angle is unchanged and remains uniform and independent of \(Q\). A uniform point on the two-dimensional unit ball has a uniform angle and radius distribution \(P(Q\leq q)=q^2\), so \(T(X)\sim U_2\).

To verify optimality, put \(h(r)=\sqrt{1-e^{-r}}\) and \(\psi(r)=\int_0^r h(t)\,dt\). The function \(h\) is nonnegative and increasing, so \(\psi\) is increasing and convex. The radial function \(\varphi(x)=\psi(\|x\|)\) is convex: for \(0\leq\lambda\leq1\), the triangle inequality and monotonicity give \(\varphi(\lambda x+(1-\lambda)y)\leq\psi(\lambda\|x\|+(1-\lambda)\|y\|)\), and convexity of \(\psi\) bounds this by \(\lambda\varphi(x)+(1-\lambda)\varphi(y)\). For \(x\ne0\),

\nabla\varphi(x)=\psi'(\|x\|)\frac{x}{\|x\|} =h(\|x\|)\frac{x}{\|x\|}=T(x).

Also \(h(r)\to0\) as \(r\to0\), so this gradient extends continuously at zero with value \(0\). Thus \(T\) is the gradient of a convex function and pushes the source to \(U_2\). Brenier’s theorem identifies it as the quadratic optimal transport map, unique almost everywhere.

Worked Example: The One-Dimensional Center-Outward Map

Suppose \(X\) has the exponential distribution with rate \(1\), supported on \(x\geq0\). The uniform distribution on the one-dimensional unit ball \([-1,1]\) has cumulative distribution function \((u+1)/2\) on that interval. The increasing transport equates this with \(F(x)=1-e^{-x}\), giving

T(x)=2F(x)-1=1-2e^{-x},\qquad x\geq0.

For \(-1\leq u<1\), the map is increasing and

P(T(X)\leq u) =P\left(X\leq-\log\left(\frac{u+1}{2}\right)\right) =1-\frac{u+1}{2} =\frac{u+1}{2}.

Therefore \(T(X)\) is uniform on \([-1,1]\). In one dimension \(T\) is the derivative of a convex function on the source support: \(T'(x)=2e^{-x}>0\), so an antiderivative has increasing derivative and is convex. The rank is \(|T(x)|\), and the sign is \(+1\) or \(-1\) according to which side of the target center \(T(x)\) lies on. This example also shows why a center-outward sign need not match the sign of the original observation relative to zero: the source center is determined by the transport, not by treating zero as a universal location estimate.

The Distribution-Free Property

The transformation depends on \(F\), but its distribution after transformation does not. This distinction is the basis for using center-outward ranks and signs in distribution-free procedures.

Theorem: If \(X\sim F\) satisfies the conditions in the definition and \(F_{\pm}\) is its center-outward distribution function, then \(F_{\pm}(X)\sim U_d\). Consequently, for \(0\leq r\leq1\), \(P(R_{\pm}(X)\leq r)=r^d\). For \(d\geq2\), the sign is uniform on the unit sphere and independent of the rank. In dimension \(1\), the sign is equally likely to be \(-1\) or \(+1\) and is independent of the rank.

The first assertion follows from the defining pushforward property. For the remaining claims, write a uniform point in the ball in polar coordinates as \(U=QS\), with \(Q=\|U\|\) and \(S=U/\|U\|\) when \(U\ne0\). The volume element in polar coordinates is proportional to \(q^{d-1}\,dq\) times surface area measure. Thus the uniform-ball probability of a radial interval and a direction set factors into a radial term and a normalized surface-area term. In particular, for \(0\leq r\leq1\),

P(Q\leq r) =\frac{\operatorname{Vol}(rB_d)}{\operatorname{Vol}(B_d)} =r^d.

The factorization proves that \(Q\) and \(S\) are independent and that \(S\) is uniform with respect to normalized surface area. When \(d=1\), the two directions are the endpoints \(-1\) and \(+1\), each with probability \(1/2\), independently of the absolute value. Since \(F_{\pm}(X)\sim U_d\), these are exactly the rank and sign claims for the transformed observation. \(\square\)

Worked Example: Checking Rank Probabilities Without Knowing the Source Distribution

Suppose \(X\) has any absolutely continuous distribution on \(\mathbb{R}^3\) with finite second moment, and use its center-outward map. The probability that its rank is at most \(1/2\) is

P(R_{\pm}(X)\leq 1/2)=(1/2)^3=\frac18.

The probability that the rank lies between \(1/2\) and \(1\) is therefore \(1-1/8=7/8\). Conditional on a rank in either region, the sign has the same uniform spherical distribution. These calculations do not require specifying whether the original \(X\) is normal, skewed, or heavy-tailed; the conditions on \(F\) are what matter.

For an independent sample \(X_1,\ldots,X_n\) from \(F\), applying the population map separately gives independent transformed observations \(F_{\pm}(X_i)\), each uniform on the ball. This is an exact distribution-free statement about the transformed sample under the specified common distribution. It does not say that the unknown map can be evaluated without estimating or otherwise knowing \(F\). Finite-sample implementations instead use an empirical transport to a fixed grid.

Finite-Sample Ranks by Optimal Assignment

Choose a deterministic reference grid \(G_n=\{g_1,\ldots,g_n\}\) in the unit ball. A useful grid has points distributed approximately uniformly over the ball and may be arranged to include antipodal pairs; depending on \(n\), a design may also include a point at the center. The empirical center-outward assignment pairs the observed points with the grid points to minimize total squared Euclidean distance.

Definition: Given observations \(x_1,\ldots,x_n\) and distinct grid points \(g_1,\ldots,g_n\), an optimal assignment is a permutation \(\pi\) minimizing \(\sum_{i=1}^n\|x_i-g_{\pi(i)}\|^2\) over all permutations of \(\{1,\ldots,n\}\). The assigned point \(\hat F_{\pm}^{(n)}(x_i)=g_{\pi(i)}\) gives the empirical rank \(\|g_{\pi(i)}\|\) and empirical sign \(g_{\pi(i)}/\|g_{\pi(i)}\|\), with sign \(0\) for a grid point at the center.

Worked Example: A Four-Point Assignment in the Plane

Consider the four observations \(x_1=(2,0)\), \(x_2=(0,1)\), \(x_3=(-1,0)\), and \(x_4=(0,-2)\), together with the toy grid \(g_1=(1/2,0)\), \(g_2=(0,1/2)\), \(g_3=(-1/2,0)\), and \(g_4=(0,-1/2)\). This small grid illustrates the assignment calculation; it is not intended to be a high-quality approximation to the uniform ball.

Because \(\sum_i\|x_i-g_{\pi(i)}\|^2=\sum_i\|x_i\|^2+\sum_j\|g_j\|^2-2\sum_i x_i\cdot g_{\pi(i)}\), minimizing cost is equivalent to maximizing the sum of inner products. Pairing each observation with the grid point in its direction gives inner products \(1,1/2,1/2,1\), with total \(3\). Any grid point in a different axial direction gives inner product \(0\) or a negative value for that observation, so this direction-matching assignment is optimal. Its total squared cost is

$$ (2-1/2)^2+(1-1/2)^2+(-1+1/2)^2+(-2+1/2)^2 =2.25+0.25+0.25+2.25=5. $$

Each observation receives empirical rank \(1/2\). Their empirical signs are, respectively, \((1,0)\), \((0,1)\), \((-1,0)\), and \((0,-1)\). In an application, a larger grid spread throughout the ball gives a finer range of ranks; the assignment principle is unchanged.

Under independent sampling from a continuous common distribution, the empirical assignment has a useful distribution-free feature. Conditional on the unordered set of observations, every labeling of those observations is equally likely. If the optimal assignment is unique, relabeling the observations simply relabels their assigned grid points. Therefore the allocation of the fixed grid points to the sample labels is a uniform random permutation, conditional on the unordered sample. With distinct grid points and absolutely continuous observations, assignment ties occur with probability zero: the cost difference between two distinct assignments is a nonzero linear function of the observations, whose zero set has probability zero. A permutation-equivariant tie rule can be used if ties nevertheless arise in a particular data set.

Important distinction: The population transformed observations are exactly independent and uniform on the ball under the stated model. A finite-sample assignment instead uses a chosen grid that approximates that reference distribution. Its distribution-free feature is the random allocation of grid points to observation labels under an iid continuous model; the grid itself is not an exact continuous uniform distribution.

Why the Construction Matters—and a Common Pitfall

Center-outward ranks and signs provide a multivariate ordering that respects the geometry of the full reference space, rather than imposing a coordinate-by-coordinate ordering. Their distribution-free population law makes them useful ingredients for procedures whose null behavior should not depend on the shape of a continuous multivariate distribution. The finite assignment also gives a concrete computational construction: a linear assignment problem can be solved using standard optimization algorithms.

A common mistake is to verify only that a proposed map has the correct pushforward distribution and then call it the quadratic optimal transport. The radial exponential example shows why that is insufficient: the pushforward calculation establishes the target law, but optimality also requires the appropriate transport structure. Here that structure was verified by exhibiting a convex potential whose gradient is the map, after which Brenier’s theorem applies. Another mistake is to treat finite-grid ranks as exact draws from the continuous uniform ball. They are points on a fixed grid, and their finite-sample calibration must be interpreted accordingly.

Check Your Understanding

Try to answer each question using the definitions and derivations above.

What assumptions on \(F\) support the stated quadratic optimal transport map, and why is absolute continuity relevant?
For a uniform point in the unit ball in dimension \(d\), derive the probability that its distance from the origin is at most \(r\), where \(0\leq r\leq1\).
Why does verifying that a map pushes \(F\) to the uniform ball not, by itself, establish that it is the quadratic optimal transport map?
In a finite-sample construction, why does minimizing total squared distance give the same assignment as maximizing the sum of observation-grid inner products?
Explain the distinction between the population distribution-free property and the finite-sample grid-allocation property.