cs.LGNov 13, 2026

Pattern-Based Matrix Analysis Under Permutations

Authors: Andrei Ermakov

Organizations: NL

Abstract

Low-rank approximation captures one important notion of matrix simplicity: a matrix is simple if it is well described by a low-dimensional linear model. This paper studies a complementary notion. We consider matrices that become structurally simple only after permuting rows and columns, so that their mass concentrates in a prescribed geometric pattern such as a band, block-diagonal, arrowhead, or related form. We introduce a pattern distance that measures how close a matrix is to a given pattern after optimal reordering, giving a common framework for structural problems such as latent ordering, community detection, and bandwidth minimization. The problem is NP-hard in general; we derive an alternating algorithm based on Linear Assignment subproblems. We further introduce a pattern-plus-low-rank decomposition that combines permutation-structured fitting with a low-rank residual, whose permutation step is pattern fitting on the residual; its gains across pattern families persist at a matched parameter budget and are substantially reduced under a density-matched random-mask control. We evaluate the framework on synthetic recovery tasks, real correlation and graph adjacency matrices, and transformer attention heads, showing that a single universal algorithm recovers qualitatively different forms of matrix structure.

Figures & tables

Appendix figures & tables33 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time

    Feb 21, 2023Yuzhou Gu, Zhao Song, Junze Yin +1Alternating MinimizationMatrix Completion

  2. Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure

    Aug 21, 2026Lawrence K. Saul, Ningyuan Huang, Dennis Bollweg +2Low-Rank Matrix DecompositionMatrix Completion