Three Faces of Leverage Scores
12 min read
Statisticians, numerical linear algebraists, and spectral graph theorists each attach a number to every row of a matrix. It took me embarrassingly long to notice it is the same number. Statisticians call it leverage, read it off the diagonal of the hat matrix, and use it to flag the observation that is steering a regression on its own; the classic reference is Hoaglin & Welsch [HW, TAS ’78]. Numerical linear algebraists use it as the importance weight that lets a few sampled rows stand in for many, a line of work opened by Drineas, Mahoney & Muthukrishnan [DMM, SODA ’06]. And on the incidence matrix of a graph it is the effective resistance of an edge, the quantity Spielman & Srivastava [SS, STOC ’08] sample by to sparsify graphs. None of the three definitions makes the other two look like the same quantity. They are, and the reason also fixes the right rate at which to sample a row.
One Number per Row
Start in one dimension, where the number 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. The general definition keeps this shape. 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 two facts we checked by hand survive in general. First, \(\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\). Second, the scores 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\). What a large share means is where the three fields part ways.
Face One: Self-Influence
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}\]
The hat matrix puts the hat on \(\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}\), some description of it should never mention \(\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 asks whether the other rows can build it for less. 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\) gets no help and keeps \(\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 . \]
Its energy collapses the same middle factors once more, landing on 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. Any feasible \(\mathbf{w}\) has \(\mathbf{A}^\top(\mathbf{w} - \mathbf{w}^*) = \mathbf{0}\), so \(\mathbf{w} - \mathbf{w}^*\) is 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 . \]
So far energy is only a name for \(\sum_j w_j^2\). On the matrix a graph hands you, it is dissipated power.
Face Three: Effective Resistance
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}\).
Face two specializes just as cleanly. 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.
The global facts specialize too. That the scores sum to the rank says 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. And leverage one picks out the bridges. 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
Three descriptions are not yet a reason to compute anything. All three fields compute the number because leverage is the right rate at which to sample rows. 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 is easy; concentration is the hard part. Uniform \(p_i = 1/n\) can lose it outright. 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 rather than \(\varepsilon\). (The needle’s leverage is \(1\); do you see why no other row can help build it?)
The whitening trick shows why leverage is the right rate for every matrix, needle or not. 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 size of its rank-one share of the spectrum, and the shares total \(d\). That fixes the sampling weights. Dividing by a term’s own share evens the terms out, and the shares sum to \(d\), so dividing by \(d\) makes a distribution:
\[ 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 importance sampling has flattened the sum: no term can dominate. 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. Every singular value of \(\mathbf{A}\), and every least-squares problem posed with it, survives on a sketch whose size never mentions \(n\). (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] is this theorem on 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 every eigenvalue) survives to \(1 \pm \varepsilon\). The needle is the bridge: uniform edge sampling on the barbell misses it and disconnects the sparsifier, while resistance sampling keeps it with high probability.
Three Fields, One Number
The number turns up in tools that do not cite each other: regression packages print it beside the residual, and randomized least-squares solvers sample rows by it to solve a small problem in place of a large one. 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]).
Three fields kept reinventing the same importance weight. When a sum of terms has a total fixed in advance, each term’s share of that total is the rate to sample it at.