🤖 machine learning

Structural Correspondence and Universal Approximation in Diagonal plus Low-Rank Neural Networks

This paper resolves the theoretical limitations of purely low-rank neural networks by introducing a Diagonal plus Low-Rank (DLoR) structure that, through minimal sparse diagonal augmentation, restores universal approximation capabilities and demonstrates that dense matrices are not prerequisites for general expressivity.

Original authors: Ying Chen, Aoxi Li, Jihun Kim, Javad Lavaei

Published 2026-05-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ying Chen, Aoxi Li, Jihun Kim, Javad Lavaei

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build a machine that can learn to draw any picture you can imagine. In the world of Artificial Intelligence, this machine is a Neural Network. Usually, to make sure the machine can draw anything perfectly, we give it a massive, heavy toolbox full of dense, complex tools (called "dense matrices"). But these heavy tools are expensive to carry around; they take up a lot of memory and require a lot of energy to use.

To save energy, scientists started using Low-Rank tools. Think of these as "folded" or "compressed" tools. They are much lighter and easier to carry. The popular method LoRA (Low-Rank Adaptation) is like taking a heavy backpack and folding it down to fit in your pocket. It works great for fine-tuning, but the paper asks a scary question: If we fold our tools too much, do we lose the ability to draw anything new?

Here is the story of what the paper discovered, explained simply.

1. The Trap of the "One-Dimensional" View

The authors first tested what happens if a neural network is strictly low-rank (specifically, rank-1). Imagine a camera that can only take photos through a very thin, single slit.

The Good News: If you only need to draw a single line (a 1D problem), this slit works perfectly. The paper proves that a strictly rank-1 network can memorize any list of single numbers perfectly.
The Bad News (The Paradox): As soon as you ask the network to draw a 2D shape (like a circle) or a 3D object, it fails completely. The authors call this "Orthogonal Blindness."

The Analogy: Imagine you are trying to describe a complex 3D sculpture to someone who can only see the world through a single vertical crack in a wall.

If the sculpture moves up and down, the person sees it.
But if the sculpture moves left or right (perpendicular to the crack), the person sees nothing.
Because the network only "sees" through this one narrow crack, it is completely blind to any changes happening sideways. It cannot learn the full shape of the world.

2. The Magic Fix: The "Diagonal" Key

The paper asks: Can we fix this blindness without making the tools heavy again?

They found a brilliant, tiny solution. They added just one extra thing to the low-rank tool: a Diagonal component.

The Structure: They call this DLoR (Diagonal plus Low-Rank).
The Metaphor: Imagine the low-rank tool is a pair of sunglasses that only let light in through a vertical slit. The "Diagonal" part is like adding a tiny, transparent mirror right in the center of the slit.
The Result: This tiny mirror (which only requires storing one number, the "alpha") allows light to bounce off and fill in the gaps. Suddenly, the sunglasses can see left, right, up, and down. The "blindness" is cured.

The paper proves that adding this tiny, sparse diagonal piece is enough to restore the network's ability to approximate any function, no matter how complex. It's like adding a single key to a locked door that opens the entire universe.

3. Two Ways to Build the Machine

The paper shows you can use these "Diagonal + Low-Rank" tools in two different ways to build a perfect machine, trading off between Width (how wide the machine is) and Depth (how many layers it has).

Option A: The Wide Machine (Additive Decomposition)
- How it works: Instead of one heavy tool, you use many small, folded tools side-by-side and add their results together.
- The Catch: You need a lot of parallel tools (width) to do the job. It's like having 100 people standing in a line, each holding a small piece of a puzzle, and you have to combine all their pieces at once.
- Bonus: The math shows this method is very stable and doesn't mess up the "bias" (the starting point) of the network.
Option B: The Deep Machine (Multiplicative Decomposition)
- How it works: Instead of standing side-by-side, you stack the tools one on top of another. The output of the first tool becomes the input for the second, and so on.
- The Catch: You need many layers (depth).
- The Winner: The paper argues this is the better way. Just like how folding a piece of paper many times makes it exponentially thicker, stacking these layers allows the network to become incredibly powerful with very few parameters. It's more efficient than making the machine wider.

