CS Paper Radar

Pattern-Based Matrix Analysis Under Permutations

Andrei Ermakov

cs.LG ·submitted 2026-11-13 02:39 UTC · v1
top venue

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.

Comment
Accepted at NeurIPS 2026 (The Fortieth Annual Conference on Neural Information Processing Systems)

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.LG stat.ML ·2026-08-21 ·Lawrence K. Saul, Ningyuan Huang, Dennis Bollweg, Jeff Soules, Diana C. Halikias
similarity 0.63
Abstract

We investigate when a sparse nonnegative matrix can be recovered from a real-valued matrix of much lower rank by zeroing out its negative elements. The potential for such decompositions suggests a mathematical connection between sparsity and rank; we analyze a number of sparse matrices with this latent low-rank structure and use them to illustrate the geometric origins of this connection. Previous algorithms have discovered these decompositions via an alternating minimization over the factors of a low-rank matrix, but to do so, they have also needed to compute and store another matrix, neither sparse nor low-rank, that is the size of their product. We develop a stochastic, alternating least-squares algorithm that operates on smaller blocks of this dense matrix and scales as a result to much larger problems. We also show how to further accelerate this algorithm with sparse optimizations and customized CUDA kernels. As one example, we use the algorithm to analyze the sparse matrix of synaptic weights for the recently published $\textit{Drosphilia}$ connectome. The nonzero elements of this matrix, with 139,255 rows and columns, record the number of synapses between cells in the nervous system of a female fruit fly. Despite a slowly decaying spectrum of singular values, this matrix exhibits a latent low-rank structure that is predictive of cell categories across multiple levels of specificity.

0.38

A Sparse Low-Rank Biclique Decomposition for Graphs

cs.LG ·2026-11-19 ·Antoine Vialle, Sergei Gerasimov, Aref Einizade, Antonio Ortega, Fragkiskos D. Malliaros +1 more
top venuecode/data similarity 0.62
Abstract · Accepted at NeurIPS 2026. 29 pages, including references and appendices

Low-rank plus sparse decompositions, such as robust PCA, typically model the low-rank component as dense and the sparse component as corruption. This viewpoint is poorly suited to graph adjacency matrices, where sparsity is structural and dense low-rank factors destroy the combinatorial and computational properties of the graph. We propose signed biclique decomposition (SBD), a sparse low-rank decomposition for integer-weighted graphs that represents the structured component as a sum of sparse signed binary rank-one factors, together with a sparse signed residual. The resulting representation remains discrete, interpretable, sparse, and compatible with standard linear algebra. We formulate fixed-rank and greedy SBD objectives and derive a gain-based greedy algorithm with theoretical guarantees. Empirically, SBD recovers block structure in noisy graphs, while its factorized representation enables efficient sparse matrix-matrix multiplication (SpMM). On real graphs with strong shared-neighborhood structure, SBD achieves compression factors above $10$ and SpMM speedups up to $6\times$ over cuSPARSE, suggesting a practical alternative to dense low-rank decompositions for graphs. Code is available at https://github.com/IAntoineV/sbd.

0.50

Exact minimum Birkhoff decompositions of doubly stochastic matrices with finite precision

cs.DS ·2026-10-19 ·András Czégel
similarity 0.61
Abstract · Submission document to QOBLIB

The minimum Birkhoff decomposition problem asks for a representation of a doubly stochastic matrix as a convex combination of as few permutation matrices as possible. This NP-hard problem arises in the scheduling of switches in data centers and satellite systems, in random assignments in economics and in the statistics of rankings. We consider doubly stochastic matrices whose entries are given with a fixed number of decimal digits and look for exact decompositions whose weights have the same precision. We propose a parallel method with three parts. For matrices built from few permutation matrices, the first part reads the weights from the frequencies of the entries and places them on the matrix positions by a rule that, given the correct weights, never fixes a position wrongly. The second part computes lower bounds from pairs of rows or columns, which remain valid for real weights, and from certificates of a satisfiability solver. For matrices built from many permutation matrices, the third part runs a beam search over steps that each make at least one entry zero. On 375 test instances with up to 100 rows, the method proves optimality for 208 instances, and 197 of these proofs also hold for real weights. Of the 190 instances built from few permutation matrices, 187 are solved to proven optimality, 180 of them within one second. Compared with the best exact decompositions known before, the new decompositions are shorter for 278 instances and never longer.

0.25

The Quick and the Dead: Estimating Sparse-Matrix Permanents with Adaptive Work Filtering

cs.DS ·2026-08-15 ·Deniz Elbek, Yiğit Manafi, Zeynep Gürdal, Sinan Yıldırım, Kamer Kaya
similarity 0.60
Abstract

Rasmussen's permanent estimator is a simple and unbiased estimator for the permanent of a binary matrix, but its practical performance can be limited by trajectories that terminate before completing a perfect matching. These failed trajectories, together with dispersion among the surviving weights, can substantially reduce the effective sample size. Although the literature leverages techniques such as matrix scaling to improve proposal balance and support filtering to remove structurally infeasible choices, using these at every step can substantially increase the trajectory cost. Furthermore, they do not directly address the choice of the next vertex. This paper uses the classical minimum-degree ordering in sparse matrix algorithms to select the next vertex with O(n + m) total bucket-maintenance work per trajectory, where n is the number of rows/columns in the matrix and m is the number of nonzeros. The proposed estimator uses adaptive schedules to invoke the more expensive scaling and filtering operations only when needed. The experiments show that it is competitive with the state of the art on the tested small matrices and scales effectively to large sparse matrices.

0.04

D-SLR: The Disjoint Row-Sparse plus Low-Rank Decomposition

