# Factor Fitting, Rank Allocation, and Partitioning in Multilevel Low Rank Matrices

arXiv: https://arxiv.org/abs/2310.19214 · HTML: https://mlsanity.com/paper/2310.19214/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 104 references that are in the map.
- First posted on arXiv 30 Oct 2023.

## Builds on (most cited first, 8 of 8)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks](https://mlsanity.com/paper/1611.01890/) (2016)
- [Monarch: Expressive Structured Matrices for Efficient and Accurate Training](https://mlsanity.com/paper/2204.00595/) (2022)
- [Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations](https://mlsanity.com/paper/1903.05895/) (2019)
- [Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models](https://mlsanity.com/paper/2112.00029/) (2021)
- [Generalized Low Rank Models](https://mlsanity.com/paper/1410.0342/) (2014)
- [Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps](https://mlsanity.com/paper/2012.14966/) (2020)
- [Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation](https://mlsanity.com/paper/1510.07363/) (2015)

## Built on by (most cited first, 2 of 2)

- [Fitting Multilevel Factor Models](https://mlsanity.com/paper/2409.12067/) (2024)
- [Customizing the Inductive Biases of Softmax Attention using Structured Matrices](https://mlsanity.com/paper/2509.07963/) (2025)

## Abstract (arXiv)

We consider multilevel low rank (MLR) matrices, defined as a row and column permutation of a sum of matrices, each one a block diagonal refinement of the previous one, with all blocks low rank given in factored form. MLR matrices extend low rank matrices but share many of their properties, such as the total storage required and complexity of matrix-vector multiplication. We address three problems that arise in fitting a given matrix by an MLR matrix in the Frobenius norm. The first problem is factor fitting, where we adjust the factors of the MLR matrix. The second is rank allocation, where we choose the ranks of the blocks in each level, subject to the total rank having a given value, which preserves the total storage needed for the MLR matrix. The final problem is to choose the hierarchical partition of rows and columns, along with the ranks and factors. This paper is accompanied by an open source package that implements the proposed methods.