Volume Sampling Keeps Leverage and Rejects Redundancy
7 min read
Suppose a matrix has many rows, and we want to keep a small set that preserves its full column rank. We can do this with as many rows as columns, but scoring the rows one at a time is not enough. Two rows can each look important and still point in the same direction, so independent draws may spend two places on one piece of information.
Volume sampling chooses sets of this size with probability proportional to their squared volume [DR, FOCS ’10]. A set with redundant rows has zero volume and is never chosen. At the same time, each row’s chance of inclusion is exactly its leverage score, the familiar measure of its individual importance. The determinant gives us both properties: useful individual rows are included often, and every selected set retains the full rank.
Area Chooses the Pair
What does the area of a pair see that the length of each row does not? Start with five rows in two dimensions:
\[ \mathbf{a}_1 = (2,0),\quad \mathbf{a}_2 = (2,0),\quad \mathbf{a}_3 = (0,1),\quad \mathbf{a}_4 = (0,1),\quad \mathbf{a}_5 = (1,1). \]
Rows 1 and 2 are long, but they are copies. If we keep both, their parallelogram has area zero. Pairing either one with row 3 gives area two, while pairing rows 3 and 5 gives area one.
The plot shows what a row-by-row score misses. Length can favor rows 1 and 2 separately, while area sees that the second copy adds no new direction.
Now write the five rows as a matrix \(\mathbf{A} \in \mathbb{R}^{5 \times 2}\). For a pair \(S\), let \(\mathbf{A}_S \in \mathbb{R}^{2 \times 2}\) contain its two rows. The absolute determinant is the area of their parallelogram, so the squared area is:
\[ \det(\mathbf{A}_S)^2. \]
There are six pairs with squared area four, two with squared area one, and two parallel pairs with squared area zero. Their total weight is therefore:
\[ 6 \cdot 4 + 2 \cdot 1 = 26. \]
The same number appears without listing the pairs. The Gram matrix and its determinant are:
\[ \mathbf{A}^\top\mathbf{A} = \begin{pmatrix} 9 & 1 \\ 1 & 3 \end{pmatrix}, \qquad \det(\mathbf{A}^\top\mathbf{A}) = 26. \]
That agreement is the Cauchy–Binet formula. For any full-column-rank matrix \(\mathbf{A} \in \mathbb{R}^{n \times d}\), with \([n]\) the set of row indices, it says:
\[ \sum_{S \subseteq [n]:\, |S|=d} \det(\mathbf{A}_S)^2 = \det(\mathbf{A}^\top\mathbf{A}). \]
The left side expands the determinant of the Gram matrix over every choice of \(d\) rows. Each term is nonnegative because it is squared, and full column rank makes their sum positive. We can therefore define basis volume sampling by dividing each term by that sum:
\[ \Pr(S) = \frac{\det(\mathbf{A}_S)^2}{\det(\mathbf{A}^\top\mathbf{A})}, \qquad |S|=d. \]
A dependent set has probability zero. More generally, the determinant is the product of the rows’ successive perpendicular lengths, so a row contributes only the part that lies outside the span of the rows already selected. The other two properties, the leverage marginals and the repulsion between aligned rows, both come from reading coefficients off this same Cauchy–Binet sum.
Row Scaling Gives the Marginals
How often does any single row appear in a volume-sampled set? Exactly as often as its leverage score says, where the leverage score of row \(i\) is:
\[ \tau_i = \mathbf{a}_i^\top(\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{a}_i. \]
Claim: under volume sampling, each row is included with probability equal to its leverage score:
\[ \Pr(i \in S) = \tau_i. \]
Proof
Scale row \(i\) by \(\sqrt{t}\) and call the resulting matrix \(\mathbf{A}(t)\). In the Cauchy–Binet sum, every set containing \(i\) acquires one factor of \(t\), while every other set is unchanged:
\[\begin{align} \det(\mathbf{A}(t)^\top\mathbf{A}(t)) &= \sum_{S:\,i\notin S} \det(\mathbf{A}_S)^2 + t \sum_{S:\,i\in S} \det(\mathbf{A}_S)^2. \end{align}\]
Thus the coefficient of \(t\) is the total unnormalized weight of sets containing row \(i\). Scaling one row changes the Gram matrix by one rank-one term:
\[ \mathbf{A}(t)^\top\mathbf{A}(t) = \mathbf{A}^\top\mathbf{A} + (t-1)\mathbf{a}_i\mathbf{a}_i^\top. \]
The matrix determinant lemma evaluates the same determinant:
\[\begin{align} \det(\mathbf{A}(t)^\top\mathbf{A}(t)) &= \det(\mathbf{A}^\top\mathbf{A}) \left[1+(t-1)\mathbf{a}_i^\top (\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{a}_i\right] \\ &= \det(\mathbf{A}^\top\mathbf{A})[1+(t-1)\tau_i] \\ &= \det(\mathbf{A}^\top\mathbf{A})[(1-\tau_i)+t\tau_i]. \end{align}\]
The first line applies the rank-one determinant formula, the second uses the definition of leverage, and the third collects the constant and linear terms in \(t\). Comparing the coefficient of \(t\) in the two expressions gives:
\[ \sum_{S:\,i\in S} \det(\mathbf{A}_S)^2 = \det(\mathbf{A}^\top\mathbf{A})\tau_i. \]
Dividing by the Cauchy–Binet normalizer proves the claim.
For the five-row example, the inverse Gram matrix is:
\[ (\mathbf{A}^\top\mathbf{A})^{-1} = \frac{1}{26} \begin{pmatrix} 3 & -1 \\ -1 & 9 \end{pmatrix}. \]
Substitution gives all five leverage scores:
\[ (\tau_1,\tau_2,\tau_3,\tau_4,\tau_5) = \left(\frac{6}{13},\frac{6}{13},\frac{9}{26},\frac{9}{26},\frac{5}{13}\right). \]
We can check row 1 directly from the pair weights. It belongs to three nonzero pairs, each with weight four, so its inclusion probability is:
\[ \Pr(1 \in S) = \frac{12}{26} = \frac{6}{13}. \]
The joint distribution has preserved exactly the row importance described on the leverage-scores page.
The Joint Distribution Subtracts Alignment
The marginals say how often each row appears, but how often do two rows appear together? For that, define the hat matrix:
\[ \mathbf{H} = \mathbf{A}(\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{A}^\top \in \mathbb{R}^{n \times n}. \]
Its diagonal contains the leverage scores, while its off-diagonal entry compares rows \(i\) and \(j\) after the geometry has been whitened:
\[ [\mathbf{H}]_{i,j} = \mathbf{a}_i^\top(\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{a}_j. \]
Claim: for distinct rows \(i\) and \(j\), the joint inclusion probability is:
\[ \Pr(i\in S,\;j\in S) = \tau_i\tau_j-[\mathbf{H}]_{i,j}^2. \]
Proof
Scale rows \(i\) and \(j\) by \(\sqrt{s}\) and \(\sqrt{t}\), and call the resulting matrix \(\mathbf{A}(s,t)\). Cauchy–Binet makes the coefficient of \(st\) equal to the total weight of sets containing both rows. The rank-two determinant lemma reduces the normalized determinant to:
\[ \det \begin{pmatrix} 1+(s-1)\tau_i & (t-1)[\mathbf{H}]_{i,j} \\ (s-1)[\mathbf{H}]_{i,j} & 1+(t-1)\tau_j \end{pmatrix}, \]
which expands as:
\[\begin{align} \frac{\det(\mathbf{A}(s,t)^\top\mathbf{A}(s,t))} {\det(\mathbf{A}^\top\mathbf{A})} &= [1+(s-1)\tau_i][1+(t-1)\tau_j] -(s-1)(t-1)[\mathbf{H}]_{i,j}^2 \\ &= 1+(s-1)\tau_i+(t-1)\tau_j \\ &\quad +(s-1)(t-1) \left(\tau_i\tau_j-[\mathbf{H}]_{i,j}^2\right). \end{align}\]
The first line evaluates the \(2 \times 2\) determinant, and the second collects the term involving both scaling parameters. The coefficient of \(st\) is therefore the joint inclusion probability, which proves the claim.
This is the pairwise marginal formula for the projection determinantal point process described by Kulesza & Taskar [KT, FnT ML ’12]. It also gives the covariance of the two inclusion indicators:
\[ \mathrm{Cov}(\mathbf{1}[i\in S],\mathbf{1}[j\in S]) = -[\mathbf{H}]_{i,j}^2. \]
The subtracted square measures alignment after whitening. It is zero for orthogonal whitened rows, and it reaches \(\tau_i\tau_j\) for parallel ones. In the latter case the joint probability is zero.
Because the leverage scores sum to \(d\), independent leverage sampling chooses row \(i\) with probability \(\tau_i/d\) on each of \(d\) draws. Row \(i\) still has expected multiplicity \(\tau_i\), but duplicate and parallel draws remain possible. Volume sampling returns \(d\) distinct rows and assigns zero probability to every dependent set.
In the figure, an unordered volume-sampled pair is put in random order so it can be compared with two independent draws. Each position has the same marginal \(\tau_i/2\) under both distributions, so the expected multiplicity across two positions is \(\tau_i\). The independent distribution spends mass on the diagonal and on the parallel pairs \((1,2)\) and \((3,4)\), while volume sampling moves that mass to pairs that span the plane.
Spanning Trees Are Volume-Sampled Bases
Is there a matrix on which volume sampling turns out to be a distribution we already know? Take a connected graph on \(v\) vertices, orient every edge arbitrarily, and form the signed vertex-by-edge incidence matrix \(\mathbf{B}\). Delete one vertex row and transpose the result, giving \(\mathbf{A}=\widetilde{\mathbf{B}}^\top\) with one row per edge and \(v-1\) columns. A sample of \(v-1\) edge rows has determinant \(\pm 1\) when the edges form a spanning tree, and determinant zero otherwise.
Volume sampling on this matrix is therefore uniform over spanning trees. Cauchy–Binet says its normalizer is the number of spanning trees, exactly the counting identity proved by the matrix-tree theorem. When every edge has unit conductance, the marginal probability that an edge belongs to the tree is its leverage score, which is also its effective resistance.
The same distribution selects actual rows for low-rank approximation [DR, FOCS ’10], and Dereziński & Warmuth use it to fit linear regression from a small set of observed responses while preserving unbiasedness [DW, NeurIPS ’17].