cs.LG stat.MEstat.ML ·2026-10-07 ·Vincent Szolnoky
theory similarity 0.58
Abstract

Compressing a matrix for reconstruction still defaults to the truncated SVD, approximating the data with a single low-rank structure. It is common to reduce the residual further by adding an overlapping row-sparse component, but methods that solve this joint problem often require iterative solvers and tuning of regularization parameters. We propose the Disjoint Row-Sparse plus Low-Rank (D-SLR) decomposition, a closed-form drop-in for the truncated SVD that improves or exactly matches it. D-SLR restricts rows to either being stored verbatim or approximated by the low-rank fit, never both. Under squared error this restriction costs nothing: the joint optimum is attainable disjointly with fewer parameters at every non-trivial rank and stored row count (shape). With zero stored rows D-SLR reduces to the truncated SVD, so it never does worse at equal cost. The algorithm scores the entire error-versus-parameters tradeoff, and the solution is chosen afterwards by a supplied error target or parameter count, or by a selection rule. The grid and solution together cost three SVDs, with no tuning or regularization. We derive an assumption-free, a-posteriori lower bound on the error at every shape, giving each solution a computable certificate on the potential gain of any other choice of rank and stored rows. Experiments on synthetic and real data (LLM embedding tables, network traffic, hyperspectral images) confirm the gains and quantify the certificate.

0.20

MHeatmap: Two-Walk Laplacian Reordering and Mosaic Layout for Rectangular Matrix Visualization

cs.LG cs.HC ·2026-10-21 ·Juntang Wang, Sheng'en Li, Liming Zhu, Yihan Wang, Siyuan Cao +4 more
theoryunusual similarity 0.57
Abstract · 10 pages, 3 figures, 1 table

Weighted rectangular matrices record relations between two types of objects, such as occupations and industries, documents and terms, origins and destinations, or annotated classes and computed clusters. Their heatmaps become difficult to read when arbitrary row and column orders scatter related objects, while equal size cells hide large differences in row and column totals. We present MHeatmap (Mosaic Heatmap), which addresses these problems in two stages. Two-Walk spectral seriation first represents the matrix as a weighted bipartite graph. Ordinary bipartite ordering uses only observed row to column links. Two-Walk also uses length-two walks, so rows that share columns and columns that share rows receive explicit similarity links. Sorting a Fiedler vector of the resulting graph Laplacian gives coordinated row and column orders. The Mosaic layout then partitions a unit square so that row height is proportional to the row total and column width is proportional to the column total, while color represents the observed entry. We prove how the Two-Walk energy combines direct alignment with shared-neighbor smoothness, derive an exact matrix vector product that permits sparse computation, and formalize the tiling and area semantics of Mosaic. Across 300 synthetic matrices and seven real data sets, Two-Walk obtains the lowest normalized 2-SUM in all 15 synthetic regimes and the highest Band@10% in 14. The largest gains occur when shared neighborhoods express the latent relational structure.

0.29

Dual-Slack Frontier Matching: Parallel Approximate Maximum-Product Matching

cs.DS ·2026-11-12 ·Marc A. Tunnell, Oguz Selvitopi, Xiaoye Sherry Li
similarity 0.55
Abstract

Maximum-product bipartite matching supports scaling and static pivot selection in sparse matrix preprocessing. We present Dual-Slack Frontier Matching (DSFM), a deterministic, shared-memory parallel algorithm for approximate maximum-product matching. Motivated by heavy matchings on small candidate supports, DSFM searches progressively exposed subgraphs ordered by fixed dual slack. Slack-ordered certified completion guarantees a perfect matching whenever one exists, or a maximum-cardinality matching with a Hall certificate otherwise. Every returned perfect matching carries an a posteriori geometric-mean quality bound; accumulated Hall obstructions can tighten this bound and improve the returned scaling. We compare DSFM with Heavy-Weight Perfect Matching (HWPM) and exact MC64 assignment on 598 nonsingular matrices. DSFM attains higher matching quality than HWPM over most quality thresholds. On a set of large instances consisting of 37 matrices, DSFM achieves a $3.53\times$ geometric-mean speedup over MC64, compared to $2.29\times$ for HWPM.

0.32

Structured Channel Network Pruning with Bi-Sparse Matrix Factorization

cs.CV ·2026-10-31 ·Jingjing Liu, Ziyang Wang, Xianchao Xiu, Wanquan Liu
code/data similarity 0.55
Abstract

Structured channel pruning for convolutional neural networks (CNNs) plays an important role in pattern recognition and deep learning. Nevertheless, existing methods usually calculate channel importance scores based on the magnitudes of individual filters, making it difficult to distinguish shared redundancy from individual channel contributions. To tackle this limitation, we propose a novel structured channel pruning method termed bi-sparse matrix factorization (BSMF). Specifically, BSMF characterizes the convolutional weight matrix as output-channel coefficients over a shared basis with row-wise $\ell_{2,p}$-norm and column-wise $\ell_{2,q}$-norm regularization terms, respectively. Note that $p,q\in[0,1)$, which, to our best knowledge, has not been explored in the literature. To solve the resulting non-convex optimization problem, we develop an efficient update scheme built upon the alternating direction method of multipliers (ADMM), in which all subproblems admit closed-form solutions. After that, a compact CNN is obtained by reconstructing the convolutional filters from the learned factors and discarding the redundant channels. Extensive experiments on the CIFAR-10 and ImageNet-1K datasets demonstrate that our proposed BSMF achieves significant network compression while maintaining high reconstruction accuracy. The source code is publicly available at https://github.com/xianchaoxiu/BSMF

0.36