Three Faces of Leverage Scores
12 min read
Suppose we want to replace a large least squares problem with a much smaller sample of its rows. Some observations contribute information that is easy to find elsewhere; others constrain a direction that few other rows tell us about. Sampling should give those harder-to-replace rows more attention.
A row’s leverage score measures how strongly its observation influences its own fitted value [HW, TAS ’78]. It is also the smallest sum of squared coefficients needed to express that row as a combination of all the rows. On a graph, the same quantity becomes an edge’s effective resistance [SS, STOC ’08]. It took me embarrassingly long to notice it is the same number. These interpretations explain why sampling in proportion to leverage can preserve a least squares problem using far fewer rows [DMM, SODA ’06].
One Number per Row
What is the number in one dimension, where it can be computed by hand? With \(d = 1\) the matrix is a single column of numbers \(a_1, \dots, a_n\), and the number we attach to row \(i\) is its share of the total squared mass:
\[ \tau_i = \frac{a_i^2}{\sum_{j=1}^{n} a_j^2} . \]
Ten identical rows split the mass ten ways, a share of \(1/10\) each. A row holding all the mass takes share \(1\). Every share sits in \([0, 1]\), and the shares sum to \(1\) no matter how many rows there are. For several columns, the denominator becomes the Gram matrix of all rows. Fix \(\mathbf{A} \in \mathbb{R}^{n \times d}\) with \(n \ge d\), full column rank, and rows \(\mathbf{a}_1^\top, \dots, \mathbf{a}_n^\top\), each \(\mathbf{a}_i \in \mathbb{R}^d\). The leverage score of row \(i\) is a quadratic form in that row:
\[ \tau_i = \mathbf{a}_i^\top (\mathbf{A}^\top\mathbf{A})^{-1}\, \mathbf{a}_i . \]
The inverse Gram matrix in the middle is the denominator from before: with \(d = 1\) it is the scalar \(1/\sum_j a_j^2\), and the display collapses back to the share. The score is also the \(i\)-th diagonal entry of the hat matrix \(\mathbf{H} = \mathbf{A}(\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{A}^\top \in \mathbb{R}^{n \times n}\). (When \(\mathbf{A}\) is rank-deficient the inverse becomes a pseudoinverse, which we need for graphs.)
The hat matrix \(\mathbf{H}\) is a projection. Multiply it by itself and the middle factors \((\mathbf{A}^\top\mathbf{A})^{-1}(\mathbf{A}^\top\mathbf{A})\) collapse to the identity:
\[\begin{align} \mathbf{H}^2 &= \mathbf{A}(\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{A}^\top\mathbf{A}(\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{A}^\top \\ &= \mathbf{A}(\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{A}^\top \\ &= \mathbf{H}. \end{align}\]
It is also symmetric, \(\mathbf{H}^\top = \mathbf{H}\), so it is the orthogonal projection onto the column space of \(\mathbf{A}\). Idempotence and symmetry together give \(\mathbf{H} = \mathbf{H}^\top\mathbf{H}\), which lets us read a diagonal entry as a squared row norm and bound it below by its own square:
\[\begin{align} \tau_i = [\mathbf{H}]_{i,i} &= [\mathbf{H}^\top\mathbf{H}]_{i,i} \\ &= \sum_{j} [\mathbf{H}]_{i,j}^2 \\ &\ge [\mathbf{H}]_{i,i}^2 = \tau_i^2. \end{align}\]
A number no smaller than its own square lies in \([0, 1]\), so \(0 \le \tau_i \le 1\). The leverage scores also sum to the rank. The trace is cyclic, so rotate the outer \(\mathbf{A}\) to the back and cancel it against the inverse:
\[\begin{align} \sum_{i=1}^{n} \tau_i &= \mathrm{tr}(\mathbf{H}) \\ &= \mathrm{tr}\big(\mathbf{A}(\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{A}^\top\big) \\ &= \mathrm{tr}\big((\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{A}^\top\mathbf{A}\big) \\ &= \mathrm{tr}(\mathbf{I}_d) \\ &= d. \end{align}\]
However many rows there are, the total leverage is fixed at \(d\), so each score is a share of a budget that never grows with \(n\). The three faces are three readings of this share, and sampling row \(i\) at rate \(\tau_i / d\) is what keeps any one reweighted row from dominating a sampled sum.
Face One: Self-Influence
Why do statisticians call this number leverage? The definition mentions only \(\mathbf{A}\), never the data. Attach responses \(\mathbf{y} \in \mathbb{R}^n\) and fit least squares, minimizing \(\|\mathbf{y} - \mathbf{A}\boldsymbol{\beta}\|_2\) over coefficients \(\boldsymbol{\beta} \in \mathbb{R}^d\). Setting the gradient to zero gives the normal equations:
\[ \mathbf{A}^\top\mathbf{A}\,\boldsymbol{\beta} = \mathbf{A}^\top\mathbf{y}. \]
Substitute the solution back into the fitted values and the hat matrix appears:
\[\begin{align} \hat{\mathbf{y}} &= \mathbf{A}\boldsymbol{\beta} \\ &= \mathbf{A}(\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{A}^\top\mathbf{y} \\ &= \mathbf{H}\mathbf{y}. \end{align}\]
This fitted-value operation gives \(\mathbf{H}\) its name: it maps \(\mathbf{y}\) to \(\hat{\mathbf{y}}\). Reading off the \(i\)-th coordinate, the leverage score is a partial derivative:
\[ \tau_i = [\mathbf{H}]_{i,i} = \frac{\partial \hat{y}_i}{\partial y_i}. \]
It is the fraction of a nudge to observation \(i\) that reappears in its own fitted value: self-influence, which is why statisticians say leverage. Notice it is still a property of \(\mathbf{A}\) alone: moving \(y_i\) does not budge \(\tau_i\).
Take the extreme \(\tau_i = 1\). The identity \(\mathbf{H} = \mathbf{H}^\top\mathbf{H}\) turns the diagonal entry into a squared length, with \(\mathbf{e}_i \in \mathbb{R}^n\) the \(i\)-th standard basis vector:
\[ \tau_i = \mathbf{e}_i^\top \mathbf{H}\mathbf{e}_i = \|\mathbf{H}\mathbf{e}_i\|_2^2 . \]
A projection preserves length only by preserving the vector, so \(\tau_i = 1\) makes \(\mathbf{e}_i\) a fixed point:
\[ \mathbf{H}\mathbf{e}_i = \mathbf{e}_i . \]
Push that through the fitted value, moving \(\mathbf{H}\) onto \(\mathbf{e}_i\) by symmetry:
\[\begin{align} \hat{y}_i &= \mathbf{e}_i^\top \mathbf{H}\mathbf{y} \\ &= (\mathbf{H}\mathbf{e}_i)^\top \mathbf{y} \\ &= \mathbf{e}_i^\top \mathbf{y} \\ &= y_i . \end{align}\]
The fit reproduces observation \(i\) exactly, for every \(\mathbf{y}\), however absurd it is.
In the plot, the teal point steers the line from the far right: delete it and the fit swings from the solid line to the dashed one, though its residual is small. The amber point does the opposite, carrying the largest residual on the plot while barely moving the fit. Leverage is about being alone in a direction of \(\mathbf{A}\), and only the residual looks at the responses at all.
Face Two: Minimum Energy
If leverage never looks at \(\mathbf{y}\), is there a description of it that never mentions \(\mathbf{y}\) either?
Claim: the leverage score is the least energy needed to build row \(i\) out of all the rows:
\[ \tau_i = \min\big\{ \|\mathbf{w}\|_2^2 \;:\; \mathbf{w} \in \mathbb{R}^n,\ \mathbf{A}^\top\mathbf{w} = \mathbf{a}_i \big\}. \]
Write out the constraint one row at a time:
\[ \mathbf{A}^\top\mathbf{w} = \sum_{j=1}^{n} w_j\, \mathbf{a}_j = \mathbf{a}_i . \]
A feasible \(\mathbf{w}\) writes row \(i\) as a linear combination of all the rows, and \(\|\mathbf{w}\|_2^2 = \sum_j w_j^2\) is the energy of that combination. One feasible choice is \(\mathbf{w} = \mathbf{e}_i\): row \(i\) builds itself at energy \(1\), so \(\tau_i \le 1\) falls out again. The minimum is small when the other rows can reconstruct \(\mathbf{a}_i\) with coefficients of low squared norm. Ten parallel copies of one row split the coefficient ten ways for total energy \(10 \cdot (1/10)^2 = 1/10\), the picture of a redundant row. A row holding the only mass in some direction of \(\mathbb{R}^d\) cannot be reconstructed by the others and has \(\tau_i = 1\).
Proof
Consider the candidate \(\mathbf{w}^* = \mathbf{A}(\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{a}_i\), the \(i\)-th column of the hat matrix \(\mathbf{H}\mathbf{e}_i\). It is feasible, since the leading \(\mathbf{A}^\top\mathbf{A}\) cancels the inverse:
\[ \mathbf{A}^\top\mathbf{w}^* = (\mathbf{A}^\top\mathbf{A})(\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{a}_i = \mathbf{a}_i . \]
Cancelling the same middle factors makes its energy equal the leverage score:
\[\begin{align} \|\mathbf{w}^*\|_2^2 &= \mathbf{a}_i^\top(\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{A}^\top\mathbf{A}(\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{a}_i \\ &= \mathbf{a}_i^\top(\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{a}_i \\ &= \tau_i . \end{align}\]
It is also optimal. For any feasible \(\mathbf{w}\), the difference satisfies \(\mathbf{A}^\top(\mathbf{w} - \mathbf{w}^*) = \mathbf{0}\) and is therefore orthogonal to the column space of \(\mathbf{A}\), while \(\mathbf{w}^*\) lies inside it. Pythagoras then splits the energy:
\[ \|\mathbf{w}\|_2^2 = \|\mathbf{w}^*\|_2^2 + \|\mathbf{w} - \mathbf{w}^*\|_2^2 \ge \|\mathbf{w}^*\|_2^2 = \tau_i . \]
For a graph incidence matrix, \(\sum_j w_j^2\) is the electrical power dissipated by a unit-resistance network.
Face Three: Effective Resistance
What does the number become on the incidence matrix of a graph? Take a connected graph with \(d\) vertices and edge set \(E\) of size \(n\), orient each edge arbitrarily, and let the row of \(\mathbf{B} \in \mathbb{R}^{n \times d}\) for edge \((u, v)\) be \(\mathbf{e}_u - \mathbf{e}_v\), the difference of the endpoints’ indicator vectors in \(\mathbb{R}^d\). Multiplying out, the Gram matrix is the graph Laplacian \(\mathbf{L} \in \mathbb{R}^{d \times d}\):
\[ \mathbf{B}^\top\mathbf{B} = \mathbf{L}, \]
with degrees on the diagonal and \(-1\) in entry \((u, v)\) for each edge. Every row of \(\mathbf{B}\) sums to zero, so the all-ones vector spans the kernel, the rank is \(d - 1\), and the pseudoinverse \(\mathbf{L}^+\) steps in.
Make every edge a one-ohm resistor, push one ampere in at \(u\), and pull it out at \(v\). Collect the vertex potentials in \(\mathbf{p} \in \mathbb{R}^d\). Ohm’s law makes an edge’s current equal the potential drop across it, so the net current leaving vertex \(z\) sums those drops over its neighbors \(z'\):
\[ \sum_{z'} (p_z - p_{z'}) = [\mathbf{L}\mathbf{p}]_z . \]
Conservation makes that net current \(+1\) at \(u\), \(-1\) at \(v\), and zero elsewhere, a linear system in \(\mathbf{p}\):
\[ \mathbf{L}\mathbf{p} = \mathbf{e}_u - \mathbf{e}_v, \qquad \text{solved by} \quad \mathbf{p} = \mathbf{L}^+(\mathbf{e}_u - \mathbf{e}_v) . \]
The effective resistance between \(u\) and \(v\) is the voltage this experiment requires, the potential gap \(p_u - p_v\):
\[ p_u - p_v = (\mathbf{e}_u - \mathbf{e}_v)^\top \mathbf{L}^+ (\mathbf{e}_u - \mathbf{e}_v) . \]
That is the definition of \(\tau_i\) with \(\mathbf{e}_u - \mathbf{e}_v\) as the row: the effective resistance of an edge is its leverage score in \(\mathbf{B}\).
A coefficient vector \(\mathbf{w}\) with one entry per edge is a flow, and the constraint \(\mathbf{B}^\top\mathbf{w} = \mathbf{e}_u - \mathbf{e}_v\) says one unit of flow enters at \(u\), exits at \(v\), and is conserved at every other vertex. The energy \(\sum_e w_e^2\) is the power the flow dissipates in the resistors, so face two becomes Thomson’s principle: the electrical flow is the cheapest unit flow, and its energy is the effective resistance.
Since the incidence matrix has rank \(d-1\), the effective resistances of the edges of any connected graph sum to \(d - 1\):
\[ \sum_{(u,v) \in E} \tau_{(u,v)} = d - 1 , \]
which is Foster’s theorem (1949), already proved by the trace computation above. An edge has leverage one exactly when it is a bridge. If deleting edge \((u,v)\) disconnects the graph, every unit flow pushes the whole unit across that edge, so its energy is at least \(1\); an edge on a cycle sends a fraction around the detour and comes in under \(1\).
In the diagram, thickness tracks resistance: the clique’s edges have many alternate routes, while the bridge has none and carries the whole unit.
The Sampling Theorem
Why is a share of a fixed budget the right probability at which to sample a row? All three fields compute leverage because it is, and the reason is that sampling by it flattens every reweighted term to the same size. Write the Gram matrix in the outer-product view, one rank-one term per row:
\[ \mathbf{A}^\top\mathbf{A} = \sum_{i=1}^{n} \mathbf{a}_i \mathbf{a}_i^\top . \]
Keeping a random subset of rows is Monte Carlo on this sum. Draw \(m\) indices independently, taking index \(i\) with probability \(p_i\), and stack the sampled rows scaled by \(1/\sqrt{m\,p_i}\) into \(\tilde{\mathbf{A}} \in \mathbb{R}^{m \times d}\). The scaling undoes the sampling bias: a single draw contributes \(\mathbf{a}_i\mathbf{a}_i^\top / (m p_i)\) with probability \(p_i\), and averaging over which index is drawn returns the whole sum, scaled by \(1/m\):
\[\begin{align} \mathbb{E}\Big[\tfrac{\mathbf{a}_i\mathbf{a}_i^\top}{m p_i}\Big] &= \sum_{j=1}^{n} p_j \cdot \frac{\mathbf{a}_j\mathbf{a}_j^\top}{m p_j} \\ &= \frac{1}{m}\sum_{j=1}^{n} \mathbf{a}_j\mathbf{a}_j^\top \\ &= \frac{1}{m}\,\mathbf{A}^\top\mathbf{A} . \end{align}\]
Summed over the \(m\) draws, \(\tilde{\mathbf{A}}^\top\tilde{\mathbf{A}}\) is unbiased for \(\mathbf{A}^\top\mathbf{A}\) at any positive \(p\).
Unbiasedness does not ensure concentration, and uniform probabilities \(p_i = 1/n\) can produce a singular sampled Gram matrix. If one direction of the column space lives in a single row (picture \(n - 1\) generic rows supported on the first \(d - 1\) coordinates, plus one needle \(\mathbf{e}_d^\top\)), uniform sampling needs \(m = \Omega(n)\) draws to see the needle once. Until it does, the sampled Gram matrix is singular in that direction: a relative error of one, when the target is a small relative error \(\varepsilon\). (The needle’s leverage is \(1\); do you see why no other row can help build it?)
Whitening shows why leverage is the right sampling probability for every matrix. Full column rank makes \(\mathbf{A}^\top\mathbf{A}\) positive definite, with an orthonormal eigenbasis \(\mathbf{v}_1, \dots, \mathbf{v}_d \in \mathbb{R}^d\) and positive eigenvalues \(\lambda_1, \dots, \lambda_d\), so halving the exponents defines its inverse square root:
\[ \mathbf{A}^\top\mathbf{A} = \sum_{k=1}^{d} \lambda_k\, \mathbf{v}_k \mathbf{v}_k^\top, \qquad (\mathbf{A}^\top\mathbf{A})^{-1/2} = \sum_{k=1}^{d} \lambda_k^{-1/2}\, \mathbf{v}_k \mathbf{v}_k^\top . \]
Conjugating by it replaces each row by its whitened version:
\[ \tilde{\mathbf{a}}_i = (\mathbf{A}^\top\mathbf{A})^{-1/2}\,\mathbf{a}_i . \]
Whitening turns the target into \(\mathbf{I}_d\), so “preserve the spectrum” becomes “keep every eigenvalue of the sampled sum near \(1\)”. The whitened term \(\tilde{\mathbf{a}}_i\tilde{\mathbf{a}}_i^\top\) has spectral norm equal to the squared whitened length, exactly the leverage score:
\[ \|\tilde{\mathbf{a}}_i\|_2^2 = \mathbf{a}_i^\top(\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{a}_i = \tau_i . \]
A row’s leverage is the spectral norm of its whitened rank-one term, and the leverage scores total \(d\). This defines the sampling probabilities:
\[ p_i = \frac{\tau_i}{d} . \]
Whichever row is drawn, the scaled term has spectral norm exactly \(d\):
\[ \Big\|\,\frac{\tilde{\mathbf{a}}_i\tilde{\mathbf{a}}_i^\top}{p_i}\,\Big\| = \frac{\tau_i}{p_i} = d , \]
so no sampled term can dominate the sum. A matrix Chernoff bound (Tropp [Tropp, FoCM ’12]) turns that flatness into a two-sided guarantee from \(m = O(d \log d / \varepsilon^2)\) draws, with high probability:
\[ (1 - \varepsilon)\, \mathbf{A}^\top\mathbf{A} \;\preceq\; \tilde{\mathbf{A}}^\top\tilde{\mathbf{A}} \;\preceq\; (1 + \varepsilon)\, \mathbf{A}^\top\mathbf{A}, \]
where \(\preceq\) compares quadratic forms direction by direction. Thus every singular value of \(\mathbf{A}\) is preserved to relative error \(\varepsilon\) by a sketch whose size does not depend on \(n\); the same guarantee applies to every least-squares objective posed with \(\mathbf{A}\). (The \(\log d\) is not slack: on the identity matrix every row has leverage \(1\), so leverage sampling is uniform and collecting all \(d\) rows is coupon collecting.)
Computing \(\tau_i\) exactly needs \((\mathbf{A}^\top\mathbf{A})^{-1}\), about as expensive as the problem the sketch was meant to shrink. Constant-factor approximations are enough, at a constant factor in \(m\), and they need no inverse.
Spielman & Srivastava [SS, STOC ’08] apply this theorem to graphs: sample \(O(d \log d / \varepsilon^2)\) edges of a \(d\)-vertex graph with probability proportional to effective resistance, and the Laplacian, hence every cut and eigenvalue, is preserved to \(1 \pm \varepsilon\). On the barbell graph, uniform sampling can miss the high-resistance bridge and disconnect the sparsifier, while resistance sampling keeps it with high probability.
Applications
Where does the number show up in practice? Regression packages print leverage beside the residual, while randomized least-squares solvers use it to sample a smaller problem. Leverage-score sampling of coalitions is also the engine inside LeverageSHAP, which turns the KernelSHAP regression into a Shapley value estimator with provable guarantees (Musco & Witter [MW, ICLR ’25]).
Across regression, electrical networks, and randomized linear algebra, leverage measures a row or edge’s share of a fixed total. Sampling in proportion to that share prevents any reweighted term from dominating.