The Effective Rank of a Matrix

矩阵的有效秩（Effective Rank） 苏剑林 · 2025-04-10 · Mathematics matrix entropy sparse low-rank

Rank is one of the fundamental concepts in linear algebra, representing the intrinsic dimensionality of a matrix. However, the strict mathematical definition of rank often doesn't quite fit numerical computation scenarios, because rank equals the number of nonzero singular values, and the mathematical notion of "equal to zero" differs from how it's treated in numerical computation. In mathematics, "equal to zero" means exactly, strictly zero—even something as small as $10^{-100}$ is still nonzero. But numerical computation is different: very often $10^{-10}$ can reasonably be treated as zero.

This is why we want to generalize the concept of rank into a form that better fits the characteristics of numerical computation, which is where the notion of Effective Rank comes from.

Error Truncation

It should be noted that there is currently no unified definition of effective rank in the academic literature. What follows are several ideas for defining effective rank from different angles. For practical problems, readers are free to pick whichever definition suits their needs. more

Let's start by considering rank from the perspective of singular values. For a matrix $\boldsymbol{M}\in\mathbb{R}^{n\times m}$, without loss of generality let $n\leq m$, so its standard rank is

\begin{equation}\mathop{\text{rank}}(\boldsymbol{M}) \triangleq \max\{i\,|\,\sigma_i > 0\}\leq n\end{equation}

where $\sigma_1\geq \sigma_2\geq \cdots\geq\sigma_n \geq 0$ are the singular values of $\boldsymbol{M}$. Intuitively, the idea of effective rank is to treat singular values that are close to zero as if they were zero, so a basic property that effective rank should satisfy is that it does not exceed the standard rank, while reducing to the standard rank in special cases. A simple definition satisfying this property is

\begin{equation}\mathop{\text{erank}}(\boldsymbol{M},\epsilon) \triangleq \max\{i\,|\,\sigma_i > \epsilon\}\end{equation}

However, the notions of "large" and "small" should be relative: 1 is large relative to 0.01, but small relative to 100. So it seems more principled to normalize by dividing by $\sigma_1$:

\begin{equation}\mathop{\text{erank}}(\boldsymbol{M},\epsilon) \triangleq \max\big\{i\,\big|\,\sigma_i/\sigma_1 > \epsilon\big\}\end{equation}

Besides directly truncating singular values that are close to zero, we can also approach this problem from the angle of low-rank approximation. In The Road to Low-Rank Approximation (Part 2): SVD] we showed that the optimal rank-$r$ approximation of a matrix is exactly the SVD result obtained by keeping only the largest $r$ singular values. Conversely, we can specify a relative error tolerance $\epsilon$ and define the effective rank as the smallest rank that achieves this relative error:

\begin{equation}\mathop{\text{erank}}(\boldsymbol{M},\epsilon) \triangleq \min\left\{ i\,\,\left|\,\,\sqrt{\left(\sum_{i=1}^r \sigma_i^2\right)\left/\left(\sum_{i=1}^n \sigma_i^2\right.\right)} \geq 1-\epsilon\right.\right\}\end{equation}

This definition has a clearer numerical meaning, but since it only considers the overall error, some examples turn out less elegant. For instance, for a $n\times n$ identity matrix, we would expect its effective rank to always be $n$, since every singular value is equally 1, and there should be no truncation at all. But under the above definition, once $n$ is large enough ($1/n < \epsilon$), the effective rank ends up being smaller than $n$.

Ratio of Norms

Although the effective rank defined in the previous section is intuitive, it depends on a hyperparameter $\epsilon$ in every case, which is ultimately not clean enough. Our basic premise now is that the notion of effective rank should depend only on relative magnitudes, so the problem becomes: how do we construct an effective rank purely from $1\geq \sigma_2/\sigma_1\geq\cdots\geq\sigma_n/\sigma_1\geq 0$? Since these all lie within $[0,1]$, one clever idea is to simply sum them up:

