Why So Many Matrices Are of Low Rank

• categories: Linear algebra, Observation

1. Communication Efficiency

Low-rank matrices are common because they allow for a more compact representation and updates:

• Exact Representation: For a matrix $A\in {\mathbb{R}}^{n\times n}$ of rank $k$, it can be expressed as $A=U{V}^T$, where $U\in {\mathbb{R}}^{n\times k}$ and $V\in {\mathbb{R}}^{n\times k}$. The storage cost is $2kn$ compared to $n^2$ for a general matrix when $k\ll n$.
• Efficient Communication: This compact representation makes it efficient to send or store data for applications like distributed computing or compressed sensing.

2. Intuition from Symmetries

Many matrices in real-world problems exhibit inherent horizontal and vertical symmetries, leading to a lower effective rank:

• Horizontal Symmetry: Rows of the matrix are linearly dependent or nearly dependent.
• Vertical Symmetry: Columns exhibit similar relationships.

For example, covariance matrices often capture dependencies between features, and the intrinsic dimensionality (rank) is much smaller than the number of features.

3. Smoothness of the World

• Sampling of Polynomials: A key observation is that sampling from a polynomial function of degree $k$ leads to a low-rank structure. For example, if $f(x)$ is a polynomial of degree $k$, the matrix of evaluations at points $\{x_1,\dots ,x_n\}$ will have rank $\le k+1$.
• Smooth Functions: Smooth functions can often be well-approximated by polynomials (e.g., via Taylor series or Fourier expansions). This leads to a low numerical rank even if the exact rank is not low.

Exception: The Hilbert Matrix

The Hilbert matrix $H_{ij}=\frac{1}{i+j-1}$ is a famous example where the numerical rank is much smaller than the matrix size. For example, for $n=1000$, the numerical rank of the Hilbert matrix is approximately $28$. The low numerical rank here arises due to smoothness properties but also the presence of separable structures and decay in the singular values.

4. Sylvester Equation and Zolotarev Bounds

A deeper reason for low-rank structure in many matrices comes from their connection to the Sylvester equation:

$$AX-XB=C,$$

where $A$ and $B$ are matrices, and $C$ is often low-rank or has specific structure.

Key Observation:

If $X$ satisfies the Sylvester equation, its rank is often low or can be bounded. This happens frequently in physics, control theory, and PDEs, where dynamics or spatial interactions are modeled by such equations.

Zolotarev Bound:

If the eigenvalues of $A$ and $B$ are well-separated (sets $E$ and $F$ of eigenvalues are disjoint), then the singular values of $X$ decay rapidly. This leads to a small effective rank for $X$. The Zolotarev bound provides a quantitative measure of this decay.

---

Why the World Is Sylvester

1. Physical Systems:
   Many dynamical systems and equilibrium problems can be expressed in terms of Sylvester or Lyapunov equations. For example:

   • Heat diffusion.
   • Wave propagation.
   • Feedback control.

2. PDE Discretizations:
   When discretizing partial differential equations, the resulting algebraic systems often have Sylvester-like forms.

3. Separation in Eigenvalues:
   In natural systems, eigenvalue distributions are often structured (e.g., separated clusters), making Sylvester equations lead to matrices with rapid decay in singular values.

Conclusion

The prevalence of low-rank matrices arises from:

• Symmetries and smoothness in real-world phenomena.
• Compact communication and representation needs.
• Deep connections to Sylvester equations and eigenvalue separation, explained rigorously by bounds like Zolotarev’s.