An Algorithm to Recover Shredded Random Matrices

2023/10/25 by Caelan Atamanchuk, Luc Devroye, Atamanchuk, Caelan +3
Engineering · Mathematics · #60C05 (Primary) 68Q25 (Secondary) #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #Random Matrices and Applications #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2310.16715

openalex publication_date 2023/10/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given some binary matrix M, suppose we are presented with the collection of its rows and columns in independent arbitrary orderings. From this information, are we able to recover the unique original orderings and matrix? We present an algorithm that identifies whether there is a unique ordering associated with a set of rows and columns, and outputs either the unique correct orderings for the rows and columns or the full collection of all valid orderings and valid matrices. We show that there is a constant c > 0 such that the algorithm terminates in O(n²) time with high probability and in expectation for random n × n binary matrices with i.i.d. Bernoulli (p) entries (m_ij)_ij=1ⁿ such that (clog²(n))/(n(loglog(n))²) ≤ p ≤ (1)/(2).

Related

• Reconstruction of shredded random matrices
• A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionaries
• Learning Low Rank Matrices from O(n) Entries
• A Simpler Approach to Matrix Completion
• The Power of Convex Relaxation: Near-Optimal Matrix Completion