# Optimal Estimation and Completion of Matrices with Biclustering Structures

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Dec 2015.

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

- [Conformal link prediction for false discovery rate control](https://mlsanity.com/paper/2306.14693/) (2023)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Nonparametric Matrix Estimation with One-Sided Covariates](https://mlsanity.com/paper/2110.13969/) (2021)
- [Distribution-Free Matrix Prediction Under Arbitrary Missing Pattern](https://mlsanity.com/paper/2305.11640/) (2023)
- [Optimal Orthogonal Group Synchronization and Rotation Group Synchronization](https://mlsanity.com/paper/2109.13491/) (2021)
- [SDP Achieves Exact Minimax Optimality in Phase Synchronization](https://mlsanity.com/paper/2101.02347/) (2021)
- [Lattice partition recovery with dyadic CART](https://mlsanity.com/paper/2105.13504/) (2021)
- [Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations](https://mlsanity.com/paper/2111.04681/) (2021)
- [Structured Optimal Variational Inference for Dynamic Latent Space Models](https://mlsanity.com/paper/2209.15117/) (2022)
- [Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels](https://mlsanity.com/paper/2304.03590/) (2023)
- [Two-Sided Nearest Neighbors: An adaptive and minimax optimal procedure for matrix completion](https://mlsanity.com/paper/2411.12965/) (2024)
- [Nonparametric Trace Regression in High Dimensions via Sign Series Representation](https://mlsanity.com/paper/2105.01783/) (2021)

## Abstract (arXiv)

Biclustering structures in data matrices were first formalized in a seminal paper by John Hartigan (1972) where one seeks to cluster cases and variables simultaneously. Such structures are also prevalent in block modeling of networks. In this paper, we develop a unified theory for the estimation and completion of matrices with biclustering structures, where the data is a partially observed and noise contaminated data matrix with a certain biclustering structure. In particular, we show that a constrained least squares estimator achieves minimax rate-optimal performance in several of the most important scenarios. To this end, we derive unified high probability upper bounds for all sub-Gaussian data and also provide matching minimax lower bounds in both Gaussian and binary cases. Due to the close connection of graphon to stochastic block models, an immediate consequence of our general results is a minimax rate-optimal estimator for sparse graphons.