4. The Big Conclusion

The main takeaway is a relief for anyone worried about making AI smaller and faster:

Purely low-rank networks are blind: If you strip away everything but the low-rank parts, the network loses its ability to learn complex shapes.
You don't need heavy tools: You don't need to go back to using massive, dense matrices to fix this.
The "Tiny Mirror" is enough: By adding a tiny, sparse diagonal component (the DLoR structure), you can keep the network lightweight and efficient while regaining its full power to learn anything.

In short, the paper proves that you don't need a giant, heavy backpack to carry the world. You just need a smart, folded map with one tiny, special key, and you can go anywhere.

Technical Summary: Structural Correspondence and Universal Approximation in Diagonal plus Low-Rank Neural Networks

1. Problem Statement

The scaling of modern deep learning architectures to billions of parameters has necessitated the adoption of parameter-efficient structures, such as Low-Rank Adaptation (LoRA) and low-rank factorization. While these methods reduce computational overhead by operating on constrained low-rank manifolds, their theoretical expressive power remains under-explored. Existing theoretical guarantees often rely on restrictive priors, such as a pretrained dense base matrix, specific activation functions (e.g., ReLU, Swish), or non-verifiable singularity conditions.

The central problem addressed is whether strictly constrained neural networks can achieve the Universal Approximation Theorem (UAT) without these restrictive assumptions. Specifically, the paper investigates the limits of purely low-rank architectures (e.g., rank-1 layers) and identifies a fundamental geometric bottleneck: Orthogonal Blindness. While purely rank-1 networks can exactly interpolate scalar datasets, they fail catastrophically when approximating multi-dimensional continuous functions because they are invariant to variations orthogonal to their projection vector.

2. Methodology

The authors propose a unified Structural Correspondence Framework to overcome the limitations of pure low-rank structures while maintaining parameter efficiency. The core methodology involves:

2.1 The DLoR Component

The paper introduces the Diagonal plus Low-Rank (DLoR) matrix structure, defined as:
$M = \alpha I_N + UV^T$
where $\alpha I_N$ is a sparse diagonal component (scaled identity) and $UV^T$ is a low-rank matrix of rank $r \ll N$ . This structure requires only $O(1)$ additional parameters (the scalar $\alpha$ ) compared to a pure low-rank matrix but provides a vital residual pathway to capture the orthogonal spectrum, thereby breaking the geometric bottleneck of orthogonal blindness.

2.2 Structural Correspondence

The framework establishes a mathematical correspondence between full-rank dense transformations and DLoR components through two decomposition strategies:

Additive Decomposition (Width Expansion): A high-rank weight matrix $W$ is decomposed into a sum of DLoR components ( $W = \sum M_l$ ). In a neural network, this linear addition is mapped through non-linear activation functions to create a parallel ensemble of layers, effectively expanding the network's width.
Multiplicative Decomposition (Depth Extension): A high-rank weight matrix $W$ is decomposed into a product of DLoR components ( $W = \prod M_l$ ). This corresponds to extending the network's depth, where sequential DLoR layers reconstruct the dense transformation while strictly preserving the original width.

2.3 Theoretical Proofs

The authors utilize asymptotic Taylor remainders and properties of non-affine continuous activation functions to prove that:

Purely rank-1 networks suffer from Orthogonal Blindness, making them incapable of spanning higher-dimensional spaces for function approximation.
DLoR networks, via additive or multiplicative decomposition, can exactly reconstruct any full-rank transformation in the limit of specific scaling parameters ( $h \to 0$ ).
Deep DLoR networks restore the UAT for general continuous activation functions, provided the network width is bounded (specifically $N = n + m + 2$ ).

3. Key Contributions

The paper presents the following specific contributions:

Formalization of Orthogonal Blindness: The authors prove that while purely rank-1 neural networks can interpolate arbitrary scalar targets, they fundamentally collapse for multi-dimensional function approximation due to their inability to capture variations orthogonal to the projection vector.
The Structural Correspondence Framework: A theoretical framework demonstrating that rank deficiency can be compensated for by either expanding network width (additive decomposition) or extending network depth (multiplicative decomposition) using DLoR components.
Universal Approximation via DLoR: Proof that introducing a minimal $O(1)$ sparse diagonal to form a DLoR structure is sufficient to restore the Universal Approximation Theorem for general continuous activation functions, without requiring a dense prior or specific activation types.
Parameter Complexity Analysis: The paper establishes that Deep DLoR networks inherit the optimal parameter complexity of standard dense architectures for approximating functions in Sobolev spaces ( $O(\epsilon^{-d/s} \log(1/\epsilon))$ ), proving that extreme low-rank constraints do not degrade fundamental information-theoretic capabilities.
Superiority of Depth over Width: Theoretical analysis indicates that multiplicative depth provides a superior parameter-to-expressivity scaling compared to additive width expansion, aligning with classical results on the exponential benefits of depth.

4. Results

Theoretical Results

Scalar vs. Multi-dimensional Targets: The paper demonstrates a paradox where rank-1 networks achieve zero error on scalar targets but fail to approximate multi-dimensional targets with $k \ge 2$ points in general position.
Existence of DLoR Approximation: Theorems 3 and 4 prove that any dense, full-rank matrix can be exactly reconstructed using DLoR components via additive (width) or multiplicative (depth) decomposition.
Restoration of UAT: Theorems 5 and 6 confirm that Deep and Wide DLoR networks are dense in the space of continuous functions $C(K, \mathbb{R}^m)$ . Theorem 7 extends this to show that any existing UAT guarantee for a dense network can be transferred to a DLoR network.
Parameter Efficiency: Theorem 8 confirms that DLoR networks match the parameter complexity bounds of dense networks for smooth functions, adhering to optimal approximation limits.

Numerical Experiments

The authors conducted experiments to validate the theoretical constructions and compare deep (multiplicative) vs. wide (additive) DLoR architectures:

UAT Validation: Experiments on a sawtooth function showed that both deep and wide DLoR structures converge to the approximation error of a dense MLP as the scaling parameter $h \to 0$ .
Training Performance: Under fixed optimization budgets (5,000 and 50,000 epochs), the deep structured model consistently achieved lower test errors and reached target accuracy thresholds ( $10^{-3}$ ) faster and with higher success rates than the wide structured model.
Spectral Decomposition: Analysis of trained models revealed that deep DLoR layers learn a distribution where the low-rank component captures dominant singular directions while the identity component preserves a broad background spectrum. In contrast, wide networks distribute representation across parallel branches in a less spectrally separated manner.

5. Significance and Claims

The paper claims to provide the fundamental mathematical justification for combining low-rank factors with sparse diagonal components (as seen in empirical frameworks like SLTrain and ResLoRA). Its significance lies in:

Rigorous Justification for PEFT: It moves beyond empirical observation to prove that a minimal sparse diagonal is a strict mathematical prerequisite for restoring universal expressivity in low-rank architectures, eliminating the need for a frozen dense base matrix.
Topological Prerequisites: The results demonstrate that dense matrices and specific activation functions are not topological prerequisites for universal expressivity; rather, the ability to capture orthogonal variations via a sparse residual pathway is the critical factor.
Architectural Blueprint: The Structural Correspondence framework offers a theoretical basis for designing next-generation parameter-efficient pretraining and fine-tuning methods, suggesting that extreme rank-deficient bottlenecks (e.g., rank-1) can achieve full expressivity if augmented correctly.
Decoupled Optimization: The framework suggests that dense parameter spaces can be effectively decoupled into independent low-rank manifolds (via depth or width expansion), enabling massive parallelization in distributed hardware without sacrificing theoretical expressivity guarantees.

The authors remain modest regarding the asymptotic nature of their proofs (relying on $h \to 0$ ), noting that in practice, DLoR components may leverage the full non-linear manifold to discover robust representations without strictly adhering to the limiting constructions, while still achieving the proven approximation bounds.