\begin{equation}\mathop{\text{erank}}(\boldsymbol{M}) \triangleq \sum_{i=1}^n\frac{\sigma_i}{\sigma_1}\end{equation}

From The Road to Low-Rank Approximation (Part 2): SVD] we know that the largest singular value $\sigma_1$ is the spectral norm] of the matrix, denoted $\Vert\boldsymbol{M}\Vert_2$, while the sum of all singular values is itself a matrix norm, called the "nuclear norm]", usually denoted $\Vert\boldsymbol{M}\Vert_*$. So the expression above can be written more compactly as

\begin{equation}\mathop{\text{erank}}(\boldsymbol{M}) \triangleq \frac{\Vert\boldsymbol{M}\Vert_*}{\Vert\boldsymbol{M}\Vert_2}\label{eq:n-2}\end{equation}

The earliest source for this is probably An Introduction to Matrix Concentration Inequalities], where it is called "Intrinsic Dimension", though the related properties had already been explored in Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization].

Similarly, we can construct an effective rank via a sum of squares:

\begin{equation}\mathop{\text{erank}}(\boldsymbol{M}) \triangleq \sum_{i=1}^n\frac{\sigma_i^2}{\sigma_1^2} = \frac{\Vert\boldsymbol{M}\Vert_F^2}{\Vert\boldsymbol{M}\Vert_2^2}\label{eq:f-2}\end{equation}

Here $\Vert\cdot\Vert_F$ is the $F$ norm. This definition seems to originate from Sampling from large matrices: an approach through geometric functional analysis], where it was called "Numerical Rank"; nowadays it's more commonly known as "Stable Rank", and is one of the more popular notions of effective rank.

In terms of computational cost, equation $\eqref{eq:f-2}$ is cheaper than equation $\eqref{eq:n-2}$. Computing the nuclear norm requires the full set of singular values, meaning a complete SVD is needed; whereas $\Vert\boldsymbol{M}\Vert_F^2$ is simply equal to the sum of squares of all matrix entries, so the main computational cost in equation $\eqref{eq:f-2}$ is just the largest singular value, which is much cheaper than computing all singular values. If we like, we can also generalize equations $\eqref{eq:n-2}$ and $\eqref{eq:f-2}$ to a sum of $k$-th powers, and the result turns out to be the more general ratio between the Schatten norm] and the spectral norm.

Distributions and Entropy

If a reader searches directly for "Effective Rank," they will most likely come across the paper The Effective Rank: a Measure of Effective Dimensionality], one of the earlier works exploring effective rank, which proposes an entropy-based definition.

First, since singular values are always non-negative, we can normalize them into a probability distribution:

\begin{equation}p_i = \frac{\sigma_i^{\gamma}}{\sum_{j=1}^n \sigma_j^{\gamma}}\end{equation}

where $\gamma > 0$. Looking at the literature, both $\gamma=1$ and $\gamma=2$ are commonly used (we used $\gamma=2$ in Moonlight]); below we'll use $\gamma=1$ as our example. With a probability distribution in hand, we can compute the Shannon entropy:

\begin{equation}H = -\sum_{i=1}^n p_i \log p_i\end{equation}

Recall that the range of entropy is $[0, \log n]$, so after exponentiating we get $e^H \in [1, n]$. When the distribution is one-hot, $e^H=1$ (only one nonzero singular value); when the distribution is uniform, $e^H=n$ (all singular values equal)—these are exactly the two special cases of standard rank, which suggests we can define effective rank as

\begin{equation}\mathop{\text{erank}}(\boldsymbol{M}) \triangleq e^H = \exp\left(-\sum_{i=1}^n p_i \log p_i\right)\label{eq:h-erank}\end{equation}

Substituting the definition of $p_i$, we find this can be further rewritten as

\begin{equation}\mathop{\text{erank}}(\boldsymbol{M}) = \exp\left(\log\sum_{i=1}^n \sigma_i -\frac{\sum_{i=1}^n \sigma_i\log\sigma_i}{\sum_{i=1}^n \sigma_i}\right)\end{equation}

It's clear that the first term inside the brackets, after $\exp$, is just $\Vert\boldsymbol{M}\Vert_*$; the second term is a weighted average of $\log\sigma_i$ with weights $\sigma_i$, in which case $\log\sigma_i$ will be approximately equal to the largest $\log\sigma_1$, and after exponentiating this gives $\sigma_1=\Vert\boldsymbol{M}\Vert_2$. So overall the expression will approximate equation $\eqref{eq:n-2}$, which shows that although defining effective rank via entropy looks like a completely different path, it actually shares the same spirit as the norm ratio approach from the previous section.

We know that standard rank satisfies the triangle inequality $\mathop{\text{rank}}(\boldsymbol{A}+\boldsymbol{B})\leq \mathop{\text{rank}}(\boldsymbol{A}) + \mathop{\text{rank}}(\boldsymbol{B})$, and the original paper proved that for (semi-)positive definite symmetric matrices $\boldsymbol{A},\boldsymbol{B}$, the effective rank defined by equation $\eqref{eq:h-erank}$ satisfies $\mathop{\text{erank}}(\boldsymbol{A}+\boldsymbol{B})\leq \mathop{\text{erank}}(\boldsymbol{A}) + \mathop{\text{erank}}(\boldsymbol{B})$. It is not yet clear whether this inequality can be extended to general matrices. It seems that proving whether effective rank preserves certain inequalities of standard rank is not an easy task.

Sparsity Metrics

From this series of definitions of effective rank—especially the progression from singular values, to a distribution, to entropy—readers have probably already sensed that effective rank shares an obvious kinship with sparsity. In fact, effective rank can be understood as a sparsity measure of the vector of singular values. The difference from ordinary sparsity metrics is that we align its range to $1\leq \mathop{\text{erank}}(\boldsymbol{M}) \leq \mathop{\text{rank}}(\boldsymbol{M}) \leq n$, matching it to the notion of rank, which makes the degree of sparsity more intuitively perceptible.

We discussed sparsity metrics fairly systematically before, in How Do We Measure the Sparsity of Data?], and in principle the results there can all be used to construct effective rank. In fact, that's exactly what we did: in the "Ratio of Norms]" section, we built an effective rank from the ratio of the Schatten norm to the spectral norm, which corresponds exactly to formula $(1)$ from that earlier post. We could also use another formula, such as $(16)$, which amounts to defining effective rank as the square of the ratio between the nuclear norm and the $F$ norm:

\begin{equation}\mathop{\text{erank}}(\boldsymbol{M}) \triangleq \frac{\Vert\boldsymbol{M}\Vert_*^2}{\Vert\boldsymbol{M}\Vert_F^2} = \frac{(\sum_{i=1}^n\sigma_i)^2}{\sum_{i=1}^n\sigma_i^2}\end{equation}

This likewise satisfies $1\leq \mathop{\text{erank}}(\boldsymbol{M}) \leq \mathop{\text{rank}}(\boldsymbol{M})$, and is a usable definition of effective rank.

It's remarkable how our understanding of effective rank and sparsity has, quite unexpectedly, come full circle. It really is a lovely experience: when I first started learning about sparsity metrics, I knew nothing about effective rank; and these past few days, while studying effective rank, I gradually came to realize that it is fundamentally connected to sparsity. There seems to be some mysterious force at work, quietly stitching together the knowledge we've accumulated across different fields and disciplines, until it all converges on the same, correct direction.

Summary

This post explored the concept of the effective rank of a matrix—an extension, tailored to numerical computation, of the classical notion of matrix rank from linear algebra—which allows for a more effective measurement of a matrix's intrinsic dimensionality.